4

我正在制作一个国际象棋引擎，对于我的棋盘，我可以使用列表或字典。由于片方表的实现使引擎慢了两倍，我想知道我是否使用了错误的数据结构。我正在使用列表，但想知道字典是否是一个更好的主意？

列表示例：

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 中看到的那样，在获取 O(1) 项目的平均情况下，它们都具有相同的复杂性list。dict因此，简单的基于索引的查找应该没有太大的区别。

编辑：我刚刚编写了一些基准代码，它获取第一个元素，一个来自中心，一个来自最后一个。您会看到一个列表有一个小的进步（尽管考虑到代码运行 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]
于 2012-10-09T06:18:00.177 回答
3

就查找速度而言，您最好使用列表而不是字典。元组甚至更快。

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
于 2012-10-09T06:24:37.537 回答
2

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

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

于 2012-10-09T06:19:46.150 回答
0

对于这样的事情，Python 通常会很慢。

看看this other SO question，第一个答案。

如果您的对象可以是不可变的，我会说您最好的选择是首先使用元组。如果没有，那么坚持使用列表。list无论哪种方式，和之间都不会有太大的区别dict。

我看到halex也刚刚回答，并且似乎同意。

于 2012-10-09T06:19:11.560 回答