プログラミングの次のステップを目指す君たちへ

「プログラミングを学んでみたけど、何を作ったら良いか分からない。」 そんな質問を最近よく受ける。そのたびに僕は「何かアプリを作る。とか、競技プログラミングをする。とか・・・」という曖昧な答えをする。なぜ、曖昧な答えをするのか。それには一言で答えられない理由があるからだ。それを、ここに記したい。

はじめに

僕はここ数年、次に何を作ったらいいか。と迷うことはない。日々、アイデア・仮説が浮かんでくるからだ。しかしそんな僕も昔は、悩む彼らと同じ、もしくはそれ以上だった(3年くらい同じ悩みと向き合ってきた)。そのとき僕も同じように有識者に相談した。しかし、彼らの答えといえば「作りたいものを作ればいいじゃん」だった。「いや、その作りたいものがないんだよ！」とは言えず、路頭に迷っていた。

正直今も自分の人生を掛けるほど何か作りたいものがあるわけではない。しかし、小さなことだけれども、あれを試してみたいな。とか、プロトタイプを作ってみたいな。と日々思う。そう成れたのは主に２つの理由があると思う。

• 技術の理解
• 生き方の理解

それぞれについて少し考えてみたい。

技術の理解

今振り返ると、作りたいものがなかった頃は、技術の理解が足りていなかったと思う。その頃は、せいぜい様々なプログラミング言語の文法を理解しているレベルだった。しかし今は、コンピュータ技術の根本や背景を理解できている。また、コンピュータがやるべき仕事 も理解できている。特に大切なのは後者で、プログラミングができる。とか、プロトコルを知っている。ではなくて、コンピュータがやるべき仕事は何か、これからコンピュータをどのように使っていけば良いか。を理解することが大切であると思う。そのためには、表面的な知識・理解ではなく、技術の歴史・背景・考え方を学ぶ必要があるし、それらを理解するためには(堂々巡りのようだが)、表面的な知識の圧倒的理解が必要である。

例えば、僕はここ２年くらいはlive coding(メディア・アート)やそのツール開発をしている。その理由は主に以下のようである。

1. プログラミングがシステム開発の道具だけになりつつある現代へのアンチテーゼ
2. プログラミングを理解している人が、理解していない人へ自然言語で説明することが求められている現代へのアンチテーゼ
3. コンピュータとアートがこれから結びついていく将来への展望

このように、細かな技術どうこうよりも、これからのコンピュータ技術のあり方、コンピュータってこんなことできるんだと！ということを考え・発信していきたいと思い活動していると、その情熱が枯渇しない限りはアイデアが止まることはない。

作りたいものがない。という人達に足りないのは、ビジョンだと思う。そしてビジョンを描けるようになるためには、それ相応の知識が必要である。アウトプットができないのは、インプットが足りないからである。だから焦らず、学び続けることを大切にして欲しい。

生き方への理解

悩んでいた当時の僕にもアイデアも少しはあったと思う。しかし、それを形にできなかったのは、時間をかけて上手くいかなったらどうしよう。とか、もう誰かがやっているよ。というもう一人の自分の声が聞こえてきたからだと思う。そんな当時の僕は、ポール・グレアム氏のエッセイが指南書だった。

今、何を、どうやってすればいいかって? まず興味の持てるプロジェクトを選ぶことだ。ある分量の資料を研究するとか、 何かを作ってみるとか、何かの問題の答えを見つけてみるとか。 ひと月以内で終わらせられるようなプロジェクトがいい。 そして、ちゃんと終わらせられる手段があるようなものにする。 少しは頑張らなくちゃならないようなものがいいけれど、ほんとうに少しだけでいい。 特に最初はね。もし二つのプロジェクトのどっちを選ぶか迷ったら、 面白そうな方を選ぼう。失敗したら、もう一方を始めればいいんだ。 これを繰り返す。そうすると次第に、ちょうど内燃機関みたいに、 このプロセスが自分で走り出すようになる。一つのプロジェクトが次の プロジェクトを生み出すようになるんだ。(そうなるまでには何年もかかるけれどね。)プロジェクトが君の将来目指すものにあまり関係なさそうだったとしても、 心配することはない。目指すものに到達する道っていうのは、君が思うより ずっと大きく曲がりくねるものなんだ。プロジェクトをやることで、道は伸びてゆくんだ。 一番大事なのは、わくわくして取り組むことだ。そうすれば経験から学ぶことができるからだ。

