読者です 読者をやめる 読者になる 読者になる

動的計画法とメモ化の実行状況が見たい

N x N のマス上にいくつか穴が開いていて、2マスを使うドミノを置いて、穴以外のマスを埋めることができるか、という問題があるとする。愚直に一つずつ試していくやり方としては、動的計画法が使える。ドミノは2マス使うので、縦に置くか、横に置くか、の選択肢がある。それぞれで処理を再帰呼び出しで分岐して、最終的にマスを埋めることができたかどうか、を判定すればよい。

ただし、これだけだとスケールしない。全く同じ盤面が何度も出てくるのに、毎回調べなければならないからだ。マスを埋めることができなかった、と判断された盤面が再度現れたときには、答えは分かっているのだから、それ以上処理を継続する必要はないはずだ。それを実現するのがメモ化(つまりキャッシュ)。動的計画法はメモ化と組み合わせて実装されることが多い。

Cの実装

メモ化に使うデータ構造をどうするか、つまり、盤面を覚えておく効率的なデータ構造、を考えなければいけない。ここでは、ドミノ(< >^ Vで示される)で埋めたマスが連続する数と、埋まっていないマス(_)が連続する数、を配列として持つことにする。つまり、

< > < >
+ ^ _ +
+ V _ _

という盤面があるとすると、6 3 1 2 になる。穴(+)についてはこだわらなくて良いので、それまでカウントしていた方の一部としてカウントする。今回は、盤面に対する情報はTrueかFalseなので、キャッシュの配列に含まれる場合はTrue(マスを埋めることができなかった)と考えれば良い。

マスを埋めることができた場合には、その盤面を出力している。また実行結果には、キャッシュにヒットした回数も出力している。

f:id:nishidy:20160828125539g:plain

  • 8x8マス。30回連続で別の盤面を実行。

f:id:nishidy:20160828131607g:plain

Javaの実装

上記のようなデータ構造は使いづらい。盤面を覚えておくのであれば、全ての盤面に対して一意のIDを割り当てることができればいいので、そういう用途ではmd5ハッシュ値が使える。JavaのDigestUtils(標準ライブラリでは無い)を使って実装した。注意すべきなのは、ドミノがどの方向で置かれていても同じように扱う必要があるので、盤面をコピーしてドミノの部分を共通のマークに入れ替えてからハッシュを取る必要がある。

f:id:nishidy:20160828132115g:plain

アルゴリズムについて

このような問題に対して動的計画法とメモ化を使うのは、やり方として間違っていないものの、データ範囲が大きくなるにつれて収束が難しくなる。Code Jamで言えば、Smallまではこのやり方で問題無いが、Largeを解くためには、このように愚直に試すやり方ではなく、盤面を俯瞰的に見ることでうまくいくかどうかを検証するアルゴリズムが必要になる。

なんとなく以下のような構造が出てくると、うまくいかないということは分かる...

+ _ +
_ _ _

Kubernetes background and network configuration

Kubernetesとそれに関連するミドルウェア

Kubernetesはdockerなどのコンテナのスケジューリングやロードバランスを担うクラスタリング制御用運用管理ツール。様々なミドルウェアを組み合わせて使うモジュラー型のアーキテクチャになっている。

etcdは分散KVSで、Zookeeperと同じようなもの。コンセンサスアルゴリズムによる合意形成の手段を実装することにより、分散環境におけるKVSのスケーラビリティとリダンダンシーを実現している。 etcdは、Linuxディストリビューションの一つであるCoreOSのアプリケーションとして提供されているが、今回はCentOS上で使用している。

flannelはネットワーク管理用ツールで、VXLANなどのオーバーレイのエンドポイントを作る。etcdとflannelが協調してクラスタ内のネットワークを形成する役目を持つ。

Kubernetesで実際にコンテナを作成するにはkubectl create -f pod.yamlでPodの作成を実行する。PodはKubernetesの概念において一つのノード上に存在するコンテナの集まりを指す。以下は、一つのコンテナのみを作成する最もシンプルなPodの設定ファイル。なお、replica数の指定なども設定ファイルに記述することになる。

# pod.yaml
apiVersion: v1
kind: Pod
metadata:
  name: nginx-pod
spec:
  containers:
    - name: nginx-container
      image: nginx
      ports:
      - containerPort: 80

