查找大列表中是否包含特定字符串的高效方法
我有一个文件，里面大概有所有英语单词（大约6万个单词，50万个字符）。我想测试一下输入的某个单词是否是“英语单词”（也就是说，这个确切的单词是否在列表里）。
在Python中，最有效的方法是什么呢？
最简单的办法就是把文件里的内容加载到一个列表里，然后检查这个单词是否在列表中。这个列表可以进行排序，我觉得这样可以把复杂度降低到O(logn)。不过我不太确定Python是怎么在列表中查找的，如果列表这么大在内存中会不会影响性能。我能不能利用一下单词长度的限制？（比如说最长的单词是15个字符）。
请注意，我是在一台内存很大的机器上运行这个程序，所以我更关心速度和CPU的使用率，而不是内存的消耗。
10 个回答
4
一种叫做Trie的数据结构非常适合你的需求。网上肯定有很多用Python实现的例子可以找到...
6
下面是一个简单的Python代码示例：
L = ['foo', 'bar', 'baz'] # Your list
s = set(L) # Converted to Set
print 'foo' in s # True
print 'blah' in s # False
26
你可以试试Python里的集合（Set）。
集合是一种不按顺序排列的、包含不同元素的对象。它的常见用途包括检查某个元素是否在集合中、从一个序列中去掉重复的元素，以及进行一些数学运算，比如交集、并集、差集和对称差集。