当時は理解できなったが、今では本当にその通りだと思う。現在は歳を取って、一ヶ月くらいあっという間に過ぎる。だから、やってもやらなくてもあっという間に過ぎるなら、やってみるかとなる。

また、アイデアの循環ができるようになってきた。何か作り始めたら、途中でアイデアが生まれ、次に作りたいものができるし、作り上げたものから話が広がり、別の仕事を受けることもある。

何かを作ったら終わりではなく、次に繋がるようになる。それは少し経験がないと理解できないと思うが、やり始めなければ永遠に理解できない。上手くいかなったらな。とか、時間を無駄にしてしまってはな。とか嫌なことが頭を過ることは分かる。しかし、実際失敗することはないし、今見えていない次のアイデアは絶対にある。だから、とりあえず手を動かしてみたい。これを人生の早い段階で気付けると後々楽になる。

まとめ

何を作ったらいいか分からない。は、技術者的理由と人間的理由があると思う。というのが僕の意見だ。

本当に今は楽しい。次々アイデアが浮かんでくる(そのためにそれ相応の努力をしているが、その話は別途としよう)。自分が昔憧れていた側に回れているいることは、とても不思議だし、とても自信になっている。今悩んでいる子たちも、自分でブレークスルーを作り、こちら側に来てくれることを願う。

【Python】ListとDequeのパフォーマンスの違い〜CPyhtonの実装を読んで〜

先日以下のブログを読みました。

dev.classmethod.jp

PythonのListとDequeのパフォーマンスを比較しています。 しかし、「なぜパフォーマンスに違いが生まれるのか。」記されていないため、この記事ではCPythonの実装を読みながら、違いが生まれる理由を探ってみたいと思います。
※本記事で扱うCPythonのコードは最新版ではありません。 ListはCommit ID3c87a667bb367ace1de6bd1577fdb4f66947da52、DequeはCommit IDd4edfc9abffca965e76ebc5957a92031a4d6c4d4です。

　目次

1. List Objectについて
2. Deque Objectについて
3. List vs Deque（先頭要素)
   3.1 List
   3.2 Deque
   3.3 まとめ(先頭要素)
   
4. List vs Deque（中間要素)
   4.1 List
   4.2 Deque
   4.3 まとめ(中間要素)
   
5. List vs Deque（末端要素)
   5.1 List
   5.2 Deque
   5.3 まとめ(末端要素)
   
6. おわりに
   
7. 参考文献
   

1. List Objectについて

初めに、簡単にデータ構造を整理しておきます。
Listは以下のようになっております。

typedef struct {
    PyObject_VAR_HEAD

    PyObject **ob_item;

    Py_ssize_t allocated;
} PyListObject;

#ifndef PyList_MAXFREELIST
#define PyList_MAXFREELIST 80
#endif
static PyListObject *free_list[PyList_MAXFREELIST];
static int numfree = 0;

ob_itemがvectorへのポインタを指すことで、可変長データ構造を実現しています。 (Listをnew()する場合、free_listからPyListObjectを一つ取り出し、 メモリ確保しています。

op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));

)

https://github.com/python/cpython/blob/3c87a667bb367ace1de6bd1577fdb4f66947da52/Include/listobject.h https://github.com/python/cpython/blob/3c87a667bb367ace1de6bd1577fdb4f66947da52/Objects/listobject.c

2. Deque Objectについて

Dequeは、双方向リンクリストと配列のハイブリッドで実現されています。

#define BLOCKLEN 64
#define CENTER ((BLOCKLEN - 1) / 2)

typedef struct BLOCK {
    struct BLOCK *leftlink;
    PyObject *data[BLOCKLEN];
    struct BLOCK *rightlink;
} block;

typedef struct {
    PyObject_VAR_HEAD
    block *leftblock;
    block *rightblock;
    Py_ssize_t leftindex;       /* 0 <= leftindex < BLOCKLEN */
    Py_ssize_t rightindex;      /* 0 <= rightindex < BLOCKLEN */
    size_t state;               /* incremented whenever the indices move */
    Py_ssize_t maxlen;          /* maxlen is -1 for unbounded deques */
    PyObject *weakreflist;
} dequeobject;

static PyTypeObject deque_type;

