摘要：问题描述：检查一个值是否存在于一个非常大的列表（包含数百万个值）中以及它的索引是什么的最快方法是什么？解决方案 1：7 in a 最清晰、最快捷的方法。您也可以考虑使用set，但从列表中构建该集合可能比更快的成员资格测试节省的时间要多。唯一可以确定的方法是进行良好的基准测试。（这也取决于您需要的操作）解决方案...

问题描述：

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

解决方案 1：

7 in a

最清晰、最快捷的方法。

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

解决方案 2：

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

在此处输入图片描述

测试代码：

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

解决方案 3：

你可以把你的物品放进set。集合查找非常高效。

尝试：

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

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

解决方案 4：

最初的问题是：

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

因此，有两件事需要发现：

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

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

结果

在此处输入图片描述

方法有：

in——基本上如果 x 在 b 中：返回 b.index(x)
try--try/catch b.index(x) （跳过检查 x 是否在 b 中）
设置——基本上如果 x 在 set(b) 中：返回 b.index(x)
bisect--用索引对 b 进行排序，在 sorted(b) 中二分查找 x。注意来自 @xslittlegrass 的 mod，它返回的是排序后的 b 中的索引，而不是原始 b)
反向——为 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()

解决方案 5：

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

用法

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

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

解决方案 6：

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() 部分，然后重复使用它。如果 a 确实发生了变化，请提供有关您正在做的事情的更多详细信息。

解决方案 7：

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

7 in list_data

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

7 in set_data

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

在此处输入图片描述

使用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()

解决方案 8：

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

for element in s:
    if element is target:
        # fast check for identity implies equality
        return True
    if element == target:
        # slower check for actual equality
        return True
return False

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

>>> 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

注意s within的逻辑是：list`any()`

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

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

解决方案 9：

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

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

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

解决方案 10：

检查列表中是否存在值

xslittlegrass 的回答表明，在检查列表中是否存在多个值时，先将列表转换为集合，然后对in集合使用运算符，比对列表使用运算符要快得多in。另一方面，Nico 的回答表明，在检查列表中是否存在单个值时，先将列表转换为集合是不值得的，因为转换为集合本身的成本很高。总之，这些答案意味着，对于某些值，将其转换为集合并检查这些值是否存在于集合中要比检查它们是否存在于列表中更快。

事实证明，这个数字非常小。下图显示了in在集合和in列表上检查不同数量的值时运行时间的差异。如图所示，平均而言，如果您需要检查列表中是否存在 5 个（或更多）值，则先将该列表转换为集合，然后再检查集合会更快。1

如果列表中存在值，则获取其索引

另一方面，如果您想检查列表中是否存在值并返回存在的值的索引，那么无论列表的长度如何，对于少量值，直接list.index()在 try-except 块中使用搜索是最快的方法。特别是，如果您想找到单个值的索引，这是最快的选择。但是，平均而言，如果要搜索的值超过 10 个，那么构建索引查找字典（如DarrylG 的答案中所示）是最快的选择。2

结果2

1用于生成第一个图形的代码。

from random import sample
from timeit import repeat
from functools import partial
import matplotlib.pyplot as plt
from matplotlib.ticker import MultipleLocator

def list_in(a, b):
    return [x in b for x in a]


def set_in(a, b):
    s = set(b)
    return [x in s for x in a]


