检查列表中是否存在值的最快方法

检查一个值是否存在于一个非常大的列表中的最快方法是什么？

2770658 次浏览
小开
最佳答案 
7 in a

最简单和最快速的方法来做到这一点。

你也可以考虑使用set，但是从你的列表中构建这个集合可能需要比更快的成员测试节省更多的时间。唯一确定的方法是很好地基准测试。（这也取决于你需要什么操作）

小开

您可以将项目放入#0。设置查找非常有效。

尝试：

s = set(a)if 7 in s:# do stuff

编辑在注释中，您说您想获取元素的索引。不幸的是，集合没有元素位置的概念。另一种方法是预先排序您的列表，然后每次需要查找元素时使用二分查找。

小开 
def check_availability(element, collection: iter):return element in collection

用法

check_availability('a', [1,2,3,4,'a','b','c'])

我相信这是知道所选值是否在数组中的最快方法。

小开 
a = [4,2,3,1,5,6]
index = dict((y,x) for x,y in enumerate(a))try:a_index = index[7]except KeyError:print "Not found"else:print "found"

只有当a没有改变时，这才是一个好主意，因此我们可以做一次，然后重复使用它。如果a确实改变了，请提供更多关于你在做什么的细节。

小开

这不是代码，而是非常快速搜索的算法。

如果你的列表和你要查找的值都是数字，这很简单。如果字符串：看底部：

  • 设“n”是你列表的长度
  • -可选步骤：如果您需要元素的索引：使用当前元素索引（0到n-1）向列表添加第二列-稍后见
  • 订购您的列表或其副本（. sort（））
  • 循环：
    • 将您的数字与列表的第n/2个元素进行比较
      • 如果较大，则在索引n/2-n之间再次循环
      • 如果较小，则在索引0-n/2之间再次循环
      • 如果相同：你找到了
  • 不断缩小列表，直到找到它或只有2个数字（在您要查找的数字下方和上方）
  • 这将查找最多19个步骤用于1.000.000的列表中的任何元素（准确地说是log（2）n）

如果您还需要数字的原始位置，请在第二个索引列中查找它。

如果您的列表不是由数字组成的，该方法仍然有效并且速度最快，但您可能需要定义一个可以比较/排序字符串的函数。

当然，这需要sorted（）方法的投入，但如果您继续重用相同的列表进行检查，这可能是值得的。

小开

听起来您的应用程序可能会从使用Bloom Filter数据结构中获得优势。

简而言之，布隆过滤器查找可以非常快速地告诉您一个值是否明确不存在于集合中。否则，您可以执行较慢的查找以获取可能在列表中的值的索引。因此，如果您的应用程序倾向于获得“未找到”结果比“找到”结果更频繁，您可能会通过添加布隆过滤器看到速度加快。

有关详细信息，维基百科提供了有关Bloom Filters如何工作的良好概述，并且在网络上搜索“python Bloom Filters库”将提供至少几个有用的实现。

小开

正如其他人所说，对于大型列表，in可能非常慢。以下是in、set和bisect性能的一些比较。注意时间（秒）是对数尺度。

在此处输入图片描述

测试代码：

import randomimport bisectimport matplotlib.pyplot as pltimport mathimport time

def method_in(a, b, c):start_time = time.time()for i, x in enumerate(a):if x in b:c[i] = 1return time.time() - start_time

def method_set_in(a, b, c):start_time = time.time()s = set(b)for i, x in enumerate(a):if x in s:c[i] = 1return time.time() - start_time

def method_bisect(a, b, c):start_time = time.time()b.sort()for i, x in enumerate(a):index = bisect.bisect_left(b, x)if index < len(a):if x == b[index]:c[i] = 1return time.time() - start_time

def profile():time_method_in = []time_method_set_in = []time_method_bisect = []
# adjust range down if runtime is too long or up if there are too many zero entries in any of the time_method listsNls = [x for x in range(10000, 30000, 1000)]for N in Nls:a = [x for x in range(0, N)]random.shuffle(a)b = [x for x in range(0, N)]random.shuffle(b)c = [0 for x in range(0, N)]
time_method_in.append(method_in(a, b, c))time_method_set_in.append(method_set_in(a, b, c))time_method_bisect.append(method_bisect(a, b, c))
plt.plot(Nls, time_method_in, marker='o', color='r', linestyle='-', label='in')plt.plot(Nls, time_method_set_in, marker='o', color='b', linestyle='-', label='set')plt.plot(Nls, time_method_bisect, marker='o', color='g', linestyle='-', label='bisect')plt.xlabel('list size', fontsize=18)plt.ylabel('log(time)', fontsize=18)plt.legend(loc='upper left')plt.yscale('log')plt.show()

profile()
小开

请注意，in运算符不仅测试相等性（==），还测试身份（is），lists的in逻辑是大致相当于（它实际上是用C编写的，而不是Python，至少在CPython中）：

for element in s:if element is target:# fast check for identity implies equalityreturn Trueif element == target:# slower check for actual equalityreturn Truereturn False

在大多数情况下，这个细节无关紧要，但在某些情况下，它可能会让Python新手感到惊讶，例如，numpy.NAN具有不等于自己的不寻常属性：

>>> import numpy>>> numpy.NAN == numpy.NANFalse>>> numpy.NAN is numpy.NANTrue>>> numpy.NAN in [numpy.NAN]True

