在带有200万项的列表中搜索项目 - Python

Question

我有一个包含190万到200万条字符串的列表。

下面这段代码：

items = [...]
item_in_list = items[-1] in items

运行0.1秒

而用sqlite3运行则需要0.7秒

---

现在问题是我需要进行这个检查1百万次，我希望能在几分钟内完成，而不是几天。

更具体来说，我是想把一个CSV文件的内容和数据库里计算出来的值进行同步。

---

有没有什么好主意？那就太好了 :)

Answer 1

你有两百万个字符串需要和另外一百万个字符串进行匹配吗？

可以尝试以下几种方法：

1. 用集合（set）来代替列表（list）来存储这两百万个字符串。
2. 如果这样做还是没有加快速度，可以试试把这些字符串放到字典（dictionary）里当作键。
3. 如果还是不行，那就找一个好的二叉树实现来用。

更新：

正如评论中提到的，集合和字典并不是用二叉树实现的，而是用哈希表。这种方式应该比列表更快，实际上可能还会比二分查找更快。

Answer 2

对于这样的搜索，我会选择二分查找。这是一种在很长的已排序列表中非常快速的方法。如果列表没有排序，那就不要使用二分查找。

Answer 3

把两个集合放进不可变集合（frozensets）里。

这里有个小的性能测试：

import random
from timeit import Timer

def random_strings(size):
    alpha = 'abcdefghijklmnopqrstuvwxyz'
    min = 3
    max = 8
    strings = []
    for count in xrange(1, size):
        current = ''
        for x in random.sample(alpha, random.randint(min,max)):
            current += x  
        strings.append(current)
    return strings

string_list_1 = random_strings(10000)
string_list_2 = random_strings(10000)

def string_test():
    common = filter(lambda x: x in string_list_2, string_list_1)
    return common

def set_test():
    string_set_1 = frozenset(string_list_1)
    string_set_2 = frozenset(string_list_2)
    common = string_set_1 & string_set_2
    return common

string_timer = Timer("__main__.string_test()", "import __main__")
set_timer = Timer("__main__.set_test()", "import __main__")
print string_timer.timeit(10)
# 22.6108954005
print set_timer.timeit(10)
#  0.0226439453

你可以看到，集合的速度快得多，性能应该也比字典好。

需要特别注意的是，我计算了创建这些集合所需的时间。这部分时间会影响你的性能，不过如果你只有一个集合明显比另一个小很多的话，整体上你还是会有很大的提升。