AtCoder ABC155 問題D Pairs 検討メモ2 NumPyとPython

#概要

AtCoder ABC155 問題D Pairsに関してメモ。

PythonとNumPyの速度を「ソート」と「二分法」について測定してみた。実施前はどちらの処理もNumPyの圧勝を予想していた。ソートはNumPyが10倍程度速い。二分法は多数の閾値をリストとして与える場合はNumPyが速いが、一つの閾値について関数を呼び出す場合はNumPyよりもPythonが速いことを示す結果が得られた。結構意外だ。

#経緯
AtCoder ABC155 問題D Pairs 検討メモ1の続き。この問題でTLEから抜け出せなかったのはPythonの速度がNumPyに較べて遅いことが理由の様であることが観察された。そこでPythonとNumPyを比較するテスト用プログラムを書いてみて、速度を測定した。

結果

（測定に使用したプログラムは一番下にある）

ソート
List(Python)とArray(NumPy)のサイズを1024から1048576まで変えた時にsorted(Python)とnumpy.sort(NumPy)の実行時間を比較してみた。グラフの縦軸は実行時間（秒）、横軸はListもしくはのArrayサイズ。

それぞれの測定は16回試行を実施していて、グラフには平均、最大、最小の経過時間を示している。
LIST：Python sorted()
ARRAY: NumPy numpy.sort()
結果よりArray(NumPy)の処理方がList(Python)の処理にくらべてほぼ10倍速いことが分かる。

二分法

List(Python)とArray(NumPy)のサイズを1024から1048576まで変えた時にbisect.bisect_left(Python)とnumpy.searchsorted(NumPy)の実行時間を比較してみた。グラフの縦軸は実行時間（秒）、横軸はListもしくはのArrayサイズ。この関数は同じサイズの問題だと、ソートよりもはるかに短時間で終了して測定制度に問題があるので1.for文で1024回呼び出すかもしくは2.閾値を1024回分LISTで与える事により1試行あたり1024回の二分法を繰り返すかした時の実施時間をプロットしている。

LIST：Python bisect.bisect_left() for文で1024回呼び出し
ARRAY: NumPy numpy.searchsorted() for文で1024回呼び出し
ARRAY2: NumPy numpy.searchsorted() 第二引数にサイズ1024のリストを渡して一回呼出し

それぞれの測定は16回試行を実施していて、グラフには平均、最大、最小の経過時間を示している。Arrayとしているものはfor文を使用して一試行あたりnumpy.searchsorted()を1024回呼び出している。Array2としているものはnumpy.searchsorted()の第二引数にサイズ1024のリストを与えることにより試行一回あたり同じ処理を実施している。

結果よりArray2(NumPy)、List(Python)、Array(NumPy)、の順で性能がよい。サイズが大きくなるに従い性能差は縮む傾向にある。しかしサイズ1048576でもArray2(NumPy)は他のものに較べて性能が数倍よい。第二引数にリストを使用しないときPython bisect.bisect_left()がNumPy numpy.searchsorted()より性能が良い様子であるのは少し意外であった。

#感想
この速度差からするとAtCoder ABC155 問題D Pairsで自分のプログラムがTLEできなかったのはNumPyを使用してなかったのが原因と推察される。いろいろ覚えないといけないこと多いな。練習のため同じ問題でC++のテストも機会あればやってみたい。

#Appedix
テストに使用したプログラム

random.bisect.py

import math
import sys
import numpy as np
import random
import time
import bisect

args = sys.argv
stdin = sys.stdin
rangeMax = 2 ** 60
n_bisect_try = 1024
target = [random.randrange(0,rangeMax) for _ in range(n_bisect_try)]

print(rangeMax) 
N = int(args[1])

def start_time():
    global start
    start = time.time()

def end_time(header="Elapsed time: "):
    global start
    elapsed_time = time.time() - start
    print("{0}{1:0.7f}".format(header,elapsed_time))
    return elapsed_time

start_time()
s = [ random.randrange(0,rangeMax) for _ in range(N)]
end_time('Time Generate Random List: ')
# print(s)    

start_time()
sn = np.array(s)
end_time('Time Make Array: ')


start_time()
s_sort = sorted(s)
end_time("Time List Sort: ")
#print(s,s_sort)

start_time()
for t in target:
    i  = bisect.bisect_left(s_sort,t)
    #print("Result List Bisect:", i)
end_time("Time List Bisect: ")

start_time()
sn_sort = np.sort(sn)
end_time("Time Array Sort: ")
# print(sn,sn_sort)

start_time()
for t in target:
    i  = np.searchsorted(sn_sort,t)
    # print("Result List Bisect:", i)
end_time("Time Array Bisect: ")

start_time()
i_array  = np.searchsorted(sn_sort,target)
#print("Result List Bisect2:", i_array)
end_time("Time Array Bisect2: ")