从列表与字典返回值

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它们都具有在平均情况下相同的复杂上获得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]