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

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

Google Code Jam 2016 Qualification Round レビュー in Haskell

今年もスケジュールが合わず参戦できなかったので後日レビュー実施。Pythonで解いた後にHaskellでやってみた。ただしHaskellで解いてみるだけでは今までと変わらない気がするので、do構文とArrayは使用しない、という制約を付けた。ただ、HaskellらしくList(無限リスト)を多用するように心がけてはいるものの、値を持ち回さないで状態系モナドを活用するという姿勢で解けるまでには至っていない。

  • Problem A. Counting Sheep

与えられた数字をNとすると、[N, N*2, N*3, ...] の無限リストを作成し、そのリストの要素を一つずつ集めたリストを準備する。つまり、[ [N], [N, N*2], [N, N*2, N*3], ...] というリストを作って、Unique . Sort で結果が"0123456789"になれば、そのリストの最後の要素を表示して終了。結果がそうならない場合に備えて実はその無限リストを1000に絞っている。

gist.github.com

  • Problem B. Revenge of the Pancakes

先頭のパンケーキと別の面のPancakeが現れたところで、同じ面のPancakeをひっくり返す。takeWhileとdropWhileを組み合わせて、Pancakeをひっくり返すリストと、そのままのリストを作り出し、それを全てのPancakeが同じ面になるまで繰り返す。全てが+ならそれで終了、-なら最後に1回加えて終了。

gist.github.com

  • Problem C. Coin Jam (Only for small)

1で始まり1で終わるnbitのcoinの無限リストを作って、Jamcoinの条件でfilterし、先頭からj個取り出す。出力に必要なNontrivial Divisorはfilterの条件式中に現れるが、出力として取り出せないので、Jamcoinを取り出した後、それを元に改めて作り出している。サンクのキャッシュが効けばそれほど非効率でも無いかなという淡い期待はあるが自信はない。これは、Python版でもLargeが解けないでいるが、Haskell版ではtakeの引数の型がIntのため、桁数制限無しのIntegerを一括して諦めているので、その時点でおそらくLargeは無理だろう。

gist.github.com

IPフラグメントされたTCPの接続テストを行う環境をNetwork Namespaceで構築する

TCP接続の際にはIPフラグメントが発生しないように、通常はPath MTU DiscoveryによってEnd-To-Endのパス中で最小のMTUを認識して、そのサイズに収まるようにパケットを送出する。これはTCPのデータ転送を効率良く行うための最適化の結果であり、インターネットのトラフィックにおいてTCPのIPフラグメントが発生しない、ということを意味しているわけではない。TCPのオフロード機能を持つNICをテストする場合など、テストが必要になるケースもあるだろう。

手順としては、パケット送信元のホストでPath MTU Discoveryを無効にして、送信先までのパスでインターフェースのMTUを小さく設定しておきルーティングを行う、という流れになる。端末を複数台用いることができれば上記手順通りに環境構築を行うことは簡単だが、ここは仮想環境とNetwork Namespaceを用いて最小の端末数で環境構築を行ってみる。ネットワークの概要は以下のようになる。パケット送出元となる仮想環境はVirtual Box上のLinuxを使う。

+-----------------------------------------+
|host1                                    |
|+---------------------------------------+|
|| guest1(fedora on virtual box)         ||
|| +---------------+                     ||
|| |ns1            |       192.168.100.99||
|| |      veth-ns12|===veth-ns21 <=> p1p2|===+ <---(Bridged)
|| |   192.168.1.10|   192.168.1.20      ||  |
|| +---------------+                     ||  |
|+---------------------------------------+|  |
+-----------------------------------------+  |
                         +---------------+   |
                         |host2          |   |
                         |192.168.100.101|===+
                         +---------------+

===は直結、<=>はルーティングを示し、Virtual Boxのネットワーク設定はブリッジとする。NATの場合は、ns1でPath MTU Discoveryを無効化してTCPのフラグメント(IPのフラグメントビット)をクリアしていても、NAT変換される際に該当のビットはセットされてしまうため、今回の目的としては問題がある。*1

