python - 字典检索或列表索引哪个更快？

Question

我正在尝试确定哪种数据结构最适合我的需求。

除了技术细节，我可能会将我的程序的需求转换为使用字典或使用列表，并且由于性能将是一个问题，我想知道什么可能是更快的解决方案。我最终得出结论，检索/索引将是关键操作。

那么在内存使用和速度方面什么更有效？

Answer 1

如果您不需要搜索，请使用列表。它更快，并且比字典使用更少的内存。对于小型集合(<100 项)，速度差异很小，但对于大型集合，dict 会慢 20% 左右。它肯定会使用更多的内存。

这是一些 timeit比较 list 和 dict 访问速度的代码。它还显示了集合对象本身消耗的 RAM(但不是它们持有的数据对象的 RAM)。

#!/usr/bin/env python3

''' Compare list vs dict access speed 

    See http://stackoverflow.com/q/39192442/4014959

    Written by PM 2Ring 2016.08.29
'''

from sys import getsizeof
from timeit import Timer

commands = {'dict' : 'for i in r:d[i]', 'list' : 'for i in r:a[i]'}

def time_test(loops, reps):
    timings = []
    setup = 'from __main__ import r, a, d'
    for name, cmd in commands.items():
        result = Timer(cmd, setup).repeat(reps, loops)
        result.sort()
        timings.append((result, name))

    timings.sort()
    for result, name in timings:
        print(name, result)

    #Find the ratio of slowest / fastest
    tlo, thi = [timings[i][0][0] for i in (0, -1)]
    print('ratio: {0:f}\n'.format(thi / tlo))

num = 2000
r = range(num)
a = list(r)
d = {i:i for i in r}

fmt = 'Sizes: num={}, list={}, dict={}'
print(fmt.format(num, getsizeof(a), getsizeof(d)))

loops, reps = 2000, 3
time_test(loops, reps)

输出

Sizes: num=2000, list=9056, dict=49200
list [1.2624831110006198, 1.3356713940011105, 1.406396518003021]
dict [1.506095960001403, 1.525646976999269, 1.5623748449979757]
ratio: 1.192963

速度差异实际上比那些结果中显示的要高，因为从 r 中检索整数所花费的时间range 对象与执行 list 和 dict 访问所花费的时间大致相同。您可以通过将这样的条目添加到 commands 来衡量这一点。字典:

'none': 'for i in r:i'