なお、kubernetes がどのノードにPodを作成するか、はおまかせになるが、下記のように確認することはできる。

[xxx@master ~]$ kubectl describe pods nginx-pod
Name:           nginx-pod
Namespace:      default
Node:           minion2/10.140.0.4
...

ちなみに、yamlの設定ファイルを部分的に管理しておいて、後でマージして一つの大きな設定ファイルを作る、といったことがSpruceというOSSを使うとできるらしく、インフラのコード化を考えると重宝しそう。以下のスライドを参照のこと。

flanneldのコンフィグとして、etcdのURLエンドポイントとキーを指定する。flanneldが管理する、クラスタとして割り当てるネットワークサブネットは、etcdctlコマンドでetcdに登録する。なお、etcdへの登録や参照にはREST APIが提供されているので、curlを使ってPOSTメソッドで行うこともできる。

# /etc/sysconfig/flanneld
FLANNEL_ETCD="http://10.140.0.2:2379"
FLANNEL_ETCD_KEY="/atomic.io/network"```
# /atomic.io/network/config
{
    "Network": "10.20.0.0/16",
    "SubnetLen": 24,
    "Backend": {
        "Type": "vxlan",
        "VNI": 1
    }
}

VXLANにおける宛先解決

enakai00.hatenablog.com

上記の記事で特におもしろいのは、Linuxカーネルが発行するL3MISSというイベントによってアプリケーションにMACアドレス解決を移譲する、L2MISSによってアプリケーションにIPアドレスの取得を移譲する、というところ。 VXLANでは、どのようにUnknown Unicastの宛先VTEPを解決するかは、VTEPの実装に依存しているようだ。etcdのような仕組みを持たない場合は、単にマルチキャストによって全てのVTEPに解決を促すことになるだろう。 これを見ると、もうARPリクエストのようにマルチキャストやブロードキャストでMACアドレスを解決するという手法は時代遅れなのかもしれない。

なお、flannelを使わずにOpen vSwitchを使うこともできる。こちらの方が、OpenFlowのAPIを使って柔軟にネットワークの制御ができるはず。

http://kubernetes.io/docs/admin/ovs-networking/kubernetes.io

VXLANを使わないネットワーク構築方法

techblog.yahoo.co.jp

VXLANはオーバーレイなので、カプセリングのオーバーヘッドにより、データ転送のスループットが犠牲になる。これを避けるために、ピュアなL3ルーティングによってクラスタ内のネットワーク接続性を担保する方法もある。上記の記事は、flannelではなくCalicoを使った、BGPでのIPルーティングによるネットワーク構築方法になる。

クラスタを一つのASとみなしてプライベートAS番号を割り当てて管理している。BGPピアはメッシュで接続する必要があるため、BGPスピーカが増えた際のAS内のIntra BGP (iBGP)でのフルメッシュによる負荷を削減するために、ルートリフレクタを使ってスター型のピアリングを構成している。

おまけの、トラブル事例もおもしろい。サーバの前段に置いたロードバランサーARP応答させるため、サーバに直接届くARP要求には応えない設定にしておいたために、サーバ内のVMからのARP要求にも応えることが出来なかった、という問題のようだ。

Google Compute Engineでの構築

実際にGCE(GKE?)を使って、KubernetesでのPod構築と、VXLANによる疎通確認を行った。詳細な設定については他のソースに譲るが、外部に公開するサービスとしてのIPアドレスには0.0.0.0を使用する、service_account_key_fileを設定する、といった点には注意したい。sudo ss -untplでListenしているポートの確認を行いながら進めた方が良い(sudoを付けないとサービスの名前が取れないので、サービスでgrepをかけることができなくなる)。あるノードのホスト(10.140.0.4)から、別のノードのコンテナ(10.20.4.2)に対してPingを実施している。flannelデバイス(10.20.52.0)が、オーバーレイネットワークのソースアドレスになっている。10.140.0.0/16がアンダーレイ(物理ネットワーク)、10.20.0.0/16がオーバーレイ(仮想ネットワーク)になる。

受信側でtcpdump(-T vxlan)によってVXLANパケットをキャプチャしている。

[xxx@minion2 ~]$ ping 10.20.4.2
PING 10.20.4.2 (10.20.4.2) 56(84) bytes of data.
64 bytes from 10.20.4.2: icmp_seq=1 ttl=63 time=1.53 ms
64 bytes from 10.20.4.2: icmp_seq=2 ttl=63 time=0.365 ms
64 bytes from 10.20.4.2: icmp_seq=3 ttl=63 time=0.332 ms
64 bytes from 10.20.4.2: icmp_seq=4 ttl=63 time=0.347 ms
64 bytes from 10.20.4.2: icmp_seq=5 ttl=63 time=0.357 ms
64 bytes from 10.20.4.2: icmp_seq=6 ttl=63 time=0.373 ms
64 bytes from 10.20.4.2: icmp_seq=7 ttl=63 time=0.450 ms
64 bytes from 10.20.4.2: icmp_seq=8 ttl=63 time=0.336 ms
^C
--- 10.20.4.2 ping statistics ---
8 packets transmitted, 8 received, 0% packet loss, time 7001ms
rtt min/avg/max/mdev = 0.332/0.511/1.533/0.388 ms

[xxx@minion2 ~]$ ip r
default via 10.140.0.1 dev eth0  proto static  metric 100 
10.20.0.0/16 dev flannel.1  proto kernel  scope link  src 10.20.52.0 
10.20.52.0/24 dev docker0  proto kernel  scope link  src 10.20.52.1 
10.140.0.1 dev eth0  proto dhcp  scope link  metric 100 
10.140.0.4 dev eth0  proto kernel  scope link  src 10.140.0.4  metric 100 
169.254.169.254 via 10.140.0.1 dev eth0  proto dhcp  metric 100 
[xxx@minion1 ~]$ sudo tcpdump -i eth0 -T vxlan host 10.140.0.4
tcpdump: verbose output suppressed, use -v or -vv for full protocol decode
listening on eth0, link-type EN10MB (Ethernet), capture size 65535 bytes
16:07:19.808846 IP minion2.c.kubernetes-test-141313.internal.52229 > minion1.c.kubernetes-test-141313.internal.otv:
 VXLAN, flags [I] (0x08), vni 1
IP 10.20.52.0 > 10.20.4.2: ICMP echo request, id 1291, seq 1, length 64
16:07:19.808945 IP minion1.c.kubernetes-test-141313.internal.54591 > minion2.c.kubernetes-test-141313.internal.otv:
 VXLAN, flags [I] (0x08), vni 1
IP 10.20.4.2 > 10.20.52.0: ICMP echo reply, id 1291, seq 1, length 64
16:07:20.809721 IP minion2.c.kubernetes-test-141313.internal.52229 > minion1.c.kubernetes-test-141313.internal.otv:
 VXLAN, flags [I] (0x08), vni 1
IP 10.20.52.0 > 10.20.4.2: ICMP echo request, id 1291, seq 2, length 64
16:07:20.809804 IP minion1.c.kubernetes-test-141313.internal.54591 > minion2.c.kubernetes-test-141313.internal.otv:
 VXLAN, flags [I] (0x08), vni 1
IP 10.20.4.2 > 10.20.52.0: ICMP echo reply, id 1291, seq 2, length 64
16:07:21.809474 IP minion2.c.kubernetes-test-141313.internal.52229 > minion1.c.kubernetes-test-141313.internal.otv:
 VXLAN, flags [I] (0x08), vni 1

その他

ロードバランスやフェイルオーバーなども実際にさわってみたい。

ハノイの塔でディスク遷移が見たい

Necessary moves over 3 rods = logN - 1 (N = # of disks)

  • 5 disks

f:id:nishidy:20160823004621g:plain

  • 8 disks

f:id:nishidy:20160823003715g:plain

  • 12 disks

f:id:nishidy:20160823011116g:plain

gist.github.com

Sortアルゴリズムの消費メモリについて

Sortアルゴリズムを自分で書いてみるとそれぞれの特性が良く分かってくる。メモリを最も消費しないのは、Bubbleソートのようにソート対象の配列を直接触っていけるような、時間がかかるが単純なアルゴリズムの場合。

ただ、そのようなアルゴリズムを優先すべきアプリケーションはなかな思いつかない(配列が小さければ消費メモリを気にすることはないだろうし、消費メモリを気にすることがないなら計算量を考慮するから)。組み込み系で、消費メモリを小さくすることが最優先されるような場合は、必要になるかもしれない。

では、QuickソートとMergeソート、どのくらいメモリを使うのだろうか。前回の安直なプログラムと、与えられたソート対象の配列のメモリ領域をなるべく直接変更しながらメモリ量を抑えるプログラム、を書いて比較。 mallocをラップして、確保したメモリ量の総和と、mallocを呼んだ回数を、それぞれのアルゴリズムでカウントして比較する。

mallocのラップ関数は以下。

unsigned long mem_size;
unsigned int malloc_cnt;

void* _malloc(size_t size){
    mem_size += size;
    malloc_cnt ++; 
    return malloc(size);
}

Macで実行した結果がこちら。

$ ./three_sorts 10000000
Quick sort : 8.67 sec.
Sorted check OK.
mem_size = 4024MB, malloc_cnt = 30000000
Merge sort : 7.25 sec.
Sorted check OK.
mem_size = 2669MB, malloc_cnt = 29999997

$ ./two_sorts_low_memory 10000000
Quick sort : 6.56 sec.
Sorted check OK.
mem_size = 1563MB, malloc_cnt = 10000000
Merge sort : 3.91 sec.
Sorted check OK.
mem_size = 889MB, malloc_cnt = 9999999

メモリ割り当て(mallocを呼ぶ回数)が少なくなるとその分速くなる。メモリ割り当てにはそれ相当の時間がかかるからだ。

Mergeソートの場合だと、malloc_cntが一回少ないので、その分メモリ量が抑えられている。 良くわからないが、配列が非常に大きいので、その一回が使用するメモリ量を大きく引き離す結果になっているのだろうと予測。結局この一回が、速度差に影響している気がしてならないが。

ソート対象のサイズが100,000,000でも今回はMergeソートの方が遅くなる現象は発生していない。

$ ./two_sorts_low_memory 100000000
Quick sort : 77.14 sec.
Sorted check OK.
mem_size = 17042MB, malloc_cnt = 100000000
Merge sort : 42.81 sec.
Sorted check OK.
mem_size = 10169MB, malloc_cnt = 99999999

gist.github.com

Sortアルゴリズムについて

Bubbleソート、Quickソート、Mergeソート、をpythonとCで実装してみた。何年ぶりだろうか。なお、pythonはバグがあるので、Cを参照のこと。

Quickソートさえ分かっていればよくて、qsortとか標準ライブラリを使えば良いと思っていたけれど、Mergeソートに負けてしまった。 最悪の計算量でいうと、QuickソートはO(n2)になってしまうが、MergeソートはO(n log n)で済む。 ソート対象の配列が非常に大きい場合は、リスクを回避という観点で言えば、QuickソートよりMergeソートの方が良さそう。あとは、どのくらいソート対象の配列にランダム性があるのかどうか、という点も考える必要があるかもしれない。 pythonの方では、指定した数の倍のシーケンシャルなリストを作った後で、指定した数だけサンプリングし、その順序をランダマイズしたリストをソート対象としている。Cの方では、重複した値をテストするために、データをサンプリングする過程で100回に1回データの重複が発生するようにしている。

Cで試したところ、mergeソートの方がquickソートよりも常に速いが、あるデータサイズを超えると、quickソートの方が速くなる。というか、mergeソートがかなり遅くなる。これはおそらく、mergeソートの実装の方がメモリを消費するので、先に上限に達してしまうからだろう。mergeソートは必ず全ての要素を最小単位まで分割するため、quickソートよりもメモリの消費量は多い。(実装でうまく回避できるのかもしれないが)

ちなみに、メモリ量を最も抑えられるのはBubbleソートですね。必要なメモリは、ソート対象の配列と一つの変数だけ。スピードは非常に遅い(平均の計算量がO(n2))けれど使用可能なメモリ量に厳しい制限があり、かつ、ソート対象の配列のサイズが小さいことが分かっていれば、Bubbleソートが解になりそうです。

  • Bubbleソート
import sys, random

i = int(sys.argv[1])
arr = list(range(i*2))
random.sample(arr,i)
rand_arr = list(arr)
random.shuffle(rand_arr)

def bs(arr):
    i=len(arr)
    while i>0:
        for j in range(0,i-1):
            if arr[j] > arr[j+1]:
                arr[j],arr[j+1] = arr[j+1],arr[j]
        else:
            i -= 1
    return arr

sorted_arr = bs(rand_arr)
assert sorted_arr == arr

if not sorted_arr == arr:
    print(rand_arr)
    print(sorted_arr)
  • Quickソート
import sys,random

#arr = list(map(lambda x: int(x), sys.argv[1:]))

i = int(sys.argv[1])
arr = list(range(i*2))
random.sample(arr,i)
rand_arr = list(arr)
random.shuffle(rand_arr)

def qs(arr):
    #print(arr)

    if len(arr) == 1:
        return arr

    med = arr[0]
    #med = arr[int(len(arr)/2)]
    sg = list(filter(lambda x: x<med, arr))
    lg = list(filter(lambda x: x>med, arr)) 

    if len(sg) == 0:
        return [med]+qs(lg) 
    if len(lg) == 0:
        return qs(sg)+[med]

    return qs(sg)+[med]+qs(lg) 

sorted_arr = qs(rand_arr)
assert sorted_arr==arr

if not sorted_arr == arr:
    print(rand_arr)
    print(sorted_arr)

  • Mergeソート
import sys, random

i = int(sys.argv[1])
arr = list(range(i*2))
random.sample(arr,i)
random_arr = list(arr)
random.shuffle(random_arr)

#print(arr)
#print(random_arr)

def bs(arr):
    size = len(arr)
    if size == 1:
        return arr
    else:
        half = int(size/2)
        left_arr = bs(arr[:half])
        right_arr = bs(arr[half:])

        merged_arr = []
        left_idx = right_idx = 0
        while left_idx<half or right_idx<size-half:
            if left_idx == half:
                merged_arr.append(right_arr[right_idx])
                right_idx += 1
            elif right_idx == size-half:
                merged_arr.append(left_arr[left_idx])
                left_idx += 1
            elif left_arr[left_idx] < right_arr[right_idx]:
                merged_arr.append(left_arr[left_idx])
                left_idx += 1
            elif left_arr[left_idx] >= right_arr[right_idx]:
                merged_arr.append(right_arr[right_idx])
                right_idx += 1

        return merged_arr

sorted_arr = bs(random_arr)
#print(sorted_arr)

assert sorted_arr == arr

if not sorted_arr == arr:
    print(arr)
    print(sorted_arr)
$ time python bubblesort.py 5000

real    0m10.906s
user    0m10.831s
sys 0m0.053s

$ for i in $(seq 1 3); do time python mergesort.py 1000000; done

real    0m26.053s
user    0m24.332s
sys 0m0.363s

real    0m26.276s
user    0m25.174s
sys 0m0.375s

real    0m23.590s
user    0m23.303s
sys 0m0.220s

$ for i in $(seq 1 3); do time python quicksort.py 1000000; done

real    0m28.814s
user    0m28.425s
sys 0m0.341s

real    0m26.910s
user    0m26.567s
sys 0m0.311s

real    0m28.079s
user    0m27.733s
sys 0m0.325s
  • C実装

gist.github.com

  • C実装のMacでの実行結果
$ ./sort 10000000
Quick sort : 13.00 sec.
Sorted check OK.
Merge sort : 9.92 sec.
Sorted check OK.

$ ./sort 20000000
Quick sort : 21.84 sec.
Sorted check OK.
Merge sort : 16.55 sec.
Sorted check OK.

$ ./sort 50000000
Quick sort : 78.04 sec.
Sorted check OK.
Merge sort : 201.94 sec.
Sorted check OK.

Rustの文字列とコピーのlifetimeについて

Rustで簡単なスレッドプログラムを書いているとき、ふとコンパイルが通らなくなって困ったのでいろいろと調べていて、gitterできいて解決したことを書き留めておく。

標準入力から入力された文字列を取得して関数に渡し、その中でチャネルを通してスレッドに送り、スレッド側で標準出力にその文字列を出力する。 指定された回数分だけそのスレッドが文字列を受け取ったら、メインスレッド側にまた別のチャネルを使って終わったことを知らせる。 sync_channelはブロックするので、このように別のチャネルをスレッドジョインの役目として使うこともできる。 以下が動くバージョンのプログラム。

use std::thread;
use std::sync::mpsc;
use std::io;

fn call<'a>(txt:&'a String, tx1: &mpsc::SyncSender<String>){
    tx1.send(txt.clone()).unwrap();
}

fn main() {
    let mut txt = String::new();
    let _ = io::stdin().read_line(&mut txt);

    let (tx1,rx1) = mpsc::sync_channel(1);
    let (tx2,rx2) = mpsc::sync_channel(1);

    thread::spawn(move||{
        for _ in 0..2 {
            let rtext = rx1.recv().unwrap();
            println!("{}",&rtext);
        }   
        tx2.send(()).unwrap();
    }); 

    call(&txt,&tx1);

    txt = "xyz".to_string();

    call(&txt,&tx1);

    rx2.recv().unwrap();
}

この場合、txtはmainで複数回使われているので、callに対して所有権を渡すことはできず、callがそれを借用することになる。ここで、callの引数となるtxtを&Stringにすべきか&strにすべきかが良く分からなかった。文字列リテラル&strで、to_string()メソッドでStringに変換できるし、&をつけることで&strにもできる。ただしこのプログラムでよく分かる明らかな違いは、strCloneを実装していないということで、callの引数となるtxtはおいそれと&strにはできないはず、ということ。チャネルの先はメインスレッドよりも長生きするかもしれないスレッドのため、txtのポインタを送ることはできないので、ここでCloneは必須。

例えば以下のようにすると、

fn call<'a>(txt:&'a str, tx1: &mpsc::SyncSender<&str>){
    tx1.send(txt.clone()).unwrap();                                                                                                             
}  

以下のようなコンパイルエラーになる。

src/main.rs:6:18: 6:25 error: cannot infer an appropriate lifetime for lifetime parameter `'a` due to conflicting requirements
src/main.rs:6     tx1.send(txt.clone()).unwrap();
                               ^~~~~~~