Linux上でNetwork Namespace(ns1)を以下のように設定する。ここではLinuxとしてFedora 20(Linux Kernel 3.19/iproute 3.14.0-2)を使っている。

sudo ip netns add ns1
sudo ip link add veth-ns12 type veth peer name veth-ns21
sudo ip link set veth-ns12 netns ns1
sudo ip netns exec ns1 ifconfig veth-ns12 192.168.1.10/24
sudo ip netns exec ns1 route add default gw 192.168.1.20
sudo ip netns exec ns1 sysctl -w net.ipv4.ip_no_pmtu_disc=1

sudo sysctl -w net.ipv4.ip_forward=1
sudo ifconfig veth-ns21 192.168.1.20/24
sudo ifconfig p2p1 192.168.100.99/24
sudo ifconfig p2p1 mtu 1000

sudo iptables -F

ここで、host2からns1に接続するためには、host2にns1のネットワーク(192.168.1.10/24)宛のルーティングを設定するか、guest1上でProxy Arpを有効にする。それによって、guest1はhost2からのARP RequestをProxyしてns1に渡す役目をしてくれる。

sudo sysctl -w net.ipv4.conf.p2p1.proxy_arp=1

ns1からhost2にpingが通ることを確認したら、iPerfでTCPパケットを送り、パケットをキャプチャしてみると、Don't fragmentビットが落とされ、TCPのパケットがIPフラグメントされていることが分かる。

f:id:nishidy:20160427004724p:plain

あとはLinux上でtc/cbqなどを使って好きに帯域制御を行うことで、ある程度実ネットワーク模擬をすることもできる。 なお、Ubuntu 14.04 LTS(Linux Kernel 3.13/iproute2 3.12.0-2)では、作成したNamespace内に仮想ファイル/proc/net/ipv4/ip_no_pmtu_discが無かった。

*1:もしかするとhost1側のPath MTU Discoveryの設定を無効化すればセットされないのかもしれない

Deep Learning勉強会に参加しました

大阪大学人工知能研究会

Deep learningの勉強会に参加して、TensorFlowのBeginnersチュートリアルと、多層パーセプトロンの実装をPythonでやりました。基本的なところは青本やCouseraなどでカバーしてありましたので導入部分は特に問題無く進めましたが、ニューラルネットワークでも理解の難しい誤差逆伝播法の導出や確率的勾配降下法の利点の根拠、などついて説明の仕方が非常にうまいと感じましたし、自分の理解も進んだ気がしました。

また本勉強会の本筋であるDeep learningの内容としては、CNN(畳み込みニューラルネットワーク)の内容を分かりやすく説明してもらえました。 これも青本などでカバーできていたものの、数式の波の前に倒れそうになっていたので、初心者向けの説明をしてもらえたおかげでその内容は理解することができたと思います。

www.tensorflow.org

TensorFlowのBeginnersチュートリアルについては、基本的には以下のチュートリアルに貼り付けてあるコードを集めてコピーするだけで、MNISTを使った手書き文字認識のパーセプトロンの実行が試せるようになっています。

MNIST For ML Beginners

ただし上記は(単層の)パーセプトロンによる解法なので、これを多層パーセプトロンを用いたモデルに拡張しましたが、チュートリアルをそのままに隠れ層を増やすだけではうまく学習できない問題があり、勉強会ではこの解決方法を教えてもらうことができました。 直感的には、ハイパーパラメータである学習係数かSGDを繰り返す回数に改善点があるかなと思いましたが、これらを減らす・増やすしてみても精度はほとんど変わらなかったため、あとはパラメータの初期値がzerosを用いて初期化されているので問題がありそうと思いましたが、実際これが学習を妨げる要素になっていました。 0初期化ではなく、tf.truncated_normal()を用いて正規分布でランダムに初期化することで、96%程度まで精度を上げることが可能になりました。 以下は単層から隠れ層を2つ増やした多層パーセプトロンを実装した例です。