def profile(methods):
    sizes = range(1, 31, 2)
    colors = ['r', 'b', 'g']
    Ns = [100, 1000000]
    fig, axs = plt.subplots(1, len(Ns), figsize=(10, 4), facecolor='white')
    for N, ax in zip(Ns, axs):
        b = sample(range(N), k=N)
        times = {f.__name__: [] for f in methods}
        for size in sizes:
            a = sample(range(len(b)*3//2), k=size)
            for label, f in zip(times, methods):
                func = partial(f, a, b)
                times[label].append(min(repeat(func, number=10))/10)
        for (k, ts), c in zip(times.items(), colors):
            ax.plot(sizes, ts, f'{c}o-', label=k)
        ax.set_title(f'List size = {N:,d}', fontsize=18)
        ax.set_xlabel('Number of values to check', fontsize=14)
        ax.set_ylabel('Runtime', fontsize=14)
        ax.xaxis.set_major_locator(MultipleLocator(5))
        ax.legend()
    return fig


methods = [list_in, set_in]
fig = profile(methods)
fig.tight_layout();

2用于生成第二个图形的代码。

def try_index(a, b):
    c = []
    for x in a:
        try:
            c.append(b.index(x))
        except ValueError:
            c.append(-1)
    return c


def set_in(a, b):
    s = set(b)
    return [b.index(x) if x in s else -1 for x in a]


def dict_lookup(a, b):
    # for faster lookups, convert dict to a function beforehand
    reverse_lookup = {x:i for i, x in enumerate(b)}.get
    return [reverse_lookup(x, -1) for x in a]


methods = [try_index, set_in, dict_lookup]
fig = profile(methods)
fig.suptitle('Get index of values that exist in a list', fontsize=20)
fig.tight_layout();

解决方案 11：

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

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

-让“n”成为列表的长度
-可选步骤：如果您需要元素的索引：将第二列添加到具有当前元素索引的列表中（0 到 n-1）- 请参阅后面的内容
对列表或其副本进行排序 (.sort())
循环遍历：

+ 将您的数字与列表中的第 n/2 个元素进行比较


    - 如果更大，则在索引 n/2-n 之间再次循环
    - 如果较小，则再次在索引 0-n/2 之间循环
    - 如果相同：你找到了

继续缩小列表，直到找到它或只有 2 个数字（在您要查找的数字的下方和上方）
这将在最多 19 步内找到 1,000,000 个列表的任何元素（准确地说是 log(2)n）

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

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

当然，这需要投资 sorted() 方法，但如果您继续重复使用相同的列表进行检查，那么这可能是值得的。

解决方案 12：

空间数据的边缘情况

可能有更快的算法来处理空间数据（例如重构以使用 kd 树），但检查向量是否在数组中的特殊情况很有用：

如果您有空间数据（即笛卡尔坐标）
如果你有整数掩码（即数组过滤）

在这种情况下，我想知道由两个点定义的（无向）边是否位于（无向）边的集合中，以便

(pair in unique_pairs) | (pair[::-1] in unique_pairs) for pair in pairs

其中pair构成两个任意长度（即形状(2,N)）的向量。

如果这些向量之间的距离有意义，那么测试可以用浮点不等式来表示，如

test_result = Norm(v1 - v2) < Tol

并且“值存在于列表中”只是any(test_result)。

下面是整数对和 R3 向量对的示例代码和虚拟测试集生成器。

# 3rd party
import numpy as np
import numpy.linalg as LA
import matplotlib.pyplot as plt

# optional
try:
    from tqdm import tqdm
except ModuleNotFoundError:
    def tqdm(X, *args, **kwargs):
        return X
    print('tqdm not found. tqdm is a handy progress bar module.')
    

def get_float_r3_pairs(size):
    """ generate dummy vector pairs in R3  (i.e. case of spatial data) """
    coordinates = np.random.random(size=(size, 3))
    pairs = []
    for b in coordinates:
        for a in coordinates:
            pairs.append((a,b))
    pairs = np.asarray(pairs)
    return pairs
    
        
def get_int_pairs(size):
    """ generate dummy integer pairs (i.e. case of array masking) """
    coordinates = np.random.randint(0, size, size)
    pairs = []
    for b in coordinates:
        for a in coordinates:
            pairs.append((a,b))
    pairs = np.asarray(pairs)
    return pairs


def float_tol_pair_in_pairs(pair:np.ndarray, pairs:np.ndarray) -> np.ndarray:
    """
    True if abs(a0 - b0) <= tol & abs(a1 - b1) <= tol for (ai1, aj2), (bi1, bj2)
    in [(a01, a02), ... (aik, ajl)]
    
    NB this is expected to be called in iteration so no sanitization is performed.

    Parameters
    ----------
    pair : np.ndarray
        pair of vectors with shape (2, M)
    pairs : np.ndarray
        collection of vector pairs with shape (N, 2, M)

    Returns
    -------
    np.ndarray
        (pair in pairs) | (pair[::-1] in pairs).
    """
    m1 = np.sum( abs(LA.norm(pairs - pair, axis=2)) <= (1e-03, 1e-03), axis=1 ) == 2
    m2 = np.sum( abs(LA.norm(pairs - pair[::-1], axis=2)) <= (1e-03, 1e-03), axis=1 ) == 2
    return m1 | m2


def get_unique_pairs(pairs:np.ndarray) -> np.ndarray:
    """
    apply float_tol_pair_in_pairs for pair in pairs
    
    Parameters
    ----------
    pairs : np.ndarray
        collection of vector pairs with shape (N, 2, M)

    Returns
    -------
    np.ndarray
        pair if not ((pair in rv) | (pair[::-1] in rv)) for pair in pairs

    """
    pairs = np.asarray(pairs).reshape((len(pairs), 2, -1))
    rv = [pairs[0]]
    for pair in tqdm(pairs[1:], desc='finding unique pairs...'):
        if not any(float_tol_pair_in_pairs(pair, rv)):
            rv.append(pair)
    return np.array(rv)

计时结果