いかなる算術演算子も使わずに加算を実現する

という問題を解く。

答えは、ビット演算子をたくみに使って加算を実現する。 つまり、ビット演算子は算術演算子には含まれないので、使っても良い。

具体的には、XORによって各位の加算を実現し、ANDと左シフト演算子によって繰り上げを実現する。 繰り上げがなくなった時点で（ゼロになった時点で）、計算は終了する。

以下のように、デバッグしながら実行してみる。

#include <stdio.h>
#define BITS 32

void bit(int n){
        int i;
        for(i=0;i<BITS;i++)
                printf("%d", (n >> (BITS-1-i)) & 1);
        printf("\n");
}

int bitplus(int a, int b){
        bit(a); bit(b); printf("\n");
        if(b==0)
                return a;
        return bitplus( a^b, (a&b)<<1 );
}

int main(int argc, char* argv[])
{
        int a = atoi(argv[1]);
        int b = atoi(argv[2]);
        bit(a); bit(b); printf("\n");
        printf("Ans = %d\n\n", bitplus( a^b, (a&b)<<1 ));
        return 0;
}

$ ./bitplus 3 5
00000000000000000000000000000011
00000000000000000000000000000101

00000000000000000000000000000110
00000000000000000000000000000010

00000000000000000000000000000100
00000000000000000000000000000100

00000000000000000000000000000000
00000000000000000000000000001000

00000000000000000000000000001000
00000000000000000000000000000000

Ans = 8

$ ./bitplus 65535 65536
00000000000000001111111111111111
00000000000000010000000000000000

00000000000000011111111111111111
00000000000000000000000000000000

Ans = 131071

$ ./bitplus 65535 65535
00000000000000001111111111111111
00000000000000001111111111111111

00000000000000000000000000000000
00000000000000011111111111111110

00000000000000011111111111111110
00000000000000000000000000000000

Ans = 131070

$ python
Python 3.4.3 (default, Oct 24 2015, 14:51:44) 
[GCC 4.2.1 Compatible Apple LLVM 6.1.0 (clang-602.0.53)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> int("10101010",2)
170
>>> int("01010101",2)
85
>>> quit()

$ ./bitplus 170 85
00000000000000000000000010101010
00000000000000000000000001010101

00000000000000000000000011111111
00000000000000000000000000000000

Ans = 255

$ ./bitplus 171 85
00000000000000000000000010101011
00000000000000000000000001010101

00000000000000000000000011111110
00000000000000000000000000000010

00000000000000000000000011111100
00000000000000000000000000000100

00000000000000000000000011111000
00000000000000000000000000001000

00000000000000000000000011110000
00000000000000000000000000010000

00000000000000000000000011100000
00000000000000000000000000100000

00000000000000000000000011000000
00000000000000000000000001000000

00000000000000000000000010000000
00000000000000000000000010000000

00000000000000000000000000000000
00000000000000000000000100000000

00000000000000000000000100000000
00000000000000000000000000000000

Ans = 256

右シフト演算

負の値を右シフトした場合、符号ビットが立っているので、1で埋められる。

...
        int k = -65535;
        bit(k);
        bit(k>>=10);
        bit(k<<=10);
...

11111111111111110000000000000001
11111111111111111111111111000000
11111111111111110000000000000000

なお、シフト対象となる左辺値の型のサイズより大きい値でシフトしようとすると、以下のようにMac（Apple LLVM version 7.0.2 (clang-700.1.81)）ではwarningが出るが実行はできる。

...
        bit(k>>=64);
...

$ gcc bitplus.c 
bitplus.c:87:14: warning: shift count >= width of type [-Wshift-count-overflow]
        bit(k>>=64);
             ^  ~~
1 warning generated.

ただ、結果としての値は、シフト演算を行う前の値になっていた。

11111111111111110000000000000001

Cではこのようなシフト演算は規定外なので、何が起こるかはプラットフォームに依存する。

Goだと、以下の記事の通り、-1になる。

Goでは、nビットシフトは1ビットシフトをn回行ったのと同じ（CやJavaは違う） - Qiita

$ cat bit.go 
package main

import (
    "fmt"
)

func main() {
    var a int32 = -65535
    fmt.Printf("%b\n", a>>64)
}

$ go run bit.go 
-1

浮動小数点数のビット表現

IEEE 754 - Wikipedia

浮動小数点のビット表現を見てみる。float型の変数からアドレスを取得し、それをint型のポインタとしてキャストしてから、その値を取り出す。

#include <stdio.h>
#define BITS 32

void bitf(float f){
        int i;
        int n = *((int *)&f);
        for(i=0;i<BITS;i++)
                printf("%d", (n >> (BITS-1-i)) & 1);
        printf("\n");
}

int main()
{
        bitf(-10.5);
        bitf(10.5);
        return 0;
}

$ ./floatbit 
11000001001010000000000000000000
01000001001010000000000000000000

符号部は、負数で1、正数で0。 仮数部と指数部の算出は以下の通り。 算出した指数部には規定通り127のバイアスを加える。

10.5 * 2^0
= 5.25 * 2^1
= 2.625 * 2^2
= 1.3125 * 2^3
= (1+0.3125) * 2^3

0.3125 * 2 = 0.625 (0)
0.625 * 2 = 1.25 (1)
0.25 * 2 = 0.5 (0)
0.5 * 2 = 1.0 (1)

指数部は3+127=130で10000010、仮数部は2ビット目と4ビット目が立つので0101、となるので、-10は1_10000010_01010000...となる。

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

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

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

Cの実装

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

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

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

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

• 実装 Dynamic Programming for board game in C · GitHub

• 4x4マス。途中結果を表示しながら実行。

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

Javaの実装

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

• 実装 Dynamic Programming for board game in Java · GitHub

• コンパイル javac -classpath ./commons-codec-1.10/commons-codec-1.10.jar BoardGame.java

• 12x12マス。やってみたものの、Completeせず。また、穴が少ない場合に、時間がかかっていることが分かる。

アルゴリズムについて

このような問題に対して動的計画法とメモ化を使うのは、やり方として間違っていないものの、データ範囲が大きくなるにつれて収束が難しくなる。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を使って、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

• 8 disks

• 12 disks

実装はこちら Tower of hanoi with arbitrary disks showing the move among rods · GitHub

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

Sortアルゴリズムの消費メモリについて（続） - Tech random memoranda

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が一回少ないので、その分メモリ量が抑えられている。 良くわからないが、配列が非常に大きいので、その一回が使用するメモリ量を大きく引き離す結果になっているのだろうと予測。結局この一回が、速度差に影響している気がしてならないが。

→ Quick sortにおいて、ソート対象の配列数が1の場合、関数を抜けるべきところを実行してしまっているため、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

実装はこちら Optimized for memory usage · GitHub

Sortアルゴリズムについて

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

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

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

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

• Python実装のLinux上での実行結果

$ 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実装

Run sort algorithms with randomized single data · GitHub

• 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にもできる。ただしこのプログラムでよく分かる明らかな違いは、strはCloneを実装していないということで、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の第２引数の型に'aがついていないので第１引数のtxtとはlifetimeが異なるはずだが、callが借用したtxtの参照先をチャネルで渡そうとしているので要求が矛盾している、と言われていることになる。txtに対してclone()を呼んでいるので、意図としては借用したtxtの値をコピーしたものを渡しているつもりだが、これはtxtが&strであることにより、値ではなくポインタをコピーしていることになってしまう。strはCloneを持っていないが、ポインタはそうではないということらしい。

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

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

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