質問
競技プログラミングの問題を解いていてリストを使うとTLE(制限時間切れ)になるものがセットを使うと楽々通ってしまうことがあり、それぞれの実行時間を調べてみました。
空のリスト、セットに10^5個の数字を追加していくだけだと両者に差はないのですが(コード1)、そこに配列から除く操作を加えると50倍近い時間差が生まれました(コード2)。
リストとセットのデータ構造の違いに由来するだろうかと思っているのですが、セットの仕組みを具体的に説明している情報が見当たりません。
どなたか詳しく教えていただけないでしょうか?
コード1
Python
1%%timeit 2a = [] 3for i in range(10 ** 5): 4 a += [i] 5 6> 9.8 ms ± 194 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 7 8%%timeit 9a = set() 10for i in range(10 ** 5): 11 a.add(i) 12> 9.28 ms ± 184 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
コード2
Python
1%%timeit 2a = [] 3for i in range(10 ** 5): 4 a += [i] 5for i in range(10 ** 5): 6 a.remove(i) 7> 965 ms ± 19.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 8 9%%timeit 10a = set() 11for i in range(10 ** 5): 12 a.add(i) 13for i in range(10 ** 5): 14 a.remove(i) 15> 18.7 ms ± 1.24 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
回答2件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。