#define MAXFREEBLOCKS 16
static Py_ssize_t numfreeblocks = 0;
static block *freeblocks[MAXFREEBLOCKS];

図で整理すると以下の通りです。(一部簡略)

https://github.com/python/cpython/blob/d4edfc9abffca965e76ebc5957a92031a4d6c4d4/Modules/_collectionsmodule.h

https://github.com/python/cpython/blob/d4edfc9abffca965e76ebc5957a92031a4d6c4d4/Modules/_collectionsmodule.c

3. List vs Deque（先頭要素)

参考ブログでは以下のコードで、処理時間を比較しています。

List

list_array = list(range(100000))
for i in range(1000):
    list_array.pop(0)

処理時間は以下の通りです。
1回目　elapsed_time:0.05488991737365723[sec]
2回目　elapsed_time:0.04288434982299805[sec]
3回目　elapsed_time:0.054895877838134766[sec]

Deque

deque_array = deque(range(100000))
for i in range(1000):
    deque_array.popleft()

処理時間は以下の通りです。
1回目　elapsed_time:0.008365631103515625[sec]
2回目　elapsed_time:0.007332801818847656[sec]
3回目　elapsed_time:0.008947134017944336[sec]

3.1. List

List.pop()の実装部はここです。
エラーチェック後、実質的にpop処理をしているのは以下の部分です。

status = list_ass_slice(self, index, index+1, (PyObject *)NULL);

pop(0)の場合、以下のようになります。

ex: a = [1,2,3,4,5,6,7,8,9,10]

list_ass_slice(self, 0, 1, (PyObject *)NULL);

#define b ((PyListObject *)v)
    if (v == NULL)
        n = 0;

    norig = ihigh - ilow; // 1
    d = n - norig;        // -1
    item = a->ob_item;
    s = norig * sizeof(PyObject *); // sizeof(PyObject *)

    if (s) {
        memcpy(recycle, &item[ilow], s);
    }

    if (d < 0) { /* Delete -d items */
        Py_ssize_t tail;
        tail = (Py_SIZE(a) - ihigh) * sizeof(PyObject *); // 9 * sizeof(PyObject *)
        memmove(&item[ihigh+d], &item[ihigh], tail); // a[1:10] を a[0:9]に移動
        if (list_resize(a, Py_SIZE(a) + d) < 0) { // Py_SIZE(a)の変更
        }
        item = a->ob_item;
    }
    for (k = norig - 1; k >= 0; --k)
        Py_XDECREF(recycle[k]); // ref--
    result = 0;

決めては以下の処理。

memmove(&item[ihigh+d], &item[ihigh], tail); // a[1:10] を a[0:9]に移動

計算量がO(n)であることが分かります。

3.2. Deque

deque.leftpop()の実装部はここです。 サイズチェック後、実質的にpop処理をしているのは以下の部分です。

item = deque->leftblock->data[deque->leftindex];
deque->leftindex++;
Py_SIZE(deque)--;

計算量がO(1)であることが分かります。

3.3. まとめ(先頭要素)

先頭要素への処理の計算量は以下の通りです。

処理	計算量
List.pop(0)	O(1)
Deque.leftpop()	O(n)

4. List vs deque（中間の要素）

参考ブログでは以下のコードで、処理時間を比較しています。

List

list_array = list(range(10000))
for i in range(1000000):
    list_array.remove(20)
    list_array.insert(20, 20)

処理時間は以下の通りです。
1回目　elapsed_time:25.979241132736206[sec]
2回目　elapsed_time:26.479660749435425[sec]
3回目　elapsed_time:26.32246232032776[sec]

Deque

deque_array = deque(range(10000))
for i in range(1000000):
    deque_array.remove(20)
    deque_array.insert(20, 20)

処理時間は以下の通りです。
1回目　elapsed_time:21.0693142414093[sec]
2回目　elapsed_time:21.471088647842407[sec]
3回目　elapsed_time:21.121334075927734[sec]

4.1. List

Listのremoveの実装はここです。
中身の肝は以下。

list_ass_slice(self, i, i+1, PyObject *)NULL)

popと同様に計算量がO(n)であることが分かります。

Listのinsertの実装はここです。
中身の肝は以下。

ins1(self, index, object)

insert(20,20)の場合、以下のようになります。

ex: a = [0,...,19,21...,100000]

ins1(self, 20, 20)