gist.github.com

$ python MNIST_2_hidden.py 
Extracting MNIST_data/train-images-idx3-ubyte.gz
Extracting MNIST_data/train-labels-idx1-ubyte.gz
Extracting MNIST_data/t10k-images-idx3-ubyte.gz
Extracting MNIST_data/t10k-labels-idx1-ubyte.gz
0.2543
0.8396
0.9029
0.9011
0.9283
0.927
0.9309
0.9469
0.946
0.9523
0.9535
0.9393
0.9571
0.9571
0.9582
0.9605
0.9634
0.9608
0.9541
0.9646

今後エキスパート向けの勉強会が開催されたときには再度参加したいと思います。

numpyの多次元配列の比較時に発生するエラーについて

numpyの多次元配列を比較しようとすると、配列の各要素を比較した結果を配列として返すので、all()やany()を使ってANDやORでreduceした結果を取得できそうだが、以下のようなエラーに遭遇する。

ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all()

多次元の場合はちゃんとメソッド使いましょう、という話。

また、差集合や積集合が欲しい場合、numpyの関数setdiff1dやintersect1dはその名の通り1次元にflattenしてしまうので、多次元配列の要素をそのまま結果に取り出したい場合はsetを使う。ただし、numpyのメソッドだけで完結しないので速度は出ないかもしれない。

$ 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.
>>> import numpy as np
>>> a = np.array([1,2,3])
>>> b = np.array([2,3,4])
>>> c = np.array([1,3,4])
>>> a==b
array([False, False, False], dtype=bool)
>>> a==c
array([ True, False, False], dtype=bool)
>>> all(a==b)
False
>>> any(a==b)
False
>>> any(a==c)
True
>>> all(a==a)
True
>>> (a==b).all()
False
>>> (a==b).any()
False
>>> (a==c).any()
True
>>> (a==a).all()
True
>>> aa = np.array([[10,20,30],[20,30,40],[30,40,50]])
>>> bb = np.array([[20,30,40],[30,40,50],[40,50,60]])
>>> cc = np.array([[10,20,30],[30,40,50],[40,50,60]])
>>> aa
array([[10, 20, 30],
       [20, 30, 40],
       [30, 40, 50]])
>>> aa==bb
array([[False, False, False],
       [False, False, False],
       [False, False, False]], dtype=bool)
>>> all(aa==bb)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all()
>>> (aa==bb).all()
False
>>> (aa==bb).any()
False
>>> (aa==cc).any()
True
>>> (aa==aa).any()
True
>>> np.setdiff1d(aa,bb)
array([10])
>>> np.setdiff1d(aa,cc)
array([], dtype=int64)
>>> np.intersect1d(aa,bb)
array([20, 30, 40, 50])
>>> np.intersect1d(aa,cc)
array([10, 20, 30, 40, 50])
>>> aas = set([tuple(x) for x in aa])
>>> bbs = set([tuple(x) for x in bb])
>>> ccs = set([tuple(x) for x in cc])
>>> np.array([x for x in aas-bbs])
array([[10, 20, 30]])
>>> np.array([x for x in aas-ccs])
array([[20, 30, 40]])
>>> np.array([x for x in aas-aas])
array([], dtype=float64)
>>> np.array([x for x in aas&bbs])
array([[20, 30, 40],
       [30, 40, 50]])
>>> np.array([x for x in aas&ccs])
array([[10, 20, 30],
       [30, 40, 50]])
>>> np.array([x for x in aas&aas])
array([[20, 30, 40],
       [10, 20, 30],
       [30, 40, 50]])

大きいサイズの配列でどの程度かかるのか試してみる。メモリに乗り切るなるべく大きいサイズの配列を準備して計測する。結果は違うが、numpyの関数と比較してみる。それぞれで差集合と積集合の処理速度が違うようだが、それほど差は無いように見える。

import numpy as np
import time

ai = [[x for y in range(2000)] for x in range(20000)]
bi = [[x+1 for y in range(2000)] for x in range(20000)]

