Pythonで作るn次元n目並べ その2:1次元n目並べ速度計測

Share on:

前回作った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で作っていこうと思います。

リスト版ソースコード

 1import random
 2import time
 3
 4def choice_index_randomly(arr):
 5    indexes = [ i for i, d in enumerate(arr) if d==0 ]
 6    return random.choice(indexes)
 7
 8def is_win(arr, index, connect_length):
 9    s = index - connect_length + 1
10    if s < 0:
11        s = 0
12    e = index + connect_length + 1
13    if e > len(arr):
14        e = len(arr)
15    str1 = ''.join( [str(i) for i in arr[s:e]] )
16    str2 = ''.join( [str(arr[index]) for i in range(connect_length)] )
17    if str2 in str1:
18        return True
19    return False
20
21def output_text(ls):
22    text = '\n'.join( ['\t'.join([str(k) for k in j]) for j in ls] )
23    with open('output.txt', mode='w') as f:
24        f.write(text)
25
26def main():
27
28    field_size = 100000
29    connect_length = 5000
30
31    # create field
32    arr = [ 0 for i in range(field_size) ]
33
34    ls = [['turn', 'player', 'put', 'time']]
35
36    # put pieces randomly
37    for i in range(30):
38
39        # player 1
40        index = choice_index_randomly(arr)
41        arr[index] = 1
42
43        start_time = time.time()
44        frag = is_win(arr, index, connect_length)
45        end_time = time.time()
46        t = end_time-start_time
47        ls.append([i, 1, index, t])
48
49        if frag:
50            print('player 1 is won!!!')
51            output_text(ls)
52            return
53
54        # player 2
55        index = choice_index_randomly(arr)
56        arr[index] = 2
57
58        start_time = time.time()
59        frag = is_win(arr, index, connect_length)
60        end_time = time.time()
61        t = end_time-start_time
62        ls.append([i, 2, index, t])
63
64        if frag:
65            print('player 2 is won!!!')
66            output_text(ls)
67            return
68    output_text(ls)
69
70if __name__ == '__main__':
71    main()

NumPy版ソースコード

 1import numpy as np
 2import random
 3import time
 4
 5def choice_index_randomly(arr):
 6    indexes = np.where(arr==0)[0]
 7    return np.random.choice(indexes)
 8
 9def is_win(arr, index, connect_length):
10    change = (arr[1:]==arr[:-1])
11
12    left = np.arange(len(change))
13    left[change>0] = 0
14    np.maximum.accumulate(left, out=left)
15
16    right = np.arange(len(change))
17    right[change[::-1]>0]=0
18    np.maximum.accumulate(right, out=right)
19    right = len(change) - right[::-1] - 1
20
21    result = np.zeros_like(arr)
22    result[:-1] += right
23    result[1:] -= left
24    result[-1] = 0
25
26    return np.max(result[arr == arr[index]]) >= connect_length
27
28def output_text(ls):
29    text = '\n'.join( ['\t'.join([str(k) for k in j]) for j in ls] )
30    with open('output.txt', mode='w') as f:
31        f.write(text)
32
33def main():
34
35    players = range(1,3)
36    field_size = 100000
37    connect_length = 5000
38
39    # create field
40    arr = np.zeros(field_size, int)
41
42    ls = [['turn', 'player', 'put', 'time']]
43
44    for i in range(30):
45
46        for player in players:
47            index = choice_index_randomly(arr)
48            arr[index] = player
49
50            start_time = time.time()
51            frag = is_win(arr, index, connect_length)
52            end_time = time.time()
53            t = end_time-start_time
54            ls.append([i, player, index, t])
55
56            if frag:
57                print('player', player, 'is won!!!')
58                output_text(ls)
59                return
60    output_text(ls)
61
62if __name__ == '__main__':
63    main()

関連記事