Py_ssize_t i, n = Py_SIZE(self); // 99,999
if (list_resize(self, n+1) < 0) // Py_SIZE(self)++

items = self->ob_item;
for (i = n; --i >= where; )
     items[i+1] = items[i];
Py_INCREF(v);
items[where] = v;

計算量がO(n)であることが分かります。

4.2. Deque

dequeのremoveの実装はここです。
中身の肝は以下。

for (i=0 ; i<n ; i++) {
        PyObject *item = deque->leftblock->data[deque->leftindex];
        int cmp = PyObject_RichCompareBool(item, value, Py_EQ);

        if (cmp > 0) {
            PyObject *tgt = deque_popleft(deque, NULL);
            assert (tgt != NULL);
            if (_deque_rotate(deque, i))
                return NULL;
            Py_DECREF(tgt);
            Py_RETURN_NONE;
        }
        _deque_rotate(deque, -1);
}

要素判定は常に左端要素を使用します。要素が見つかるまでrotate(-1)を行います。要素が見つかり次第、popleft()し、rotate(要素index)します。
計算量がO(n)であることが分かります。

この_deque_rotate()の中身はここです。
中身の肝は以下。

Py_ssize_t m = n;

if (m > rightindex + 1)
    m = rightindex + 1;
if (m > leftindex)
    m = leftindex;
    assert (m > 0 && m <= len);
    rightindex -= m;
    leftindex -= m;
    src = &rightblock->data[rightindex + 1];
    dest = &leftblock->data[leftindex];
    n -= m;
    do {
        *(dest++) = *(src++);
    } while (--m);

    deque->leftblock = leftblock;
    deque->rightblock = rightblock;
    deque->leftindex = leftindex;
    deque->rightindex = rightindex;

計算量がO(n)であることが分かります。

次にinsertの実装はここです。
中身の肝は以下。

    if (_deque_rotate(deque, -index))
        return NULL;
    if (index < 0)
        rv = deque_append(deque, value);
    else
        rv = deque_appendleft(deque, value);
    if (_deque_rotate(deque, index))
        return NULL;

rotate()して左端か右端にappend()しています。
rotate()の計算量は上記の通り、O(n)であることが分かります。

4.3. まとめ(中間要素)

中間要素への処理の計算量は以下の通りです。

処理	計算量
List.remove()	O(n)
List.insert()	O(n)
Deque.remove()	O(n)
Deque.insert()	O(n)

参照ブログでは、Dequeの方が高速に処理できました。 その理由は、以下の通りです。

List: 削除要素以外の全要素でメモリ移動が伴う
Deuqe: 先頭要素から削除要素までのみメモリ移動が伴う

処理時間測定コードでは、先頭から20番目の要素をromove()、insert()しています。よってDequeの方が、メモリ移動の対象になる要素が少なく、処理時間が高速だったと考えられます。

5. List vs deque（末端の要素）

参考ブログでは以下のコードで、処理時間を比較しています。

List

list_array = list(range(1000))
for i in range(100000):
    list_array.append(0)

処理時間は以下の通りです。
1回目　elapsed_time:0.017949581146240234[sec]
2回目　elapsed_time:0.019548416137695312[sec]
3回目　elapsed_time:0.019548416137695312[sec]

Deque

deque_array = deque(range(1000))
for i in range(100000):
    deque_array.append(0)

処理時間は以下の通りです。
1回目　elapsed_time:0.023968935012817383[sec]
2回目　elapsed_time:0.023933887481689453[sec]
3回目　elapsed_time:0.01991128921508789[sec]

5.1. List

Listのappendの実装はここです。 中身の肝は以下。

app1(self, object)

append(0)の場合、以下のようになります。

Py_ssize_t n = PyList_GET_SIZE(self);
if (list_resize(self, n+1) < 0) // Py_SIZE(self)++

Py_INCREF(v);
PyList_SET_ITEM(self, n, v); // (((PyListObject *)(op))->ob_item[i] = (v))

計算量がO(1)であることが分かります。

5.2. Deque

dequeのappendの実装はここです。 中身の肝は以下。

deque_append_internal(deque, item, deque->maxlen)

deque_append_internal()の実装はここです。 中身の肝は以下。

    deque->rightindex++;
    deque->rightblock->data[deque->rightindex] = item;

計算量がO(1)であることが分かります。

5.3. まとめ(末端要素)

末尾要素への処理の計算量は以下の通りです。