al = np.array(ai)
bl = np.array(bi)

print(al)
print(bl)

start = time.time()
als = set([tuple(x) for x in al])
end = time.time()
print("{0:.5f} sec.".format(end-start))

bls = set([tuple(x) for x in bl])

start = time.time()
a_m_b = np.array([x for x in (als-bls)])
end = time.time()
print("{0:.5f} sec.".format(end-start))

start = time.time()
a_a_b = np.array([x for x in (als&bls)])
end = time.time()
print("{0:.5f} sec.".format(end-start))

print("# of setdiff  : {0}".format(len(a_m_b)))
print("# of intersect: {0}".format(len(a_a_b)))

start = time.time()
a_nm_b = np.setdiff1d(al,bl)
end = time.time()
print("{0:.5f} sec.".format(end-start))

start = time.time()
a_na_b = np.intersect1d(al,bl)
end = time.time()
print("{0:.5f} sec.".format(end-start))

print("# of setdiff1d  : {0}".format(len(a_nm_b)))
print("# of intersect1d: {0}".format(len(a_na_b)))
$ python numpy_test.py 
[[    0     0     0 ...,     0     0     0]
 [    1     1     1 ...,     1     1     1]
 [    2     2     2 ...,     2     2     2]
 ..., 
 [19997 19997 19997 ..., 19997 19997 19997]
 [19998 19998 19998 ..., 19998 19998 19998]
 [19999 19999 19999 ..., 19999 19999 19999]]
[[    1     1     1 ...,     1     1     1]
 [    2     2     2 ...,     2     2     2]
 [    3     3     3 ...,     3     3     3]
 ..., 
 [19998 19998 19998 ..., 19998 19998 19998]
 [19999 19999 19999 ..., 19999 19999 19999]
 [20000 20000 20000 ..., 20000 20000 20000]]
3.99010 sec.
1.13345 sec.
4.29675 sec.
# of setdiff  : 1
# of intersect: 19999
2.65021 sec.
1.83890 sec.
# of setdiff1d  : 1
# of intersect1d: 19999

Haskell Stateモナド(状態モナド遊びについての理解)

状態モナド遊び - あどけない話

すごいHaskellたのしく学ぼう!

すごいHaskellたのしく学ぼう!

HaskellのStateモナドは関数を扱うため、Maybeなどのモナドに比べてさらに理解が難しい。上記のサイトや参考書はそれをうまく説明しているが、それでも直感的にはまだ理解しづらいので、上記サイトの内容を以下のように紐解いてみるとより理解が深まると思う。

まず、Monadicモナドとcons0、runの定義は以下である。

instance Monad Monadic where
    Monadic f >>= g = Monadic $ \cnt0 -> let (result1, cnt1) = f cnt0
                                             Monadic h       = g result1
                                             (result2, cnt2) = h cnt1
                                         in (result2, cnt2)
    return x = Monadic $ \cnt -> (x, cnt)

cons0 x xs = Monadic $ \cnt -> (Cons x xs, cnt + 1)

run (Monadic func) initCnt = func initCnt

求めたい式は以下である。

run (cons0 "a" Nil >>= cons0 "b" >>= cons0 "c") 0

ここで、cons0 "a" Nilの部分を、その定義通りに置き換えてみる。

run (Monadic $ \cnt -> (Cons "a" Nil, cnt + 1) >>= cons0 "b" >> = cons0 "c") 0

最初の>>=を、その定義通りに置き換えてみる。

run (
    Monadic $ \cnt0 -> let (result1, cnt1) = \cnt -> (Cons "a" Nil, cnt + 1) cnt0
                            Monadic h      = cons0 "b" result1
                           (result2, cnt2) = h cnt1
                       in  (result2, cnt2)
    >>= cons0 "c"
) 0

cons0 "b" result1の部分も、その定義通りに置き換えてみる。

