AtCoder ABC019D - Make Them Evenという問題を解いていて疑問に思ったことがあります。
今回、問題そのもののロジックは関係ありません。
この問題では複数の答えをまとめて出力することが求められるので、ansというリストを作り、そこにそれぞれの条件での答えを入れていくことにしました。
4つの数値でひとつの答えを成すので、はじめ私は ans += [(a, b, c, d)]
としてタプルにまとめた形でリストに追加しました。(コード1)
ですが、他の方の解答にはstr.format()を用いた高速なものがありました。
ロジック部分を変えずに、ansへの追加方法のみをans += ["{} {} {} {}".format(a, b, c, d)]
に変えたものがコード2です。
最も処理が重かったケースでそれぞれ、464msと301msかかりました。
これだけならば単なる高速化テクニックの1つに過ぎないのですが、自分で検証したところ、その速度差が再現できませんでした。
むしろ、str.formatのほうが圧倒的に遅いくらいです。(コード3)
どなたか再現ができなかった理由、あるいは一般にはリストの要素としてどちらが早いものなのか教えていただけないでしょうか?
コード1
Python
1# ABC109D - Make Them Even (tuple style) 2def main(): 3 H, W = tuple(map(int, input().split())) 4 A = list(list(map(lambda x: int(x) % 2, input().split())) for _ in range(H)) 5 ans = [] 6 for i in range(H): # move left to right 7 for j in range(W - 1): 8 if A[i][j]: 9 A[i][j] ^= 1 10 A[i][j + 1] ^= 1 11 ans += [(i + 1, j + 1, i + 1, j + 2)] 12 13 for i in range(H - 1): # move up to down 14 if A[i][W - 1]: 15 A[i][W - 1] ^= 1 16 A[i + 1][W - 1] ^= 1 17 ans += [(i + 1, W, i + 2, W)] 18 print(len(ans)) 19 for i in ans: 20 print(*i) 21 22 23if __name__ == "__main__": 24 main()
コード2
Python
1# ABC109D - Make Them Even (str-format style) 2def main(): 3 H, W = tuple(map(int, input().split())) 4 A = list(list(map(lambda x: int(x) % 2, input().split())) for _ in range(H)) 5 ans = [] 6 for i in range(H): # move left to right 7 for j in range(W - 1): 8 if A[i][j]: 9 A[i][j] ^= 1 10 A[i][j + 1] ^= 1 11 ans += ["{} {} {} {}".format(i + 1, j + 1, i + 1, j + 2)] 12 13 for i in range(H - 1): # move up to down 14 if A[i][W - 1]: 15 A[i][W - 1] ^= 1 16 A[i + 1][W - 1] ^= 1 17 ans += ["{} {} {} {}".format(i + 1, W, i + 2, W)] 18 print(len(ans)) 19 for i in ans: 20 print(*i) 21 22 23if __name__ == "__main__": 24 main()
コード3
Python
1# 実験用コードまとめ 2%%timeit 3A = [] 4for _ in range(10 ** 6): 5 A += [(1, 1, 1, 1)] 6for i in A: 7 i 8# 94.6 ms ± 4.9 ms per loop (mean ± std. dev. of 7 runs, 10 loops each) 9 10%%timeit 11A = [] 12for _ in range(10 ** 6): 13 i = 1 14 A += [(i, i, i, i)] 15for i in A: 16 i 17# 167 ms ± 10.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 18 19%%timeit 20A = [] 21for _ in range(10 ** 6): 22 A += ["{} {} {} {}".format(1, 1, 1, 1)] 23for i in A: 24 i 25# 575 ms ± 5.66 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 26 27%%timeit 28A = [] 29for _ in range(10 ** 6): 30 i = 1 31 A += ["{} {} {} {}".format(i, i, i, i)] 32for i in A: 33 i 34# 595 ms ± 8.37 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
回答2件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
退会済みユーザー
2019/08/13 19:29 編集
2019/08/13 19:29
退会済みユーザー
2019/08/13 19:29