処理	計算量
List.append()	O(1)
Deque.append()	O(1)

6. おわりに

本記事では、PythonのListとDequeの処理の違いをCythonのコードから探ってみました。
ListとDequeによって「なぜパフォーマンスに違いが生まれるのか。」理解につながれば幸いです。

7. 参考文献

https://postd.cc/python-internals-pyobject/ https://note.nkmk.me/python-collections-deque/ https://docs.python.org/ja/3/c-api/sequence.html https://docs.python.org/ja/3/c-api/intro.html https://docs.python.org/3/c-api/typeobj.html

protocol buffersバイナリデータを読む

目的

protocol buffersでエンコーディングされたバイナリデータを読んでみます。

準備

この記事では、Protocol Buffer Basics: Pythonのコードを使用します。

addressbook.proto

syntax = "proto2";

package tutorial;

message Person {
  required string name = 1;
  required int32 id = 2;
  optional string email = 3;

  enum PhoneType {
    MOBILE = 0;
    HOME = 1;
    WORK = 2;
  }

  message PhoneNumber {
    required string number = 1;
    optional PhoneType type = 2 [default = HOME];
  }

  repeated PhoneNumber phones = 4;
}

message AddressBook {
  repeated Person people = 1;
}

writing_a_message.py

#! /usr/bin/python

import addressbook_pb2
import sys

# This function fills in a Person message based on user input.
def PromptForAddress(person):
  person.id = int(raw_input("Enter person ID number: "))
  person.name = raw_input("Enter name: ")

  email = raw_input("Enter email address (blank for none): ")
  if email != "":
    person.email = email

  while True:
    number = raw_input("Enter a phone number (or leave blank to finish): ")
    if number == "":
      break

    phone_number = person.phones.add()
    phone_number.number = number

    type = raw_input("Is this a mobile, home, or work phone? ")
    if type == "mobile":
      phone_number.type = addressbook_pb2.Person.MOBILE
    elif type == "home":
      phone_number.type = addressbook_pb2.Person.HOME
    elif type == "work":
      phone_number.type = addressbook_pb2.Person.WORK
    else:
      print "Unknown phone type; leaving as default value."

# Main procedure:  Reads the entire address book from a file,
#   adds one person based on user input, then writes it back out to the same
#   file.
if len(sys.argv) != 2:
  print "Usage:", sys.argv[0], "ADDRESS_BOOK_FILE"
  sys.exit(-1)

address_book = addressbook_pb2.AddressBook()

# Read the existing address book.
try:
  f = open(sys.argv[1], "rb")
  address_book.ParseFromString(f.read())
  f.close()
except IOError:
  print sys.argv[1] + ": Could not open file.  Creating a new one."

# Add an address.
PromptForAddress(address_book.people.add())

# Write the new address book back to disk.
f = open(sys.argv[1], "wb")
f.write(address_book.SerializeToString())
f.close()

reading_a_message.py

#! /usr/bin/python

import addressbook_pb2
import sys

# Iterates though all people in the AddressBook and prints info about them.
def ListPeople(address_book):
  for person in address_book.people:
    print "Person ID:", person.id
    print "  Name:", person.name
    if person.HasField('email'):
      print "  E-mail address:", person.email

    for phone_number in person.phones:
      if phone_number.type == addressbook_pb2.Person.MOBILE:
        print "  Mobile phone #: ",
      elif phone_number.type == addressbook_pb2.Person.HOME:
        print "  Home phone #: ",
      elif phone_number.type == addressbook_pb2.Person.WORK:
        print "  Work phone #: ",
      print phone_number.number

# Main procedure:  Reads the entire address book from a file and prints all
#   the information inside.
if len(sys.argv) != 2:
  print "Usage:", sys.argv[0], "ADDRESS_BOOK_FILE"
  sys.exit(-1)

address_book = addressbook_pb2.AddressBook()

# Read the existing address book.
f = open(sys.argv[1], "rb")
address_book.ParseFromString(f.read())
f.close()

ListPeople(address_book)

解析

以上のコードよりADDRESS_BOOK_FILEを作成します。

% python reading_a_message.py ADDRESS_BOOK_FILE

Person ID: 1
  Name: jone
  E-mail address: jone@example.com
  Mobile phone #:  000-0000-0001
Person ID: 2
  Name: mike
  E-mail address: mike@example.com
  Home phone #:  000-0000-0002
  Work phone #:  000-0000-0022

