NumPy
前回、重複のないランダムな数値のリストを作成する方法を紹介しました。
今回はNumPyのargsortでソートの方法を変えた場合の処理時間を検討したので、その結果を紹介します。
それでは始めていきましょう。
元の配列がすでにソートされている場合
まずはソートする対象である元の配列がすでにソートされており、0から順に並んでいる場合です。
その場合、並び替えは必要ないのですが、ソートが必要かどうかの確認がいるため、ある程度の処理時間がかかります。
その確認作業にかかる時間がソート方法によって違うのか検証しようと言うわけです。
「quicksort」、「mergesort」、「heapsort」、「stable」の順に見ていきましょう。
%%timeit
import numpy as np
data = np.arange(10000)
np.argsort(data, kind="quicksort")
実行結果
89.3 µs ± 3.41 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)%%timeit
import numpy as np
data = np.arange(10000)
np.argsort(data, kind="mergesort")
実行結果
24.3 µs ± 915 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)%%timeit
import numpy as np
data = np.arange(10000)
np.argsort(data, kind="heapsort")
実行結果
629 µs ± 5.83 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)%%timeit
import numpy as np
data = np.arange(10000)
np.argsort(data, kind="stable")
実行結果
24.2 µs ± 837 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)「mergesort」と「stable」が同じくらいの処理時間で24μ秒程度、次に「quicksort」で90μ秒程度、最後に「hearpsort」で630μ秒程度でした。
最大で26倍程度も違うという結果となりました。
元の配列が逆にソートされている場合
次は元の配列が完全に逆にソートされている場合です。
つまり降順に並んでおり、それを昇順に並び替えるということです。
%%timeit
import numpy as np
data = np.arange(10000, 0, -1)
np.argsort(data, kind="quicksort")
実行結果
120 µs ± 3.44 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)%%timeit
import numpy as np
data = np.arange(10000, 0, -1)
np.argsort(data, kind="mergesort")
実行結果
28.7 µs ± 931 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)%%timeit
import numpy as np
data = np.arange(10000, 0, -1)
np.argsort(data, kind="heapsort")
実行結果
655 µs ± 12.9 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)%%timeit
import numpy as np
data = np.arange(10000, 0, -1)
np.argsort(data, kind="stable")
実行結果
29.2 µs ± 1.12 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)今回も「mergesort」と「stable」が同じくらいの処理時間で30μ秒程度、次に「quicksort」で120μ秒程度、最後に「hearpsort」で655μ秒程度でした。
重複のないランダムな数値のリストの場合
次に重複のないランダムな数値のリストの場合を試してみます。
ランダムな数字は前回紹介した重複のないランダムな数値のリストを作成する方法で作成しました。
import numpy as np
import sys
def int_nooverlap(start, end, samples):
if end - start < samples:
print("Sample number should be less than numbers from start to end.")
sys.exit(1)
else:
rng = np.random.default_rng()
initial_data = list(range(start, end))
data = []
while len(data) < samples:
pick_index = rng.integers(len(initial_data))
data.append(initial_data[pick_index])
del initial_data[pick_index]
return data
data = int_nooverlap(0, 10000, 10000)この場合、同じランダムな数値のリストに対してソート速度を検討したいので、Jupyter Notebook上で異なるセルで並列的にソートしています。
%%timeit
import numpy as np
np.argsort(data, kind="quicksort")
実行結果
1.15 ms ± 16.6 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)%%timeit
import numpy as np
np.argsort(data, kind="mergesort")
実行結果
1.18 ms ± 24.5 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)%%timeit
import numpy as np
np.argsort(data, kind="heapsort")
実行結果
1.65 ms ± 35.9 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)%%timeit
import numpy as np
np.argsort(data, kind="stable")
実行結果
1.22 ms ± 27.1 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)重複のないランダムな数値の場合は「quicksort」と「mergesort」、「stable」が大体1ミリ秒程度、「heapsort」が1.65ミリ秒という結果になりました。
重複のあるランダムな数値のリストの場合
最後に重複のあるランダムな数値のリストの場合です。
0から1000までの数値の中からランダムに数値を抽出し、10000個の数値をもつリストを作成しました。
import numpy as np
rng = np.random.default_rng()
data = rng.integers(0, 1000, 10000)同じリストに対して、それぞれのソート方法を計測してみます。
%%timeit
import numpy as np
np.argsort(data, kind="quicksort")
実行結果
535 µs ± 10.5 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)%%timeit
import numpy as np
np.argsort(data, kind="mergesort")
実行結果
592 µs ± 4.64 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)%%timeit
import numpy as np
np.argsort(data, kind="heapsort")
実行結果
1.04 ms ± 22.6 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)%%timeit
import numpy as np
np.argsort(data, kind="stable")
実行結果
619 µs ± 13.7 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)この場合は「quicksort」が535μ秒、続いて「mergesort」と「stable」が600μ秒程度、最後に「heapsort」で1ミリ秒という結果になりました。
まとめてみるとソートしたいリストが綺麗に並んでいることはごくまれだと思いますので、やはりランダムな数値のリストの結果を重視すべきだと思います。
そうなるとどちらも「quicksort」が「mergesort」や「stable」よりもわずかではありますが処理時間が短かったので、とりあえず「quicksort」を選んでおけば良いのかなと思います。
むしろデフォルトが「quicksort」なので、特に指定をする必要はないことになります。
ただ昇順でも降順でもすでにソートされている場合は「mergesort」や「stable」の方が速いので、その様な可能性がある場合は「mergesort」を選ぶといいかもしれません。
次回はアルファベットのリストを作成する方法を紹介します。
ではでは今回はこんな感じで。
コメント