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

问题描述 投票：702回答：12

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

我知道列表中的所有值都是唯一的，如本例所示。

我尝试的第一种方法是（在我的实际代码中为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"

Stack Overflow用户的建议方法（我的实际代码为2.74秒：

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

在我的真实代码中，第一种方法耗时3.81秒，第二种方法耗时1.88秒。这是一个很好的改进，但是：

我是使用Python /脚本的初学者，有没有更快的方法来做相同的事情并节省更多的处理时间？

我的应用程序的更多具体说明：

在Blender API中，我可以访问粒子列表：

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])
python performance list
12个回答
1378
投票
7 in a

最快捷的方法。

[您也可以考虑使用set，但是从列表中构造该集合可能要花费比更快的成员资格测试所节省的时间。唯一可以确定的基准就是基准测试。 （这还取决于您需要执行哪些操作）

1
投票

@ Winston Ewert的解决方案极大地提高了超大型列表的速度，但是>>> l=[1,2,3] >>> l.__contains__(3) True >>> 表示，如果经常到达else分支，则try：/ except：/ else：构造将变慢。另一种方法是将this stackoverflow answer方法用于dict：

.get()

a = [4,2,3,1,5,6] index = dict((y, x) for x, y in enumerate(a)) b = index.get(7, None) if b is not None: "Do something with variable b" 方法仅适用于无法保证键在字典中的情况。如果键是存在，它将返回值（与.get(key, default)相同），但如果不存在，则dict[key]返回默认值（此处为.get()）。在这种情况下，您需要确保所选的默认值不在None中。

-1
投票

对我来说，这是0.030秒（真实），0.026秒（用户）和0.004秒（系统）。

a
-1
投票

检查乘积等于k的数组中是否存在两个元素的代码：

try:
print("Started")
x = ["a", "b", "c", "d", "e", "f"]

i = 0

while i < len(x):
    i += 1
    if x[i] == "e":
        print("Found")
except IndexError:
    pass
174
投票

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

enter image description here

测试代码：

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()
32
投票

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

尝试：

set

edit在注释中，您说您想获取元素的索引。不幸的是，集合没有元素位置的概念。另一种方法是对列表进行预排序，然后在每次需要查找元素时使用s = set(a) if 7 in s: # do stuff 。

31
投票
binary search

使用方法

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

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

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

这只会是一个好主意，如果a保持不变，因此我们可以做一次dict（）部分，然后重复使用它。如果确实发生了变化，请提供您正在做的更多详细信息。

7
投票

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

简而言之，如果集合中肯定没有值，则使用Bloom过滤器查找可以很快地告诉您。否则，您可以进行较慢的查找，以获取列表中可能存在的值的索引。因此，如果您的应用程序倾向于比“已找到”结果更频繁地获得“未找到”结果，则可以通过添加布隆过滤器来加快速度。

有关详细信息，Wikipedia很好地概述了布隆过滤器的工作方式，并且对“ python布隆过滤器库”的网络搜索将至少提供一些有用的实现。

5
投票

[请注意，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" 运算符不仅测试相等性（in），还测试身份（==），is的in逻辑为list以下内容（实际上是用C语言编写的）至少在CPython中不是Python）：

roughly equivalent to

[在大多数情况下，这个细节是无关紧要的，但是在某些情况下，它可能会使Python新手感到惊讶，例如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 具有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 与in的list逻辑为：

any()

但是，我要强调的是，这是一个极端的情况，对于大多数情况，any(element is target or element == target for element in lst) 运算符是经过高度优化的，并且确实是您想要的（当然是in或list） 。

4
投票

或使用set：

__contains__

演示：

sequence.__contains__(value)
2
投票

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

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

  • -使“ n”为列表的长度
  • -（可选步骤：如果需要元素索引：将第二列添加到元素的当前索引（0到n-1）-稍后再见]
  • 订购列表或列表的副本（.sort（））
  • 循环通过：
    • 将您的电话号码与列表的第n / 2个元素进行比较
      • 如果更大，则在索引n / 2-n之间再次循环
      • 如果较小，则在索引0-n / 2之间再次循环
      • 如果相同：您找到它
  • 保持缩小列表的大小，直到找到它或只有2个数字（在所寻找的数字的下方和上方）
  • 这将在至多19个步骤中找到1.000.000的列表中的任何元素（精确地为log（2）n）

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

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

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

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.