如何高效地搜索数百万次列表？

Question

我知道一个简单的搜索方法是使用包含字符串的列表，然后只需执行if string in list，但速度会变慢，我听说字典键在处理大量数据时几乎没有减速，因为它们没有顺序。

然而，我不需要与项目相关的任何其他信息，所以仅仅为了保存键并将值设置为None感觉有点不合适。

有没有一种像字典键一样速度快，但像列表一样的东西可以使用？

以下是一个快速的示例：

import time, random

totalRange = 100000
searchFor = 5000

#Create a list of 10 million characters
searchableList = []
for i in range( totalRange ):
    searchableList.append( random.randint( 0, totalRange ) )

#Create dictonary with keys set to 'None'
searchableDict = {}
for i in searchableList:
    searchableDict[i] = None

searchableSet = set( searchableList )

#Search list
startTime = time.time()
numberMatches = 0
for number in range( searchFor ):
    if number in searchableList:
        numberMatches += 1
print numberMatches, time.time()-startTime

#Search dictionary keys
startTime = time.time()
numberMatches = 0
for number in range( searchFor ):
    if number in searchableDict:
        numberMatches += 1
print numberMatches, time.time()-startTime

#Search set
startTime = time.time()
numberMatches = 0
for number in range( searchFor ):
    if number in searchableSet:
        numberMatches += 1
print numberMatches, time.time()-startTime

以下是时间输出：

List: 18.8 seconds
Set: 0.002 seconds
Dictionary: 0.0009 seconds

尽管集合比列表快得多，但字典仍然快了一倍，所以我想知道是否还有其他我不知道的东西。使用字典也不会太糟糕，我只是想象有比 dictionary[key]=None 更清晰的方法。

基于iCodez的答案进行编辑：

当totalRange=1000000和searchFor=50000（高10倍）时的测试结果：

List = 20 minutes and still going
Dictionary = 0.023 seconds
Set = 0.02 seconds
Set.intersection = 0.008 seconds

更多计算后，似乎集合和字典的效率非常相似，但是使用 set.intersection 的方法明显更好。

- Peter

---

最干净、最清晰、最明显的方法是使用集合。不幸的是，你目前的实现似乎对此有一点点惩罚，但这真的不像是需要太过担心的事情。如果你可以容忍一点模糊性，布隆过滤器可能是一个很好的选择。 - Lee Daniel Crocker

使用集合。你们的时间差可以忽略不计，而且从概念上讲，这是正确的数据结构。 - Zero Piraeus

.002和.0009的差别太小，很难确定哪个更快。这是在使用类似于计时器的工具时所能容许的误差范围之内。 - Falmarri

你应该使用 timeit 模块来测量这样的小时间... - Joran Beasley

就我所知，我刚做的一些时间测试表明集合稍微快了一点。但是如果以速度为代价（换取内存），使用Joran建议的set.intersection应该会更快。 - DSM

Answer 1

在这种情况下，您应该使用一个set。集合与字典具有相同的查找时间（常量），但它们由单个项而不是键/值对组成。因此，您可以以更少的内存获得相同的速度和更好的数据表示。

---

此外，您可以使用 set.intersection 来替代 for 循环，以提高效率：

numberMatches = len(searchableSet.intersection(xrange(searchFor)))

你也会注意到我用 xrange 替换了 range。这样做可以避免 Python 构建不必要的列表，从而浪费内存。

- user2555451

---

它们具有相同的渐近查找时间，是的，但 OP 的计时表明，由于某种原因，对于他的数据，字典查找速度更快。 - senshin

由于他正在使用 set.intersection 计算交集的数量，这可能会更快。 - Joran Beasley

谢谢，不过你有没有想过为什么在我的例子中设置set不是很有效率？增量只是为了确保结果准确而做的临时处理，但set.intersection看起来非常有用，我之前也不确定如何使用xrange，现在也有所帮助 :) - Peter

它显然会受到您的CPU和其他各种硬件因素的影响... - Joran Beasley

@Peter - set.intersection 是用 C 写的，所以 Python 只需查找名称，剩下的工作由 C 完成。然而，您的代码让 Python 完成了大部分工作，这几乎总是会更慢。此外，range 创建了一个相当大的列表，浪费了时间。 - user2555451

Answer 2

使用

a_dict = dict.fromkeys(my_text.split())

- Joran Beasley

---

谢谢，这比我自己的方法更优雅了。但是它仍然存在一个问题，就是用所有键都赋值为“无”的字典。我的意思是完全避免这种情况，而是使用一个像字典一样快速的列表。 :) - Peter

我并不反对 set 是合适的数据结构...这只是在回答关于更好的 d[key] = None 方法的问题。 - Joran Beasley

我之前不知道也可以这样做，所以这对我来说仍然非常有用。通常我会使用循环来完成所有操作，所以看到更好的方法很不错 :) - Peter