ADDRESS_BOOK_FILEをhexdumpすると、以下のようになります。

% hexdump -C ADDRESS_BOOK_FILE
00000000  0a 2d 0a 04 6a 6f 6e 65  10 01 1a 10 6a 6f 6e 65  |.-..jone....jone|
00000010  40 65 78 61 6d 70 6c 65  2e 63 6f 6d 22 11 0a 0d  |@example.com"...|
00000020  30 30 30 2d 30 30 30 30  2d 30 30 30 31 10 00 0a  |000-0000-0001...|
00000030  40 0a 04 6d 69 6b 65 10  02 1a 10 6d 69 6b 65 40  |@..mike....mike@|
00000040  65 78 61 6d 70 6c 65 2e  63 6f 6d 22 11 0a 0d 30  |example.com"...0|
00000050  30 30 2d 30 30 30 30 2d  30 30 30 32 10 01 22 11  |00-0000-0002..".|
00000060  0a 0d 30 30 30 2d 30 30  30 30 2d 30 30 32 32 10  |..000-0000-0022.|
00000070  02                                                |.|
00000071

ADDRESS_BOOK_FILEをEncodingに従って解析すると以下のようになります。

アドレス	00000000	00000001	00000002	00000003	00000004	00000005	00000006	00000007
データ	0a	2d	0a	04	6a	6f	6e	65
内容	0x00001010 -> 最後の3ビット(010)よりLength-delimited型, 3回右シフトすると field number = 0x0001(people)	payload size (0x2d bytes) (jone分)	0x00001010 -> 最後の3ビット(010)よりLength-delimited型, 3回右シフトすると field number = 0x0001(name)	文字列は4 byte	j	o	n	e

アドレス	00000008	00000009	0000000a	0000000b	0000000c	0000000d	0000000e	0000000f
データ	10	01	1a	10	6a	6f	6e	65
内容	0x00010000 -> 最後の3ビット(000)よりVarint型, 3回右シフトすると field number = 0x0010(id)	id(jone) = 1	0x00011010 -> 最後の3ビット(010)よりLength-delimited型, 3回右シフトすると field number = 0x0011(email)	文字列は0x10 byte	j	o	n	e

アドレス	00000010	00000011	00000012	00000013	00000014	00000015	00000016	00000017
データ	40	65	78	61	6d	70	6c	65
内容	@	e	x	a	m	p	l	e

アドレス	00000018	00000019	0000001a	0000001b	0000001c	0000001d	0000001e	0000001f
データ	2e	63	6f	6d	22	11	0a	0d
内容	.	c	o	m	0x00100010 -> 最後の3ビット(010)よりLength-delimited型, 3回右シフトすると field number = 0x0100(phones)	payload size (0x11 bytes)	0x00001010 -> 最後の3ビット(010)よりLength-delimited型, 3回右シフトすると field number = 0x0001(number)	文字列は0x0d byte

アドレス	00000020	00000021	00000022	00000023	00000024	00000025	00000026	00000027
データ	30	30	30	2d	30	30	30	30
内容	0	0	0	-	0	0	0	0

アドレス	00000028	00000029	0000002a	0000002b	0000002c	0000002d	0000002e	0000002f
データ	2d	30	30	30	31	10	00	0a
内容	-	0	0	0	1	0x00010000 -> 最後の3ビット(000)よりVarint型, 3回右シフトすると field number = 0x0010(type)	PhoneType = 0(MOBILE)	0x00001010 -> 最後の3ビット(010)よりLength-delimited型, 3回右シフトすると field number = 0x0001(people)

アドレス	00000030	00000031	00000032	00000033	00000034	00000035	00000036	00000037
データ	40	0a	04	6d	69	6b	65	10
内容	payload size (0x40 bytes) (mike分)	0x00001010 -> 最後の3ビット(010)よりLength-delimited型, 3回右シフトすると field number = 0x0001(name)	文字列は4 byte	m	i	k	e	0x00010000 -> 最後の3ビット(000)よりVarint型, 3回右シフトすると field number = 0x0010(id)

アドレス	00000038	00000039	0000003a	0000003b	0000003c	0000003d	0000003e	0000003f
データ	02	1a	10	6d	69	6b	65	40
内容	id(mike) = 2	0x00011010 -> 最後の3ビット(010)よりLength-delimited型, 3回右シフトすると field number = 0x0011(email)	文字列は0x10 byte	m	i	k	e	@