要区分这些不寻常的情况，您可以使用any()，例如：

>>> lst = [numpy.NAN, 1 , 2]>>> any(element == numpy.NAN for element in lst)False>>> any(element is numpy.NAN for element in lst)True

注意list和any()的in逻辑是：

any(element is target or element == target for element in lst)

但是，我应该强调这是一个边缘情况，对于绝大多数情况，in运算符是高度优化的，当然正是您想要的（无论是list还是set）。

小开

或者使用__contains__：

sequence.__contains__(value)

演示：

>>> l = [1, 2, 3]>>> l.__contains__(3)True>>>
小开

因为这个问题并不总是应该被理解为最快的技术方式-我总是建议最直接、最快的理解/写作方式：列表理解、一行代码

[i for i in list_from_which_to_search if i in list_to_search_in]

我有一个包含所有项目的list_to_search_in，并希望返回list_from_which_to_search中项目的索引。

这将返回一个漂亮列表中的索引。

还有其他方法可以检查这个问题——但是列表推导足够快，加上写得足够快，可以解决问题。

小开

最初的问题是：

知道一个值是否存在于列表（列表）中的最快方法是什么它有数百万个值），它的索引是什么？

因此，有两件事要找：

  1. 是列表中的一个项目，并且
  2. 什么是索引（如果在列表中）。

为此，我修改了@xslittle的代码来计算所有情况下的索引，并添加了一个额外的方法。

搜索结果

在此处输入图片描述

方法是：

  1. in--基本上如果x在b中：返回b.index（x）
  2. try--try/catch在b.index（x）（跳过检查x是否在b中）
  3. set--基本上如果x在set（b）中：返回b.index（x）
  4. bis-用它的索引对b进行排序，在排序（b）中对x进行二进制搜索。来自@xslittle的注释mod，他返回排序b中的索引，而不是原来的b）
  5. 反转--为b形成反向查找字典d；然后d[x]提供x的索引。

结果表明，方法5是最快的。

有趣的是，尝试和集方法在时间上是等价的。

测试代码

import randomimport bisectimport matplotlib.pyplot as pltimport mathimport timeitimport itertools
def wrapper(func, *args, **kwargs):" Use to produced 0 argument function for call it"# Reference https://www.pythoncentral.io/time-a-python-function/def wrapped():return func(*args, **kwargs)return wrapped
def method_in(a,b,c):for i,x in enumerate(a):if x in b:c[i] = b.index(x)else:c[i] = -1return c
def method_try(a,b,c):for i, x in enumerate(a):try:c[i] = b.index(x)except ValueError:c[i] = -1
def method_set_in(a,b,c):s = set(b)for i,x in enumerate(a):if x in s:c[i] = b.index(x)else:c[i] = -1return c
def method_bisect(a,b,c):" Finds indexes using bisection "
# Create a sorted b with its indexbsorted = sorted([(x, i) for i, x in enumerate(b)], key = lambda t: t[0])
for i,x in enumerate(a):index = bisect.bisect_left(bsorted,(x, ))c[i] = -1if index < len(a):if x == bsorted[index][0]:c[i] = bsorted[index][1]  # index in the b array
return c
def method_reverse_lookup(a, b, c):reverse_lookup = {x:i for i, x in enumerate(b)}for i, x in enumerate(a):c[i] = reverse_lookup.get(x, -1)return c
def profile():Nls = [x for x in range(1000,20000,1000)]number_iterations = 10methods = [method_in, method_try, method_set_in, method_bisect, method_reverse_lookup]time_methods = [[] for _ in range(len(methods))]
for N in Nls:a = [x for x in range(0,N)]random.shuffle(a)b = [x for x in range(0,N)]random.shuffle(b)c = [0 for x in range(0,N)]
for i, func in enumerate(methods):wrapped = wrapper(func, a, b, c)time_methods[i].append(math.log(timeit.timeit(wrapped, number=number_iterations)))
markers = itertools.cycle(('o', '+', '.', '>', '2'))colors = itertools.cycle(('r', 'b', 'g', 'y', 'c'))labels = itertools.cycle(('in', 'try', 'set', 'bisect', 'reverse'))
for i in range(len(time_methods)):plt.plot(Nls,time_methods[i],marker = next(markers),color=next(colors),linestyle='-',label=next(labels))
plt.xlabel('list size', fontsize=18)plt.ylabel('log(time)', fontsize=18)plt.legend(loc = 'upper left')plt.show()
profile()
小开

如果你只想检查列表中一个元素的存在，

7 in list_data

是最快的解决方案但请注意

7 in set_data

从一个大列表中创建一个集合比in慢300到400倍，所以如果你需要检查许多元素，首先创建一个集合更快。

在此处输入图片描述

用灌流图创建的情节：

import perfplotimport numpy as np

def setup(n):data = np.arange(n)np.random.shuffle(data)return data, set(data)

def list_in(data):return 7 in data[0]

def create_set_from_list(data):return set(data[0])

def set_in(data):return 7 in data[1]

b = perfplot.bench(setup=setup,kernels=[list_in, set_in, create_set_from_list],n_range=[2 ** k for k in range(24)],xlabel="len(data)",equality_check=None,)b.save("out.png")b.show()

提交答案