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

12 回答

• 25

  正如其他人所说， 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()
  

  回复于 2024-04-20T22:09:03+08:00
• 5

  你可以将你的物品放入set . 集查找非常有效 .

  尝试：

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

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

  回复于 2024-04-20T22:09:03+08:00
• 29

  对我来说它是0.030s（真实），0.026s（用户）和0.004s（sys） .

  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
  

  回复于 2024-04-20T22:09:03+08:00
• 14

  7 in a
  

  最清晰，最快捷的方式 .

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

  回复于 2024-04-20T22:09:03+08:00
• 1146

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

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

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

  回复于 2024-04-20T22:09:03+08:00
• 1

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

  Usage

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

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

  回复于 2024-04-20T22:09:03+08:00
• 0

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

  回复于 2024-04-20T22:09:03+08:00
• 3

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

  对于s中的元素：
  如果元素是目标：
  ＃快速检查身份意味着平等
  返回True
  if element == target：
  ＃慢检查实际的平等
  返回True
  返回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
  

  注意 list 的 in 逻辑与 any() 将是：

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

  但是，我应该强调这是一个边缘情况，并且对于绝大多数情况， in 运算符是高度优化的，当然正是您想要的（使用 list 或 set ） .

  回复于 2024-04-20T22:09:03+08:00
• 0

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

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

  • -let "n"是列表的长度

  • -optional步骤：如果需要元素的索引：使用元素的当前索引（0到n-1）将第二列添加到列表中 - 请参阅稍后的内容

  • 订购您的清单或其副本（.sort（））

  • 循环：

  • 将您的号码与列表的第n / 2个元素进行比较

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

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

  • 如果相同：你找到了

  • 继续缩小列表范围，直到找到它或只有2个数字（低于和高于您要查找的数字）

  • 这将找到 at most 19 steps for a list of 1.000.000 中的任何元素（准确地说是log（2）n）

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

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

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

  回复于 2024-04-20T22:09:03+08:00
• 125

  或者使用 __contains__ ：

  sequence.__contains__(value)
  

  Demo:

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

  回复于 2024-04-20T22:09:03+08:00
• 1

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

  回复于 2024-04-20T22:09:03+08:00
• 1

  用于检查产品是否等于k的数组中是否存在两个元素的代码 .

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

  回复于 2024-04-20T22:09:03+08:00