4

私はチェスエンジンを作っています。私のピースの正方形のテーブルには、リストや辞書を使用できます。ピーススクエアテーブルの実装によりエンジンが2倍遅くなったため、間違ったデータ構造を使用していないかと思いました。私はリストを使用していますが、辞書がより良いアイデアであるかどうか疑問に思っていますか？

リストの例：

list_ex = [50, 30, 30, 30
           20, 30, 50, 40]
call = list_ex[2]

辞書の例：

dict_ex = {0: 50, 1: 30, 2: 30, 3: 30,
           4: 20, 5: 30, 6: 50, 7: 40}
call = dict_ex[2]

ご覧のとおり、私は常にインデックスを知っています。そのインデックスに関連付けられている値を返す必要があります。これ、辞書、またはリストのどちらのデータ構造が高速でしょうか？

4

4 に答える 4

6

TimeComplexityのpython wiki でわかるようにlist、dictO(1) のアイテムを取得する際の平均的なケースでは、どちらも同じ複雑さを持っています。したがって、単純なインデックス ベースのルックアップではそれほど大きな違いはないはずです。

編集: 最初の要素、中央から 1 つ、最後の要素を取得する小さなベンチマーク コードを書きました。リストがわずかに進んでいることがわかります (ただし、コードが 1000000 回実行されることを考えると、0.01 秒の偏差はそれほど大きくありません)。

要約すると、私があなたの状況にあった場合、リストを使用します。これは、インデックス ベースのリクエストの問題にも適しているためです。

>>> from timeit import Timer
>>> t=Timer("(l[0], l[3], l[7])","l=[50, 30, 30, 30, 20, 30, 50, 40]")
>>> sorted(t.repeat(5))
[0.17861513267149576, 0.17863279532627985, 0.17883092423682, 0.17892576501373014, 0.18901037296996037]
>>> t=Timer("(l[0], l[3], l[7])","l={0: 50, 1: 30, 2: 30, 3: 30, 4: 20, 5: 30, 6: 50, 7: 40}")
>>> sorted(t.repeat(5))
[0.18541179903735383, 0.1855488765975224, 0.1855757545505412, 0.18578041096390052, 0.21753940019925722]
于 2012-10-09T06:18:00.177 に答える