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

7 in a

最清晰和最快的方法。

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

---

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

https://i.stack.imgur.com/HSRgg.png

测试代码：

import random
import bisect
import matplotlib.pyplot as plt
import math
import time


def method_in(a, b, c):
    start_time = time.time()
    for i, x in enumerate(a):
        if x in b:
            c[i] = 1
    return 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] = 1
    return 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] = 1
    return 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 lists
    Nls = [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()

---

您可以将您的项目放入 set。集合查找非常有效。

尝试：

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

edit 在评论中您说您想获取元素的索引。不幸的是，集合没有元素位置的概念。另一种方法是对列表进行预排序，然后在每次需要查找元素时使用 binary search。

---

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

用法

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

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

---

原来的问题是：

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

因此，有两件事要找到：

是列表中的一项，索引是什么（如果在列表中）。

为此，我修改了@xslittlegrass 代码以在所有情况下计算索引，并添加了一个附加方法。

结果

https://i.stack.imgur.com/pGDfO.png

方法是：

in-- 基本上 if x in b: return b.index(x) try--try/catch on b.index(x) （跳过检查是否 x in b） set-- 基本上 if x in set(b) : return b.index(x) bisect--用它的索引对 b 排序，在 sorted(b) 中对 x 进行二分搜索。注意来自 @xslittlegrass 的 mod，它返回排序后的 b 中的索引，而不是原始 b) reverse--为 b 形成反向查找字典 d；然后 d[x] 提供 x 的索引。

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

有趣的是，try 和 set 方法在时间上是等价的。

测试代码

import random
import bisect
import matplotlib.pyplot as plt
import math
import timeit
import 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] = -1
    return 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] = -1
    return c

def method_bisect(a,b,c):
    " Finds indexes using bisection "

    # Create a sorted b with its index
    bsorted = 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] = -1
        if 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 = 10
    methods = [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()

---

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 没有改变，这将是一个好主意，因此我们可以执行一次 dict() 部分，然后重复使用它。如果确实发生了变化，请提供有关您正在做什么的更多详细信息。

---

请注意，in 运算符不仅测试相等性 (==)，还测试身份 (is)，list 的 in 逻辑如下 roughly equivalent to（它实际上是用 C 编写的，而不是Python，至少在 CPython 中）：

for element in s: if element is target: # 快速检查身份意味着相等 return True if element == target: # 较慢检查实际相等 return True return False

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

>>> import numpy
>>> numpy.NAN == numpy.NAN
False
>>> numpy.NAN is numpy.NAN
True
>>> 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 

请注意，带有 any() 的 list 的 in 逻辑是：

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

但是，我应该强调这是一种极端情况，对于绝大多数情况，in 运算符都经过了高度优化，并且当然正是您想要的（使用 list 或使用 set）。

---

如果您只想检查列表中是否存在一个元素，

7 in list_data

是最快的解决方案。请注意，尽管

7 in set_data

是一种近乎自由的操作，与集合的大小无关！从大列表创建集合比 in 慢 300 到 400 倍，因此如果需要检查许多元素，首先创建集合更快。

https://i.stack.imgur.com/qDxyN.png

使用 perfplot 创建的绘图：

import perfplot
import 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()

---

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

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

有关详细信息，Wikipedia 很好地概述了布隆过滤器的工作原理，并且在网络上搜索“python 布隆过滤器库”将提供至少几个有用的实现。

---

或使用 __contains__：

sequence.__contains__(value)

演示：

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

---

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

如果您的列表和您要查找的值都是数字，那么这非常简单。如果字符串：查看底部：

-让“n”成为列表的长度

-可选步骤：如果您需要元素的索引：将第二列添加到具有当前元素索引（0到n-1）的列表中 - 见下文

订购您的列表或它的副本 (.sort())

循环：将您的数字与列表的第 n/2 个元素进行比较 如果较大，则在索引 n/2-n 之间再次循环 如果较小，则在索引 0-n/2 之间再次循环 如果相同：您找到了

将您的数字与列表的第 n/2 个元素进行比较 如果较大，则在索引 n/2-n 之间再次循环 如果较小，则在索引 0-n/2 之间再次循环 如果相同：您找到了

如果更大，则在索引 n/2-n 之间再次循环

如果更小，则在索引 0-n/2 之间再次循环

如果相同：你找到了

继续缩小列表，直到找到它或只有 2 个数字（在您要查找的数字的下方和上方）

这将在最多 19 个步骤中找到 1.000.000 列表中的任何元素（准确地说是 log(2)n）

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

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

当然，这需要 sorted() 方法的投入，但如果你一直重复使用同一个列表进行检查，这可能是值得的。

---

因为问题并不总是应该被理解为最快的技术方式 - 我总是建议最直接的最快方式来理解/编写：列表理解，单行

[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 中项目的索引。

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

还有其他方法可以检查这个问题 - 但是列表推导足够快，加上编写它足够快的事实，以解决问题。

---