アドレス	00000040	00000041	00000042	00000043	00000044	00000045	00000046	00000047
データ	65	78	61	6d	70	6c	65	2e
内容	e	x	a	m	p	l	e	.

アドレス	00000048	00000049	0000004a	0000004b	0000004c	0000004d	0000004e	0000004f
データ	63	6f	6d	22	11	0a	0d	30
内容	c	o	m	0x00100010 -> 最後の3ビット(010)よりLength-delimited型, 3回右シフトすると field number = 0x0100(phones)	payload size (0x11 bytes)	0x00001010 -> 最後の3ビット(010)よりLength-delimited型, 3回右シフトすると field number = 0x0001(number)	文字列は0x0d byte	0

アドレス	00000050	00000051	00000052	00000053	00000054	00000055	00000056	00000057
データ	30	30	2d	30	30	30	30	2d
内容	0	0	-	0	0	0	0	-

アドレス	00000058	00000059	0000005a	0000005b	0000005c	0000005d	0000005e	0000005f
データ	30	30	30	32	10	01	22	11
内容	0	0	0	2	0x00010000 -> 最後の3ビット(000)よりVarint型, 3回右シフトすると field number = 0x0010(type)	PhoneType = 1(HOME)	0x00100010 -> 最後の3ビット(010)よりLength-delimited型, 3回右シフトすると field number = 0x0100(phones)	payload size (0x11 bytes)

アドレス	00000060	00000061	00000062	00000063	00000064	00000065	00000066	00000067
データ	0a	0d	30	30	30	2d	30	30
内容	0x00001010 -> 最後の3ビット(010)よりLength-delimited型, 3回右シフトすると field number = 0x0001(number)	文字列は0x0d byte	0	0	0	-	0	0

アドレス	00000068	00000069	0000006a	0000006b	0000006c	0000006d	0000006e	0000006f
データ	30	30	2d	30	30	32	32	10
内容	0	0	-	0	0	2	2	0x00010000 -> 最後の3ビット(000)よりVarint型, 3回右シフトすると field number = 0x0010(type)

アドレス	00000070
データ	02
内容	PhoneType = 2(WORK)

バイナリって楽しいですね。

参考文献

Protocol Buffers Developer Guide Overview
Protocol Buffers Developer Guide Encoding
https://developers.google.com/protocol-buffers/docs/pythontutorial=Protocol Buffer Basics: Python
GitHub - protocolbuffers/protobuf: Protocol Buffers - Google's data interchange format
Proto3 Language Guide（和訳）

github-trending を公開しました。[Command Line Tool]

コマンドラインツール「github-trending」を公開しました。

What is this?

コマンドラインでTrending repositories on GitHub today · GitHubを眺めるツールです。
github.com

機能は以下の２点です。

• Trending repositories on GitHub today · GitHubを眺める
• リポジトリのREADMEを眺める

使い方

Syntax

Usage:

    $ gt <command> [params] [options]

Auto-Completer and Interactive Help

以下のコマンドにより、フィッシュスタイルの補完とインタラクティブヘルプを使用した自動補完メニューを有効にできます。

    $ github-trending

オートコンプリータ内では、同じ構文が適用できます。

    github> gt <command> [params] [options]

Commands

View Trending

Trending repositories on GitHub today · GitHubを眺めます。
Usage:

    $ gt trend [option] [limit]

Examples:

    $ gt trend
    $ gt trend --language python
    $ gt trend --dev
    $ gt trend --monthly
    $ gt trend --limit 10

View Repository README

リポジトリのREADMEを眺めます。
Usage:

    $ gt view [user/repository]

インストール

本ツールはgithub-trending-cli · PyPIで公開しております。
次のコマンドでインストールできます。

    $ pip install github-trending-cli

サポートPythonバージョン

• Python 2.6
• Python 2.7
• Python 3.3
• Python 3.4
• Python 3.5

サポートプラットフォーム

• Mac OS X
  • Tested on OS X 10.12

終わりに

本ツールはOSSとして、Apache licenseで公開しております。(PR絶賛受け付けております！)
github.com

また、使い方の詳細はREADMEに書いております。

是非、ご利用ください。

Atom UI themeを公開しました

「seti-black-ui」というAtom UI themeを公開しました。