これは、callの第2引数の型に'aがついていないので第1引数のtxtとはlifetimeが異なるはずだが、callが借用したtxtの参照先をチャネルで渡そうとしているので要求が矛盾している、と言われていることになる。txtに対してclone()を呼んでいるので、意図としては借用したtxtの値をコピーしたものを渡しているつもりだが、これはtxtが&strであることにより、値ではなくポインタをコピーしていることになってしまう。strCloneを持っていないが、ポインタはそうではないということらしい。

なお、ここのコンパイルエラーでは以下のようにも言われてしまうが、

consider using an explicit lifetime parameter as shown: fn call<'a>(txt: &'a str, tx1: &mpsc::SyncSender<&'a str>)

これに従ったからといって解決しない。結局は、

`txt` does not live long enough

となり、上記で説明した通りスレッドの方がメインスレッドよりも長生きするかもしれないため、コンパイルは通らない。

ブログがFlickrの写真貼り付けに対応した

staff.hatenablog.com

ということでFlickr Proで管理していた時代からだいぶ時間が経ってしまっていた写真を載せてみた。ユーザ選択も写真マルチ選択も簡単で、楽しい。

Touring on the back

photo by senbonzakura08

A young man walking into the classic studio

photo by senbonzakura08

Narrow street between shops made by blocks

photo by senbonzakura08

A french restaurant for adults

photo by senbonzakura08

An unnoticeable sign for the popular avenue

photo by senbonzakura08

One noon in the court of great palace

photo by senbonzakura08

A classic station without lights at dusk

photo by senbonzakura08

Overlooking similar houses in a town

photo by senbonzakura08

Square shape houses and a deep pink car

photo by senbonzakura08

A big church across the river over a cup of cappuccino

photo by senbonzakura08

Great shrine gate covered by lots of green

photo by senbonzakura08

A bronze statue of the famous samurai

photo by senbonzakura08

A tower and the city in black and white

photo by senbonzakura08

A big apple hanged in the air

photo by senbonzakura08

Bronze lanterns hanged along the edge of a roof

photo by senbonzakura08

The large stage area in a festival under the bad weather

photo by senbonzakura08

Go for a ride

photo by senbonzakura08

A high building behind the dead gingko tree

photo by senbonzakura08

The park with circles on the ground

photo by senbonzakura08

A tower in the distance

photo by senbonzakura08