2

假设我有一本字典：

myDict = {
    'title': 'a nice title',
    'nice_list': [1,2,3,4,5,6,6,7,...,99999],
    'nice_lists_last_item': 99999,
}

nice_list如果它大于最终项目，我只想附加一个项目。

什么更快：

  1. 使用：if new_element > nice_list[-1]

或者

  1. 使用：if new_element > nice_lists_last_item

方法 1 是否必须扫描整个列表（和/或nice_list每次都将所有列表放入内存）才能找到该项目？哪个更快？（记住我打算做几十亿次这样的比较？）

方法 2 会将最后一个元素存储为它自己独特的 dict 条目，这样更快吗？

4

3 回答 3

6

如有疑问，请测试：

>>> %timeit if 1 > myDict['nice_list'][-1]: 0
10000000 loops, best of 3: 110 ns per loop
>>> %timeit if 1 > myDict['nice_lists_last_item']: 0
10000000 loops, best of 3: 68.8 ns per loop
>>> nice_list = myDict['nice_list']
>>> %timeit if 1 > nice_list[-1]: 0
10000000 loops, best of 3: 62.6 ns per loop
>>> nice_lists_last_item = myDict['nice_lists_last_item']
>>> %timeit if 1 > nice_lists_last_item: 0                      
10000000 loops, best of 3: 43.4 ns per loop

如您所见，直接访问字典值比从字典中访问列表然后访问其最后一个值要快。但是直接访问列表的最后一个值更快。这应该不足为奇；Python 列表知道自己的长度，并在内存中作为数组实现，因此查找最后一项就像从长度中减去 1 并进行指针运算一样简单。由于碰撞检测的开销，访问字典键有点慢；但它只慢了几纳秒。最后，如果您真的想再节省几纳秒，您可以将最后一个值存储在它自己的值中。

当你同时做这两件事时，最大的减速就出现了。

于 2013-04-24T19:08:05.923 回答
4

如此处所述，从列表中获取项目是 O(1) 。即便如此，显式存储值仍然会更快，因为无论查找速度有多快，它仍然比不进行查找要慢。（但是，如果您明确存储该值，则必须在将新项目添加到列表时对其进行更新；如果更新并检查它的总成本是否超过每次抓取最后一个项目的成本是您必须对自己进行基准测试；这可能取决于您实际添加新项目的频率。）

请注意，不存在“将所有内容nice_list放入内存”的问题。如果您有一个带有列表的字典，则整个列表已经在内存中。在其中查找一个值不会导致它占用更多内存，但是如果您有数十亿个这样的列表，您甚至会在尝试查找任何内容之前耗尽内存，因为仅创建列表就会用完太多的内存。

于 2013-04-24T18:58:31.460 回答
0

在 CPython 中，答案可能是否定的。list 是使用动态数组实现的。

于 2013-04-24T18:58:16.757 回答