整列する時間を測る

これは何？

という記事に関する追加情報

例によって私にはコメントを書くことができないのでこうして記事を書いた。

データ

バブルソートということで、比較と入れ替えを行う。
比較の回数はデータに依存しないと思う（自信ない）けど、入れ替えの回数はデータに依存するので、データによって処理時間が変わる。

手元で「10000要素を5000回バブルソート」を go で書いたバイナリで実行したところ、

種	平均(秒)	標準偏差(秒)
固定	0.05362	0.0014
乱数	0.05495	0.0018

という具合で、データを変えると時間のばらつきが大きくなることがわかる。

今回はバブルソートの時間が知りたいというよりも、なんか時間のかかる処理をさせてその差を見たいということだと思うので、逆順に整列済みのデータを与えるのが良いと思った。

go の乱数

go の乱数が

go

	// 乱数で配列を初期化
	rand.Seed(time.Now().UnixNano())

となっていたけど、これは deprecated。

Deprecated: Programs that call Seed and then expect a specific sequence of results from the global random source (using functions such as Int) can be broken when a dependency changes how much it consumes from the global random source. To avoid such breakages, programs that need a specific result sequence should use NewRand(NewSource(seed)) to obtain a random generator that other packages cannot access.

雑にまとめると「君の知らないパッケージでグローバル乱数使うかもしれないから、 rand.Seed 使っても同じシーケンスにはならないかもよ。というわけで、 rand.Seed は非推奨」ということ。

Python の JIT

@ratorato さんの コメント で気がついたので、JIT で試してみた。

shell

$ pip install numba 

としてから

python

# 略
from numba import jit

# 略

# バブルソートアルゴリズムを実行する関数
@jit(nopython=True)
def bubblesort(array):
    # 以下略

と改変したコードを動かした。

	出力（抜粋）
元のコード (JIT なし)	24.13283 seconds.
改変後 (JIT 有効)	1.39359 seconds.

なるほど速い。

JavaScript (node) のこと

node の中身のことは全然知らないんだけど、Number を単なる 64bit 浮動小数点数として持っているとは思えない。おそらく C言語的に書くと

想像

struct Number{
  something s;
  union {
    int32_t i32;
    uint32_t u32;
    double d;
  } v;
};

のようになっていて、Number 一個で 96bit か 128bit ぐらいあるんだと思う。
だとすると、32bit 固定長でやっている Java なんかとくらべるとどうしても交換操作が遅くなる。

実際 new Array(ARRAY_SIZE); を new Int32Array(ARRAY_SIZE); に変えるだけで 1割以上速くなる。

比較操作については、最適化器に気づかれていて整数比較が走っているように見える。

というのは
array[i] = Math.floor(Math.random() * 0x7FFFFFFF); を array[i] = 0.1+Math.floor(Math.random() * 0x7FFFFFFF); に変えると 3割以上遅くなる。

まとめると

実装	元のコードを 1.00 とした時間
元のコード	1.00
Int32Array を利用	0.87
0.1 加算	1.36

という感じ。

Python と多倍長整数

一方 Python では多倍長整数となっている。
多倍長整数は普通の整数よりずっと遅いのが普通なので、コンパイラかどうかという話とは別のハンデを負っている。

Go や Java で多倍長整数版をつくるとだいぶ遅いと思う。試してないけど。