AtCoderのPython3はnumpyを使うことができる。その高速化テクニックをまとめる。
時間計測はAtCoderのコードテストを使用。
※追記中
〇基本的な考え方
〇二分探索
N=10**6
大きさNのリストでN回二分探索をする。計算量O(NlogN)。
numpyなし：bisectを使用
numpyあり：numpy.searchsortedを使用
import time
import bisect
import numpy as np
n=10**6
a=list(range(n))
b=list(range(n))
c=np.array(range(n),dtype="int64")
d=np.array(range(n),dtype="int64")
t1=time.time()
for i in range(n):
j=bisect.bisect_left(a,b[i])
t2=time.time()
print(t2-t1)
t3=time.time()
js=np.searchsorted(c,d)
t4=time.time()
print(t4-t3)
結果
numpyなし：約0.6s弱
numpyあり：約0.08s
大幅な高速化に成功。
＜例題＞
C - 億マス計算
D - Pairs
〇条件を満たす値を調べる
N=10**6
大きさNのリストのすべての要素に対し、ある値xとの大小関係を調べる。計算量O(N)。
numpyなし1：for文を回して1つずつ比較
numpyなし2：リスト内包表記を使用
numpyあり：b[b>x]を使用
import time
import numpy as np
n=10**6
a=list(range(n))
b=np.array(range(n),dtype="int64")
x=100
t1=time.time()
cnt=0
for i in range(len(a)):
if a[i]>x:
cnt+=1
print(cnt)
t2=time.time()
print(t2-t1)
t3=time.time()
print(len([a[i] for i in range(n) if a[i]>x]))
t4=time.time()
print(t4-t3)
t5=time.time()
print(len(b[b>x]))
t6=time.time()
print(t6-t5)
結果
numpyなし1：約0.18s
numpyなし2：約0.12s
numpyあり：約0.005s
大幅な高速化に成功。
＜例題＞
D - Pairs
〇累積和
N=10**6
大きさNのリストの累積和を求める。計算量O(N)。
numpyなし：itertoolsのaccumulateを使用
numpyあり：cumsumを使用
import time
from itertools import accumulate
import numpy as np
n=10**6
a=list(range(n))
b=np.array(range(n),dtype="int64")
t1=time.time()
s1=list(accumulate(a))
t2=time.time()
print(t2-t1)
t3=time.time()
s2=b.cumsum()
t4=time.time()
print(t4-t3)
結果
numpyなし：約0.04s
numpyあり：約0.004s
それなりに速くなる。
＜例題＞
D - AtCoder Express 2
〇総和
N=10**6
大きさNのリストの総和を求める。計算量O(N)。
numpyなし：sum(a)を使用
numpyあり：b.sum()を使用
import time
import numpy as np
a=list(range(10**6))
b=np.array(range(10**6),dtype="int64")
t1=time.time()
print(sum(a))
t2=time.time()
t3=time.time()
print(b.sum())
t4=time.time()
print(t2-t1)
print(t4-t3)
結果
numpyなし：約0.007s
numpyあり：約0.001s
それほど変化なし。
＜例題＞
D - AtCoder Express 2
〇最大最小
N=10**6
大きさNのリストの最大値（最小値）を求める。計算量O(N)。
numpyなし：max(a)を使用
numpyあり：b.max()を使用
import time
import numpy as np
a=list(range(10**6))
b=np.array(range(10**6),dtype="int64")
t1=time.time()
print(max(a))
t2=time.time()
t3=time.time()
print(b.max())
t4=time.time()
print(t2-t1)
print(t4-t3)
結果
numpyなし：約0.018s
numpyあり：約0.0012s
それなりに速くなる。
※注意
for文の繰り返し回数が多く、min(max)を使用する回数が多いが、配列の大きさは小さいという場合にはnumpyのmin(max)とリストのmin(max)の速度が逆転することが分かった。つまり、numpyのmin(max)を繰り返し使用するときには遅くなる可能性がある。
import time
import numpy as np
def main():
a=np.array(range(10**5),dtype=np.int64)
b=list(range(10**5))
c=np.array(range(10**2),dtype=np.int64)
d=list(range(10**2))
t1=time.time()
for i in range(10**2):
x=a.min()
t2=time.time()
t3=time.time()
for i in range(10**2):
x=min(b)
t4=time.time()
t5=time.time()
for i in range(10**5):
x=c.min()
t6=time.time()
t7=time.time()
for i in range(10**5):
x=min(d)
t8=time.time()
print(t2-t1)
print(t4-t3)
print(t6-t5)
print(t8-t7)
if __name__=="__main__":
main()
結果
〇for文少、配列大の場合
numpyあり：約0.01s
numpyなし：約0.16s
〇for文多、配列小の場合
numpyあり：約0.5s
numpyなし：約0.17s
〇2つの配列の要素を比較し、大きい方（小さい方）を選んでいく
N=10**6
numpyなし1：for文を回して1つずつ比較
numpyなし2：リスト内包表記を使用
numpyあり：numpy.maximumを使用
import time
import numpy as np
n=10**6
x=100
a1=list(range(n))
a2=list(range(n))
b1=[x]*n
b2=[x]*n
c=np.array(range(n),dtype="int64")
d=np.full(n,x,dtype="int64")
t1=time.time()
for i in range(n):
if a1[i]<b1[i]:
a1[i]=b1[i]
t2=time.time()
t3=time.time()
a2=[b2[i] if a2[i]<b2[i] else a2[i] for i in range(n)]
t4=time.time()
t5=time.time()
c=np.maximum(c,d)
t6=time.time()
print(t2-t1)
print(t4-t3)
print(t6-t5)
結果
numpyなし1：約0.13s
numpyなし2：約0.14s
numpyあり：約0.003s
大幅な高速化に成功。一般にリスト内包表記の方が速いと言われるが、今回はリスト内包表記の方がなぜか遅い。
＜例題＞
D - Knapsack 1
