2016-08-23

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

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

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

2016-08-16

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

2016-08-07

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.

2016-05-19

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

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

2016-05-10

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

staff.hatenablog.com

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

Touring on the back

A young man walking into the classic studio

Narrow street between shops made by blocks

A french restaurant for adults

An unnoticeable sign for the popular avenue

One noon in the court of great palace

A classic station without lights at dusk

Overlooking similar houses in a town

Square shape houses and a deep pink car

A big church across the river over a cup of cappuccino

Great shrine gate covered by lots of green

A bronze statue of the famous samurai

A tower and the city in black and white

A big apple hanged in the air

Bronze lanterns hanged along the edge of a roof

The large stage area in a festival under the bad weather

Go for a ride

A high building behind the dead gingko tree

The park with circles on the ground

A tower in the distance