run (
    Monadic $ \cnt0 -> let (result1, cnt1) = \cnt -> (Cons "a" Nil, cnt + 1) cnt0
                            Monadic h      = Monadic $ \cnt -> (Cons "b" result1, cnt + 1)
                           (result2, cnt2) = h cnt1
                       in  (result2, cnt2)
    >>= cons0 "c"
) 0

ここで一度、置き換えた結果出現した関数の部分をfとおく。

run (
    Monadic $ f >>= cons0 "c"
) 0

次の>>=を、その定義通りに置き換えてみる。

run (
    Monadic $ \cnt0 -> let (result1, cnt1) = f cnt0
                            Monadic h      = cons0 "c" result1
                           (result2, cnt2) = h cnt1
                       in  (result2, cnt2)
) 0

cons0 "c" result1の部分も、その定義通りに置き換えてみる。

run (
    Monadic $ \cnt0 -> let (result1, cnt1) = f cnt0
                            Monadic h      = Monadic $ \cnt -> (Cons "c" result1, cnt + 1)
                           (result2, cnt2) = h cnt1
                       in  (result2, cnt2)
) 0

runを、その定義通りに置き換えてみる。

\cnt0 -> let (result1, cnt1) = f cnt0
              Monadic h      = Monadic $ \cnt -> (Cons "c" result1, cnt + 1)
             (result2, cnt2) = h cnt1
         in  (result2, cnt2)
0

つまり、runに与えた初期値0は、ラムダ式の引数cnt0に渡るので、それがそのままfに渡ることになる。これは、>>=をいくつ連結していても同じことである。fがネストされている状態になり、cnt0の値はfを通る度に規定された状態変化(この場合はcnt + 1)を伴いながら伝搬していく。

ここで再度fを見てみる。上記で見たとおり、cnt0は初期値0である。

Monadic $ \cnt0 -> let (result1, cnt1) = \cnt -> (Cons "a" Nil, cnt + 1) cnt0
                        Monadic h      = Monadic $ \cnt -> (Cons "b" result1, cnt + 1)
                       (result2, cnt2) = h cnt1
                   in  (result2, cnt2)

cnt0=0を代入して計算すると、fの結果は(Cons "b" (Cons "a" Nil), 2)となることが分かる。

ここで以下のincr1を使った例についても考えてみる。

incr1 = Monadic $ \cnt -> (999, cnt + 1)

cons1 x xs = do incr1
                return (Cons x xs)

run (cons1 "c" =<< cons1 "b" =<< cons1 "a" Nil) 0

doは構文糖衣で、>>=を使った式に書き換えられる。ただし、ここでincr1の結果を使っていないので、これは引数を取らないラムダ式になる。

cons1 x xs = incr1 >>= \_ -> return (Cons x xs)

incr1とreturnを、その定義通りに置き換える。

Monadic $ \cnt -> (999, cnt + 1) >>= \_ -> Monadic $ \cnt -> (Cons x xs, cnt)

>>=を、その定義通りに置き換える。すると、ラムダ式の引数に渡されたresult1の結果(ここでは999)は使われないことが良く分かる。

Monadic $ \cnt0 -> let (result1, cnt1) = \cnt -> (999, cnt + 1) cnt0
                       Monadic h       = \_ -> Monadic $ \cnt -> (Cons x xs, cnt) result1
                       (result2, cnt2) = h cnt1
                   in (result2, cnt2)

先ほどのcons0の場合と形は変われど、cons1の場合も同様に>>=の結合になるので、runに初期値として与えられたcnt0は、状態変化を伴いながら伝搬していくことになる。 incr2の例は、状態から取り出した値であるresult1の結果がラムダ式に渡ることになる。

ポイントになったのはcons1 x xsに現れたincr1だと思う。命令型脳で考えていると、このincr1のラムダ式が意味を成さない。また、構文糖衣であるdo式は命令型言語のように式を書ける便利構文である、と単純化してしまっていて、本来は>>=であることをスキップしてしまっている。そして、Haskellが純粋関数型であり、遅延評価を行い、>>=がbindと呼ばれる糊付け役である、ということを常に意識しながら読むことが大事である。