Python：列表 vs 字典用于查找表

Question

我有大约1000万个值需要放入某种查找表中，所以我想知道什么更有效率，是使用列表还是字典？

我知道对于两者都可以像这样做：

if something in dict_of_stuff:
    pass

和

if something in list_of_stuff:
    pass

我认为使用字典会更快更有效。

感谢您的帮助。

编辑1
关于我的尝试，提供一些更多信息。 欧拉问题92。我正在制作一个查找表，以查看计算出的值是否已经被计算过。

编辑2
用于查找的效率。

编辑3
该值没有与之相关联的值...那么使用set是否更好？

- Casey

---

效率是指什么？插入？查找？内存消耗？ 您是检查值的纯存在，还是与之相关的任何元数据？ - mthurlin

作为一种附注，对于那个特定的问题，您不需要一个1000万的列表或字典，而是一个更小的。 - sfotiadis

http://www.jessicayung.com/how-python-implements-dictionaries/ - Nirmal

Answer 1

速度

在列表中进行查找的时间复杂度为O(n)，在字典中进行查找的时间复杂度是摊销后的O(1)，与数据结构中的项目数量有关。如果您不需要关联值，请使用集合。

内存

字典和集合都使用哈希，它们使用的内存比仅用于对象存储的内存要多得多。根据A.M. Kuchling在《精美代码》中的说法，实现尝试保持哈希表2/3的满载状态，因此您可能会浪费相当多的内存。

如果您不会动态添加新项（根据您更新的问题），则对列表进行排序并使用二分查找可能是值得的。这是O(log n)的时间复杂度，并且对于字符串来说可能会更慢，在没有自然排序的对象上则无法实现。

- Torsten Marek

---

是的，但如果内容从不改变，那这是一次性的操作。二分查找的时间复杂度为O(log n)。 - Torsten Marek

@John Fouhy：整数并没有存储在哈希表中，只有指针，也就是说，您有40M的整数（当然，如果其中很多都很小，实际上并不是这样），以及60M的哈希表。我同意现在这并不是什么大问题，但还是值得记住的。 - Torsten Marek

这是一个老问题，但我认为针对非常大的集合/字典，“摊销O(1)”可能不成立。根据http://wiki.python.org/moin/TimeComplexity ，最坏情况下时间复杂度为O(n)。我想这取决于内部哈希实现，在什么点上平均时间从O(1)分离开来，开始收敛于O(n)。您可以通过根据某些“容易识别”的属性（例如第一个数字的值，然后是第二个、第三个等，直到获得最佳集合大小）将全局集合分成较小的部分来提高查找性能。 - Nisan.H

这让我感到困惑。从这个页面（https://wiki.python.org/moin/TimeComplexity）可以看出，列表查找的时间复杂度为O(1)，字典查找的时间复杂度为O(n)，这与你所说的相反。我是否有误解？ - temporary_user_name

@Aerovistae，我认为您误读了该页面上的信息。在列表下面，我看到“x in s”（查找）的时间复杂度为O(n)。同时，它也显示集合和字典查找的平均时间复杂度为O(1)。 - Dennis

Answer 2

字典是一种哈希表，因此查找键非常快。因此，在字典和列表之间，字典会更快。但如果您没有要关联的值，则使用集合会更好。它是一个哈希表，没有“表”部分。

---

编辑：针对您的新问题，是的，使用集合会更好。只需创建两个集合，一个用于以1结尾的序列，另一个用于以89结尾的序列。我已成功使用集合解决了这个问题。

- nosklo

---

你甚至不需要集合。只需使用动态规划方法，记录每个数字链是否以1、89或未知结尾。 - qwr

Answer 3

set() 正是你需要的。O(1) 的查找速度，而且比字典更小。

- recursive

Answer 4

我做了一些基准测试，结果表明在运行python 2.7.3和i7 CPU的linux系统上，对于大数据集，字典比列表和集合更快：

• python -mtimeit -s 'd=range(10**7)' '5*10**6 in d'

  执行10次，最好的3次结果：每次64.2毫秒

• python -mtimeit -s 'd=dict.fromkeys(range(10**7))' '5*10**6 in d'

  执行10000000次，最好的3次结果：每次0.0759微秒

• python -mtimeit -s 'from sets import Set; d=Set(range(10**7))' '5*10**6 in d'

  执行1000000次，最好的3次结果：每次0.262微秒

如您所见，相比于列表和集合，字典要快得多，大约比集合快三倍。但是在某些应用中，您可能仍然想选择集合，因为它很美观。而且如果数据集非常小（小于1000个元素），列表的性能表现也很不错。

- EriF89

---

但对我来说，问题是：这些时间实际上在衡量什么？不是给定列表、字典或集合的访问时间，而是更多的时间和循环来_创建_列表、字典、集合，最后找到并访问一个值。那么，这与问题有关吗？...虽然很有趣... - andzep

