什么是最有效的方法来检查python中的一组数字的存在

Question

因此，我有一个列表中的数字在Python这样的列表中： [1,89,1221,1919,1920,10210,...]与成千上万的数字，我想检查是否我有一个变种。

我做这种方式：

if i in mylist: 

但是，这是最快的方法是什么？

一些进一步的规范：

• 列表中没有保持重复
• 列表仅持有整数
• 列表如果提高性能
• 名单其实可以是一组可订购（所以没有重复）
• 该列表可以是任何种类的集合

Answer 1

转换为集合并做in是最快的方法。

if i in set(mylist): 

一组基本上是一个哈希表，查找是O（1）。

Answer 2

从列表中选择一个集合，相交集合并检查交集的大小？

Answer 3

只有当您在此列表中进行多次查找时，转换为set才值得。如果性能很重要，那么应该从一开始就测量如果使用set（仍然插入元素）的性能比说出列表更好。总之，尝试一些事情和措施。

但是，如果只是由于创建新数据结构的开销，转换为仅用于单个成员资格测试的集合听起来效率低下。

import random 
import timeit 

mylist = list(random.randint(1, 50000) for i in xrange(1000)) 
myset = set(mylist) 

s = "1919 in mylist" 
t = timeit.Timer(s, "from __main__ import mylist") 
print s + ":%.2f usec/pass" % (1000000 * t.timeit(number = 100000)/100000) 

s = "1919 in set(mylist)" 
t = timeit.Timer(s, "from __main__ import mylist") 
print s + ":%.2f usec/pass" % (1000000 * t.timeit(number = 100000)/100000) 

下面是结果：

1919 in mylist:22.81 usec/pass 
1919 in set(mylist):65.42 usec/pass 

Answer 4

一种方法是使用timeit module测试的各种方法。例如，我刮起了下面的代码：

import array 
import bisect 
import random 
import timeit 

mylist = list(random.randint(1, 50000) for i in xrange(1000)) 
myset = set(mylist) 
myarray = array.array('l', mylist) 

s = "1919 in mylist" 
t = timeit.Timer(s, "from __main__ import mylist") 
print s + ":%.2f usec/pass" % (1000000 * t.timeit(number = 100000)/100000) 

s = "1919 in myset" 
t = timeit.Timer(s, "from __main__ import myset") 
print s + ":%.2f usec/pass" % (1000000 * t.timeit(number = 100000)/100000) 

s = "1919 in myarray" 
t = timeit.Timer(s, "from __main__ import myarray") 
print s + ":%.2f usec/pass" % (1000000 * t.timeit(number = 100000)/100000) 

mysortedlist = sorted(mylist) 
mysortedarray = array.array('l', mysortedlist) 

s = "1919 in mysortedlist" 
t = timeit.Timer(s, "from __main__ import mysortedlist") 
print s + ":%.2f usec/pass" % (1000000 * t.timeit(number = 100000)/100000) 

s = "1919 in mysortedarray" 
t = timeit.Timer(s, "from __main__ import mysortedarray") 
print s + ":%.2f usec/pass" % (1000000 * t.timeit(number = 100000)/100000) 

def bisect_in(a, x): 
    i = bisect.bisect_left(a, x) 
    return (i != len(a) and a[i] == x) 

s = "bisect_in(mysortedlist, 1919)" 
t = timeit.Timer(s, "from __main__ import bisect_in, mysortedlist") 
print s + ":%.2f usec/pass" % (1000000 * t.timeit(number = 100000)/100000) 

，我得到了以下结果：

1919 in mylist:73.89 usec/pass 
1919 in myset:0.29 usec/pass 
1919 in myarray:103.77 usec/pass 
1919 in mysortedlist:75.12 usec/pass 
1919 in mysortedarray:114.21 usec/pass 
bisect_in(mysortedlist, 1919):4.17 usec/pass 

支持他人的论点，使用一组是最快的（假设这个测试下代码使）。

Answer 5

如果您愿意牺牲一些内存效率，您可以构建一个查找表，其中列表索引是您希望检查的值。

最初的名单：

In [106]: %timeit i in myList 
    10000 loops, best of 3: 21.3 us per loop 

构建一个查找表：

In [90]: lookup = [False for i in range(max(myList)+1)] 

    In [91]: for i in myList: 
       lookup[i] = True 

    In [92]: %timeit lookup[i] 
    10000000 loops, best of 3: 50.7 ns per loop 

查找表是这里〜400倍比无序列表更快。

如果您的列表的最大值可接受地较低，并且如果设置查找表的时间显着小于检查变量是否在表格中花费的总时间，则此选项才真正可行。

有趣的是，使用Numpy数组时，查找表方法速度降低了25％。 （但建立查找表要快得多）

编辑：此方法在速度方面也优于“我在set（myList）”中的2倍。