失眠网,内容丰富有趣,生活中的好帮手!
失眠网 > 检查列表中是否存在值的最快方法

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

时间:2022-09-15 05:08:41

相关推荐

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

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

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

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

堆栈溢出用户建议的方法(我的实际代码为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 indexin the array"particles.index([x+1,y,z])

#1楼

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

如果您要查找的列表和值都是数字,那么这很简单。 如果是字符串:请看底部:

-让“ n”为列表的长度 -可选步骤:如果需要元素索引,请向列表中添加第二列,其中元素的当前索引为(0至n-1)-稍后请参见 订购列表或列表的副本(.sort()) 依次通过: 将您的数字与列表的第n / 2个元素进行比较 如果更大,则在索引n / 2-n之间再次循环 如果较小,则在索引0-n / 2之间再次循环 如果相同:您找到了 不断缩小列表的范围,直到找到它或只有2个数字(在您要查找的数字的下方和上方) 这将在最多19个步骤中找到1.000.000列表中的任何元素(准确地说是log(2)n)

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

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

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

#2楼

听起来您的应用程序可能会受益于使用Bloom Filter数据结构的优势。

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

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

#3楼

正如其他人所述,对于大型列表,in可能会非常慢。 这是insetbisect的性能比较。 请注意时间(以秒为单位)是对数刻度。

测试代码:

import randomimport bisectimport matplotlib.pyplot as pltimport mathimport timedef 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 = []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()

#4楼

对我来说,这是0.030秒(实际),0.026秒(用户)和0.004秒(系统)。

try:print("Started")x = ["a", "b", "c", "d", "e", "f"]i = 0while i < len(x):i += 1if x[i] == "e":print("Found")except IndexError:pass

#5楼

请注意,in运算符不仅测试相等性(==),还测试身份(is),lists的in逻辑大致等效于以下内容(它实际上是用C而不是Python编写的,至少是在CPython中编写的):

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

请注意,使用any()listin逻辑为:

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

但是,我要强调的是,这是一个极端的情况,in绝大多数情况下,in运算符都是经过高度优化的,这正是您想要的(当然是listset)。

#6楼

present = FalsesearchItem = 'd'myList = ['a', 'b', 'c', 'd', 'e']if searchItem in myList:present = Trueprint('present = ', present)else:print('present = ', present)

#7楼

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

n = len(arr1)for i in arr1:if k%i==0:print(i)

#8楼

或使用__contains__

sequence.__contains__(value)

演示:

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

#9楼

@Winston Ewert的解决方案极大地提高了非常大的列表的速度,但是这个stackoverflow答案表明,如果经常到达除外分支,则try:/ except:/ else:构造将变慢。 另一种方法是将.get()方法用于dict:

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)。 你需要确保在这种情况下所选择的默认不会是a

#10楼

这对我有用:(列表理解,单线)

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

这将在一个不错的列表中返回索引。

#11楼

最初的问题是:

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

因此,有两件事要找到:

是列表中的一项,并且 什么是索引(如果在列表中)。

为此,我修改了@xslittlegrass代码以在所有情况下计算索引,并添加了其他方法。

结果

方法是:

in-基本上如果b中的x:返回b.index(x) try--try / catch on b.index(x)(跳过必须检查b中的x) set-基本上,如果x在set(b)中:返回b.index(x) bisect-用索引对其b进行排序,对sorted(b)中的x进行二进制搜索。 注意@xslittlegrass的mod,它返回排序后的b中的索引,而不是原始b) 反向-为b形成字典d的反向循环; 则d [x]提供x的索引。

结果表明,方法5最快。

有趣的是,tryset方法在时间上是等效的。

测试代码

import randomimport bisectimport matplotlib.pyplot as pltimport mathimport timeitimport itertoolsdef 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 wrappeddef method_in(a,b,c):for i,x in enumerate(a):if x in b:c[i] = b.index(x)else:c[i] = -1return cdef method_try(a,b,c):for i, x in enumerate(a):try:c[i] = b.index(x)except ValueError:c[i] = -1def 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 cdef 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 arrayreturn cdef 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 cdef 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()

#12楼

7 in a

最清晰,最快的方法。

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

#13楼

您可以将您的物品放在一个set。 集合查找非常有效。

尝试:

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

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

#14楼

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

用法

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

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

#15楼

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

如果觉得《检查列表中是否存在值的最快方法》对你有帮助,请点赞、收藏,并留下你的观点哦!

本内容不代表本网观点和政治立场,如有侵犯你的权益请联系我们处理。
网友评论
网友评论仅供其表达个人看法,并不表明网站立场。