Pythonで作るn次元n目並べ その2:1次元n目並べ速度計測
2020/03/08 categories:Python| tags:Python|
前回作った1次元n目並べをNumPyに書き換えて速度比較してみました。
条件
盤面のサイズやn目並べのnが小さいと計算時間がほぼ0になってしまうので、n目並べの盤面の大きさは1,000,000で5,000個連続した場合勝ちという条件で実行して、盤面をリストで作った場合とNumPyで作った場合の勝ち判定の処理で比較しました。計測回数は先攻後攻を30ターンで計60回です。
結果
List| | | | NumPy | | |
turn| player| put | time | turn | player | put | time
0 | 1| 89854 | 0.005984 | 0 | 1 | 791 | 0.003990
0 | 2| 69833 | 0.003989 | 0 | 2 | 75395 | 0.001995
1 | 1| 3732 | 0.004986 | 1 | 1 | 66728 | 0.002993
1 | 2| 58347 | 0.003989 | 1 | 2 | 71069 | 0.001997
| | … | | | | … |
28 | 1| 61684 | 0.004987 | 28 | 1 | 14086 | 0.001995
28 | 2| 52860 | 0.003991 | 28 | 2 | 14478 | 0.001994
29 | 1| 20981 | 0.003989 | 29 | 1 | 84475 | 0.001995
29 | 2| 63148 | 0.004987 | 29 | 2 | 14659 | 0.001995
| List| NumPy
max| 0.005984| 0.003990
min| 0.003988| 0.001994
range| 0.001996| 0.001996
average| 0.004339| 0.002361 3σ| 0.001540| 0.001555
所感
NumPyは使ったことがほとんどありませんでした。使ってみた感じは、速度は速いし、便利なメソッドがたくさんあり、多次元化するときにも有利かもしれません。次回からはNumPyで作っていこうと思います。
リスト版ソースコード
import random
import time
def choice_index_randomly(arr):
indexes = [ i for i, d in enumerate(arr) if d==0 ]
return random.choice(indexes)
def is_win(arr, index, connect_length):
s = index - connect_length + 1
if s < 0:
s = 0
e = index + connect_length + 1
if e > len(arr):
e = len(arr)
str1 = ''.join( [str(i) for i in arr[s:e]] )
str2 = ''.join( [str(arr[index]) for i in range(connect_length)] )
if str2 in str1:
return True
return False
def output_text(ls):
text = '\n'.join( ['\t'.join([str(k) for k in j]) for j in ls] )
with open('output.txt', mode='w') as f:
f.write(text)
def main():
field_size = 100000
connect_length = 5000
# create field
arr = [ 0 for i in range(field_size) ]
ls = [['turn', 'player', 'put', 'time']]
# put pieces randomly
for i in range(30):
# player 1
index = choice_index_randomly(arr)
arr[index] = 1
start_time = time.time()
frag = is_win(arr, index, connect_length)
end_time = time.time()
t = end_time-start_time
ls.append([i, 1, index, t])
if frag:
print('player 1 is won!!!')
output_text(ls)
return
# player 2
index = choice_index_randomly(arr)
arr[index] = 2
start_time = time.time()
frag = is_win(arr, index, connect_length)
end_time = time.time()
t = end_time-start_time
ls.append([i, 2, index, t])
if frag:
print('player 2 is won!!!')
output_text(ls)
return
output_text(ls)
if __name__ == '__main__':
main()NumPy版ソースコード
import numpy as np
import random
import time
def choice_index_randomly(arr):
indexes = np.where(arr==0)[0]
return np.random.choice(indexes)
def is_win(arr, index, connect_length):
change = (arr[1:]==arr[:-1])
left = np.arange(len(change))
left[change>0] = 0
np.maximum.accumulate(left, out=left)
right = np.arange(len(change))
right[change[::-1]>0]=0
np.maximum.accumulate(right, out=right)
right = len(change) - right[::-1] - 1
result = np.zeros_like(arr)
result[:-1] += right
result[1:] -= left
result[-1] = 0
return np.max(result[arr == arr[index]]) >= connect_length
def output_text(ls):
text = '\n'.join( ['\t'.join([str(k) for k in j]) for j in ls] )
with open('output.txt', mode='w') as f:
f.write(text)
def main():
players = range(1,3)
field_size = 100000
connect_length = 5000
# create field
arr = np.zeros(field_size, int)
ls = [['turn', 'player', 'put', 'time']]
for i in range(30):
for player in players:
index = choice_index_randomly(arr)
arr[index] = player
start_time = time.time()
frag = is_win(arr, index, connect_length)
end_time = time.time()
t = end_time-start_time
ls.append([i, player, index, t])
if frag:
print('player', player, 'is won!!!')
output_text(ls)
return
output_text(ls)
if __name__ == '__main__':
main()
