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

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

はじめに

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

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

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

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

技術の理解

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

例えば、僕はここ2年くらいは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];

図で整理すると以下の通りです。(一部簡略) f:id:blue_9:20200105195853p:plain

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)


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

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

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

https://i.imgur.com/Jh0Ddmx.gif

What is this?

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

機能は以下の2点です。

使い方

Syntax

Usage:

    $ gt <command> [params] [options]

Auto-Completer and Interactive Help

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

    $ github-trending

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

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

https://i.imgur.com/fwHg07X.png

Commands

https://i.imgur.com/eer1XsJ.png

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

https://i.imgur.com/5Bxmdld.png

View Repository README

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

    $ gt view [user/repository]

https://i.imgur.com/Liq7Wvq.png
https://i.imgur.com/VYLklBq.png

インストール

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

    $ pip install github-trending-cli

サポートPythonバージョン

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

終わりに

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

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

是非、ご利用ください。

Atom UI themeを公開しました

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

f:id:blue_9:20180621002648p:plain
seti-black-ui

特徴

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

atom.io

動機

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

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

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

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

What is it?

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

f:id:blue_9:20180610201721p:plain
amazonページに、メルカリでの値段が表示されます

f:id:blue_9:20180610201725p:plain
クリックするとメルカリの検索ページに飛びます

メリット

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


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

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

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


アルゴリズムの解説では
http://nw.tsuda.ac.jp/lec/dijkstra/
がとても素晴らしい。大変参考になりました。ありがとうございました。
しかし、このサイトではPythonJavaでの実装のみ。加えて、優先順位付きキューを使用している。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

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