@andzep，你误解了，-s 选项是为了设置 timeit 环境，即不计入总时间。-s 选项只运行一次。在 Python 3.3 中，我得到了以下结果：生成器（range）-> 0.229 微秒，列表 ->157 毫秒，字典 -> 0.0806 微秒，集合 -> 0.0807 微秒。集合和字典的性能相同。但初始化字典比集合需要更长的时间（总时间分别为13.580秒和11.803秒）。 - sleblanc

为什么不使用内置的set呢？我用sets.Set()得到的结果比使用内置的set()要差很多。 - Thomas Guyot-Sionnest

@ThomasGuyot-Sionnest 内置的 set 已经在 Python 2.4 中引入，所以我不确定为什么我没有在我的解决方案中使用它。使用 Python 3.6.0，我可以通过 python -mtimeit -s "d=set(range(10**7))" "5*10**6 in d" 得到良好的性能（10000000 次循环，最佳结果：每次循环 0.0608 微秒），与字典基准测试差不多，所以感谢您的评论。 - EriF89

相信range函数会生成一个区间对象，而不是列表。 - 0TTT0

Answer 5

你需要一个字典。

在 Python 中，对于（未排序的）列表，“in”操作需要 O(n) 的时间——如果数据量很大的话，这是不好的。而另一方面，字典是一种哈希表，所以您可以期望 O(1) 的查找时间。

正如其他人所指出的那样，如果您只有键而不是键/值对，可以选择使用集合（一种特殊类型的字典）。

相关信息：

• Python 维基：Python 容器操作的时间复杂度信息。
• SO：Python 容器操作的时间和内存复杂度。

- zweiterlinde

---

即使对于已排序的列表，“in”也是O(n)。 - Roger Pate

对于链表来说，是的——但是在Python中，“lists”大多数人会称之为向量，提供O(1)的索引访问和O(log n)的查找操作（当排序时）。 - zweiterlinde

你是说，对于随机值的搜索，应用于已排序列表的in运算符比应用于未排序列表更有效吗？（我认为它们在内部实现为向量还是链表中的节点并不相关。） - martineau

Answer 6

作为一组新的测试，以证明 @EriF89 多年来仍然是正确的：

$ python -m timeit -s "l={k:k for k in xrange(5000)}"    "[i for i in xrange(10000) if i in l]"
1000 loops, best of 3: 1.84 msec per loop
$ python -m timeit -s "l=[k for k in xrange(5000)]"    "[i for i in xrange(10000) if i in l]"
10 loops, best of 3: 573 msec per loop
$ python -m timeit -s "l=tuple([k for k in xrange(5000)])"    "[i for i in xrange(10000) if i in l]"
10 loops, best of 3: 587 msec per loop
$ python -m timeit -s "l=set([k for k in xrange(5000)])"    "[i for i in xrange(10000) if i in l]"
1000 loops, best of 3: 1.88 msec per loop

在这里，我们还比较了元组（tuple）和列表（lists），在某些用例中，元组被认为比列表更快（并且使用更少的内存）。但在查找表的情况下，元组表现并不更好。

字典（dict）和集合（set）的性能都非常好。这带出了一个有趣的观点，与@SilentGhost关于唯一性的答案有关：如果OP在数据集中有1000万个值，并且不知道其中是否存在重复项，则值得将其元素的set/dict与实际数据集并行保留，并在其中测试是否存在。可能这1000万个数据点只有10个唯一值，这是一个更小的搜索空间！

SilentGhost关于字典的错误实际上很有启示性，因为可以使用字典将重复数据（在值中）相关联到一个不重复的集合（键）中，从而保持一个数据对象来保存所有数据，但仍然像查找表一样快速。例如，字典键可以是要查找的值，而值可以是虚拟列表中该值出现的索引列表。

例如，如果要搜索的源数据列表是l=[1,2,3,1,2,1,4]，则可以通过以下字典对其进行优化，以实现搜索和内存的优化：

>>> from collections import defaultdict
>>> d = defaultdict(list)
>>> l=[1,2,3,1,2,1,4]
>>> for i, e in enumerate(l):
...     d[e].append(i)
>>> d
defaultdict(<class 'list'>, {1: [0, 3, 5], 2: [1, 4], 3: [2], 4: [6]})

使用这个字典，可以知道：

1. 值是否在原始数据集中（例如2 in d返回True）
2. 值在原始数据集中的位置（例如d[2]返回数据在原始数据列表中被找到的索引列表：[1, 4]）

- hamx0r

---

对于你最后一段的内容，虽然读起来有意义，但看到你试图解释的实际代码会更好（也可能更容易理解）。 - kaiser

Answer 7

如果数据是唯一的，使用set()会是最有效的方法，但如果有两个值，使用字典也需要保证唯一性（哎呀） :)

- SilentGhost

---

当我看到我的答案发布时，我意识到了。 - SilentGhost

Answer 8

你实际上不需要在表中存储一千万个值，所以无论哪种方式都没什么大问题。

提示：考虑一下第一次平方和操作后结果的大小。最大可能的结果要远小于一千万...

- Kiv