字典检索和列表索引哪个更快？

Question

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

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

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

Answer 1

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

这是一些timeit比较列表与字典的访问速度的代码。它还显示集合对象本身消耗的 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范围对象检索整数所需的时间与执行列表和字典访问所需的时间大致相同。您可以通过向字典中添加如下条目来衡量这一点commands：

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

Answer 2

好吧，从字典中检索与从列表中检索具有相同的复杂性：

_dict[1]
_list[1]

但是......，使用字典，你可以使用：

_dict.get(1, 'something else')

如果没有 key ，它只会返回“其他内容” 1。使用列表，你无法做到这一点。您只想获取按 number 索引的项目1。如果您要求列表之外的项目，那么索引将高于您的列表长度，那么您的程序将提出IndexError必须处理的问题。下一个问题是您必须知道该列表的大小，因此您需要先检查它。