从列表返回值与从字典返回值

Question

我正在做一个国际象棋引擎，对于我的棋子方桌，我可以使用列表或字典。由于块方表的实现使引擎变慢了两倍，我想知道我是不是使用了错误的数据结构。我正在使用列表，但我想知道字典是不是更好？

列表示例：

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]

如你所见，我总是知道索引，我只需要返回与该索引相关的值。哪种数据结构会更快，字典还是列表？

Answer 1

正如你在TimeComplexity，list和dict上的python wiki中看到的，它们在获取O(1)项的平均情况下都具有相同的复杂度。因此，对于简单的基于索引的查找，应该没有太大的区别。

编辑:我刚刚写了一个小的基准测试代码，它获取第一个元素，一个从中心开始，最后一个。您可以看到一个列表有一个小的提升(尽管考虑到代码运行1000000次时，0.01s的偏差并不是很大)。

总而言之，如果我在你的情况下，我会使用列表，因为它也更适合基于索引的请求的问题。

>>> 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]

Answer 2

就查找速度而言，使用列表比使用字典更好。元组甚至更快一点。

timeit dict_ex[2]
10000000 loops, best of 3: 148 ns per loop

timeit list_ex[2]
10000000 loops, best of 3: 116 ns per loop

tuple_ex=tuple(list_ex)

timeit tuple_ex[2]
10000000 loops, best of 3: 112 ns per loop

Answer 3

您可以很容易地使用timeit模块(python -m timeit -S "setup" -- "statement")对此进行基准测试。但在这种情况下，我可以告诉你，字典不会胜过列表，因为列表查找与字典查找相比是微不足道的。两者都将是快速的，独立于关键字和集合中项目的数量，但list将在微基准测试中获胜。当然，，这不应该决定你的决定。追求清晰，优化算法，而不是无关紧要的细节，过早的优化，等等令人厌恶。

但我仍然认为列表更合适，无论是在语义上(你没有自由形式的映射，你有一个序列)，还是为了防止错误(通过拒绝超出范围和非整数索引)。