Python：遍历列表 vs 遍历字典项的效率

Question

在CPython中，使用some_dict.items()进行迭代是否和迭代相同项的列表一样高效？

- Jonathan Livni

---

可能不行，但是你可以使用 timeit 进行一些基准测试。 - Hans Then

Answer 1

这取决于你使用的Python版本。在Python 2中，some_dict.items()会创建一个新列表，这需要额外的时间和内存。另一方面，一旦列表被创建，它就是一个列表，因此在列表创建的开销完成后，应该具有相同的性能特征。

在Python 3中，some_dict.items()创建一个视图对象而不是一个列表，我预计创建和迭代items()会比Python 2更快，因为不需要复制任何东西。但我也预计，与已创建的列表相比，迭代已创建的视图会稍微慢一些，因为字典数据存储得有点稀疏，我认为Python没有好的方法来避免迭代字典中的每个bin，即使是空的。

在Python 2中，一些定时确认了我的直觉：

>>> some_dict = dict(zip(xrange(1000), reversed(xrange(1000))))
>>> some_list = zip(xrange(1000), xrange(1000))
>>> %timeit for t in some_list: t
10000 loops, best of 3: 25.6 us per loop
>>> %timeit for t in some_dict.items(): t
10000 loops, best of 3: 57.3 us per loop

使用iteritems速度略快，但遍历items大约慢两倍...

>>> %timeit for t in some_dict.iteritems(): t
10000 loops, best of 3: 41.3 us per loop

但是，遍历列表本身基本上与遍历任何其他列表相同：

>>> some_dict_list = some_dict.items()
>>> %timeit for t in some_dict_list: t
10000 loops, best of 3: 26.1 us per loop

Python 3可以比Python 2更快地创建和迭代items（与上面的57.3微秒相比）：

>>> some_dict = dict(zip(range(1000), reversed(range(1000))))
>>> %timeit for t in some_dict.items(): t      
10000 loops, best of 3: 33.4 us per loop 

但是创建视图的时间可以忽略不计；实际上，迭代速度比列表更慢。

>>> some_list = list(zip(range(1000), reversed(range(1000))))
>>> some_dict_view = some_dict.items()
>>> %timeit for t in some_list: t
10000 loops, best of 3: 18.6 us per loop
>>> %timeit for t in some_dict_view: t
10000 loops, best of 3: 33.3 us per loop

这意味着在Python 3中，如果你想要多次迭代字典中的项，并且性能至关重要，你可以将视图缓存为列表，以获得30%的加速。

>>> some_list = list(some_dict_view)
>>> %timeit for t in some_list: t
100000 loops, best of 3: 18.6 us per loop

- senderle

---

但是，由于未计时的行 some_list = list(some_dict_view)，速度提升有可能被抵消了吗？ - dnk8n

Answer 2

一个小的基准测试表明，迭代列表明显更快。

def iterlist(list_):
    i = 0
    for _ in list_:
        i += 1
    return i

def iterdict(dict_):
    i = 0
    for _ in dict_.iteritems():
        i += 1
    return i

def noiterdict(dict_):
    i = 0
    for _ in dict_.items():
        i += 1
    return i

list_ = range(1000000)
dict_ = dict(zip(range(1000000), range(1000000)))

在 Python 2.7 (Kubuntu) 上使用 IPython 进行测试：

%timeit iterlist(list_)
10 loops, best of 3: 28.5 ms per loop

%timeit iterdict(dict_)
10 loops, best of 3: 39.7 ms per loop

%timeit noiterdict(dict_)
10 loops, best of 3: 86.1 ms per loop

- Wolph

Answer 3

虽然通过迭代 some_list 的速度比 some_dict.items() 快 2 倍，但是通过索引迭代 some_list 几乎与通过键迭代 some_dict 相同。

K = 1000000
some_dict = dict(zip(xrange(K), reversed(xrange(K))))
some_list = zip(xrange(K), xrange(K))
%timeit for t in some_list: t
10 loops, best of 3: 55.7 ms per loop
%timeit for i in xrange(len(some_list)):some_list[i]
10 loops, best of 3: 94 ms per loop
%timeit for key in some_dict: some_dict[key]
10 loops, best of 3: 115 ms per loop
%timeit for i,t in enumerate(some_list): t
10 loops, best of 3: 103 ms per loop

- AaronYin