seti-black-ui

特徴

・黒いです
・ミニマルなデザインです

atom.io

動機

元々「seti-ui」というthemeを使っていましたが、自分好みに改良を加えているうちに、オリジナルとは異なるものになっていったので、公開することにしました。(seti-uiの作者Jesse Weed氏に謝意を表す)
ただ、あくまでもオレオレテーマなので、自分のためだけに改良して、呑気にリリースする予定です。
syntax themeも近い内に公開する予定です。

興味がある方は是非ご利用ください。

Chrome拡張機能「その本、メルカリで!」を公開しました

Chrome拡張機能「その本、メルカリで!」を公開しました。

What is it?

amazonで見ている本が、メルカリで何円なのか分かります。

amazonページに、メルカリでの値段が表示されます

クリックするとメルカリの検索ページに飛びます

メリット

・amazonでの値段とメルカリでの値段が比較できます(中古本はメルカリの方が安い場合が多い)
・ワンクリックでメルカリの検索ページに飛べます

以下で公開しているので、興味がある方は是非ご利用ください。
chrome.google.com

ダイクストラ法(C言語)

ダイクストラ法について調べてみると、思った以上に解説が少ない。それでもアルゴリズムを理解する分には、充分にある。
しかし、実装については別だ。
「ダイクストラ法　C言語」でググって表示されるサイトに載っているコードはまともに動かない。
だから、C言語でダイクストラ法を書くことにした。

アルゴリズムの解説では
http://nw.tsuda.ac.jp/lec/dijkstra/
がとても素晴らしい。大変参考になりました。ありがとうございました。
しかし、このサイトではPythonとJavaでの実装のみ。加えて、優先順位付きキューを使用している。C言語には、そんな高級なデータ構造はないので、普通に配列を使って実装します。
以下がそのコード。(コメントは参考サイトのアルゴリズム解説の文を用いました && コメントは変数名は冗長に書きました)

#include <stdio.h>

#define INF 10000000
#define SIZE 1000
#define TRUE 1
#define FALSE 0

int DIST[SIZE][SIZE];
int COST[SIZE];
int VIA[SIZE];
int N;
char USED[SIZE];

int dijkstra(int start, int goal)
{
  int min, target;

  COST[start] = 0;

  while(1){

    /* 未確定の中から距離が最も小さい地点(a)を選んで、その距離を その地点の最小距離として確定します */
    min = INF;
    for(int i = 0; i < N; i++){
      if(!USED[i] && min > COST[i]) {
        min = COST[i];
        target = i;
      }
    }

    /* 全ての地点の最短経路が確定 */
    if(target == goal)
      return COST[goal];

    /* 今確定した場所から「直接つながっている」かつ「未確定の」地点に関して、
    今確定した場所を経由した場合の距離を計算し、今までの距離よりも小さければ書き直します。 */
    for(int neighboring = 0; neighboring < N; neighboring++){
      if(COST[neighboring] > DIST[target][neighboring] + COST[target]) {
        COST[neighboring] = DIST[target][neighboring] + COST[target];
        VIA[neighboring] = target;
      }
    }
    USED[target] = TRUE;
  }
}

int main(void){
  int r;
  int a,b,l;
  int s,d;

  /* 初期化 */
  for(int i = 0; i < SIZE; i++) {
    COST[i] = INF;
    USED[i] = FALSE;
    VIA[i] = -1;
    for(int j = 0; j < SIZE; j++)
      DIST[i][j] = INF;
  }

  /* 入力 */
  scanf("%d %d", &N, &r);
  for(int i = 0; i < r; i++){
    scanf("%d %d %d", &a, &b, &l);
    DIST[a][b] = l;
  }
  scanf("%d %d", &s, &d);

  /* ダイクストラ法で最短経路を求める */
  printf("distance:%d\n", dijkstra(s,d));

  /* 経路を表示(ゴールから) */
  int node = d;
  printf("%d", node);
  while(1){
    node = VIA[node];
    printf(" -> %d", node);
    if (node == s) break;
  }

  return 0;
}

実行結果。

% ./dijkstra
7 10
0 1 30
0 3 10
0 2 15
1 3 25
1 4 60
2 3 40
2 5 20
3 6 35
4 6 20
5 6 30
0 6
distance:45
6 -> 3 -> 0

データは参考サイトの項「課題２」にあります。