【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」にあります。

2017を振り返る

年末バタバタで今年を振り返るのは無理そうだと思ったが、今年も残り2時間というところで、急に手持ち無沙汰になったので簡単に振り返る。

1月~3月

CTF4bに行ったことをきっかけにCTFを始めた。Pwnを中心にやっていたこともあり、低レイヤの魅力にハマって、色々な文献に目を通して、世界が広がった。勉強会にも参加して、人脈を作れたことも良かった。
大学卒業した。みんな4年間ありがとう!

5月

逆求人イベントに行って、色々な会社と接することができた。そこで、やっぱりエンジニアではなく、シンクタンク・コンサル行こうと思い、シンクタンク・コンサルのインターンを探し始めた。
SecHackが合格になった。技術やるならセキュリティがいいなと思っていたので、嬉しかった。受かったからには、頑張らないとなという思いから、苦手なネットワークの勉強をした。(結局、一年取り組むことになる)

6月、7月

インターン応募のためにES書きまくって面接しまくった。コンサルのための本とかたくさん読んで、ESの書き方、面接での答え方を勉強して、実践、反省を繰り返した。最初の頃は下手くそだったけど、途中からは受かりまくったので、やり方は間違ってなかったらしい。この辺から秋までは技術の勉強は対してやらなかったので、エンジニアとしての成長はあまりない。

8月

旅に行けた。絶景最高。

9月

2社インターン。すごく優秀な社員さんと学生に囲まれて幸せだった。結果はボロボロだったけど、コンサルの思考・仕事術を少しは盗めたことは大きい。仮説思考・アウトプットドリンに触れることができて良かった。

10月

北海道寒かったな。
インターンのためにまたESを書き始めた。

11月

祖父が亡くなった。色々考えた。

12月

インターン。相変わらずアウトプットドリブン。金融業界に興味を持ち始めた。

総まとめ

コツコツとネットワークの勉強を続けて、だいぶ理解が深まった。一番苦手な分野が苦手でなくなったことは大きい。
面接をたくさんこなして、面接が得意になった。
コンサルの仕事が出来て良かった。コンサルの仕事術はどの仕事をしても役に立つ。

6月から忙しくなって、4つくらいプロジェクトは回すわ、各地に飛ばなくてはならないわで、途中体調も崩したし、疲れた。しかし、精神的充実は大きい。それらのプロジェクトは今も続いてるわけだけど、全体的にパフォーマンスが悪い。一つ一つの完成度は8割くらいでイマイチだと思ってる。来年はマルチタスクをこなせるようになりたい。(そのためには何をすべきなのか?)

来年やりたいこと

「書く」ことに時間を割きたい。
47都道府県制覇したい。(現在40都道府県)
2月から圧倒的当事者意識の会社で働くので、気を引き締めて頑張りたい。


あっ、音楽では渋谷系にハマった。
オザケンスカパラピチカート・ファイヴ。一年ずっと聞いてたな。あと、The Strokes

皆様一年ありがとうございました!
来年も是非よろしくお願いいたします!!