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

Question

我正在寻找最快的方法来了解列表中是否存在值(列表中包含数百万个值)以及它的索引是什么？我知道列表中的所有值都是唯一的,就像我的例子一样.

我尝试的第一种方法是(在我的实际代码中为3.8秒):

a = [4,2,3,1,5,6]

if a.count(7) == 1:
    b=a.index(7)
    "Do something with variable b"

我尝试的第二种方法是(快2倍:我的实际代码为1.9秒):

a = [4,2,3,1,5,6]

try:
    b=a.index(7)
except ValueError:
    "Do nothing"
else:
    "Do something with variable b"

Stackoverflow用户提出的方法(我的实际代码为2.74秒):

a = [4,2,3,1,5,6]
if 7 in a:
    a.index(7)

在我的实际代码中,第一种方法需要3.81秒,第二种方法需要1.88秒.这是一个很好的改进但是:

我是Python /脚本的初学者,我想知道是否有最快的方法可以做同样的事情并节省更多的处理时间？

我的应用程序更具体的解释:

在blender的API中,a可以访问粒子列表:

particles = [1, 2, 3, 4, etc.]

从那里,我可以访问它的位置:

particles[x].location = [x,y,z]

我通过搜索每个粒子的位置测试每个粒子是否存在邻居,如:

if [x+1,y,z] in particles.location
    "Find the identity of this neighbour particle in x:the particle's index
    in the array"
    particles.index([x+1,y,z])

Answer 1

7 in a

最清晰,最快捷的方式.

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

Answer 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 = []

    Nls = [x for x in range(1000,20000,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(math.log(method_in(a,b,c)))
        time_method_set_in.append(math.log(method_set_in(a,b,c)))
        time_method_bisect.append(math.log(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.show()

Answer 3

你可以把你的物品放进去set.集查找非常有效.

尝试:

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

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

Answer 4

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

用法

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

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

Answer 5

原来的问题是：

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

因此，有两件事要找到：

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

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

结果

方法有：

1. in--basically if x in b: return b.index(x)
2. try--try/catch on b.index(x)（跳过必须检查 b 中的 x）
3. 设置——基本上如果 x 在 set(b): 返回 b.index(x)
4. bisect——用它的索引对 b 进行排序，在 sorted(b) 中对 x 进行二分搜索。注意来自@xslittlegrass 的 mod 返回排序 b 中的索引，而不是原始 b)
5. 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()

Answer 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()部分然后重复使用它.如果确实有变化,请提供您正在做的更多详细信息.

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

Answer 8

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

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

有关详细信息,Wikipedia提供了Bloom Filters如何工作的良好概述,并且对"python bloom filter library"的Web搜索将提供至少一些有用的实现.

Answer 9

或使用__contains__：

sequence.__contains__(value)

演示：

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

Answer 10

请注意，in运算符不仅测试相等性（==），还测试身份（is），s 的in逻辑大致等同于以下内容（实际上，它至少是在CPython中用C而不是Python编写的）：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 的in逻辑为：listany()

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

但是，我要强调的是，这是一个in极端的情况，在绝大多数情况下，运算符都是经过高度优化的，而这正是您想要的（当然是使用a list或使用a set）。