Fastest way to check if a value exists in a list

Question

What is the fastest way to know if a value exists in a list  a list with millions of values in it  and what its index is  I know that all values in the list are unique as in this example  The first method I try is  3 8 sec in my real code   a    4 2 3 1 5 6   if a count 7     1      b a index 7       quot Do something with variable b quot   The second method I try is  2x faster  1 9 sec for my real code   a    4 2 3 1 5 6   try      b a index 7  except ValueError       quot Do nothing quot  else       quot Do something with variable b quot   Proposed methods from Stack Overflow user  2 74 sec for my real code   a    4 2 3 1 5 6  if 7 in a      a index 7   In my real code  the first method takes 3 81 sec and the second method takes 1 88 sec  It s a good improvement  but  I m a beginner with Python scripting  and is there a faster way to do the same things and save more processing time  More specific explanation for my application  In the Blender API I can access a list of particles  particles    1  2  3  4  etc    From there  I can access a particle s location  particles x  location    x y z   And for each particle I test if a neighbour exists by searching each particle location like so  if  x 1 y z  in particles location      quot Find the identity of this neighbour particle in x the particle s index     in the array quot      particles index  x 1 y z

User · Answer

It sounds like your application might gain advantage from the use of a Bloom Filter data structure.

In short, a bloom filter look-up can tell you very quickly if a value is DEFINITELY NOT present in a set. Otherwise, you can do a slower look-up to get the index of a value that POSSIBLY MIGHT BE in the list. So if your application tends to get the "not found" result much more often then the "found" result, you might see a speed up by adding a Bloom Filter.

For details, Wikipedia provides a good overview of how Bloom Filters work, and a web search for "python bloom filter library" will provide at least a couple useful implementations.

User · Answer

The original question was       What is the fastest way to know if a value exists in a list  a list   with millions of values in it  and what its index is    Thus there are two things to find    is an item in the list  and what is the index  if in the list     Towards this  I modified  xslittlegrass code to compute indexes in all cases  and added an additional method   Results    Methods are    in--basically if x in b  return b index x  try--try catch on b index x   skips having to check if x in b  set--basically if x in set b   return b index x  bisect--sort b with its index  binary search for x in sorted b   Note mod from  xslittlegrass who returns the index in the sorted b  rather than the original b   reverse--form a reverse lookup dictionary d for b  then  d x  provides the index of x    Results show that method 5 is the fastest   Interestingly the try and the set methods are equivalent in time     Test Code  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  lt  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               gt     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

User · Answer

7 in a   Clearest and fastest way to do it   You can also consider using a set  but constructing that set from your list may take more time than faster membership testing will save  The only way to be certain is to benchmark well   this also depends on what operations you require

User · Answer

You could put your items into a set  Set lookups are very efficient   Try   s   set a  if 7 in s      do stuff   edit In a comment you say that you d like to get the index of the element  Unfortunately  sets have no notion of element position  An alternative is to pre-sort your list and then use binary search every time you need to find an element

User · Answer

Or use   contains    sequence   contains   value   Demo   gt  gt  gt  l    1  2  3   gt  gt  gt  l   contains   3  True  gt  gt  gt

User · Answer

As stated by others  in can be very slow for large lists  Here are some comparisons of the performances for in  set and bisect  Note the time  in second  is in log scale   Code for testing  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  lt  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 to great or up if there are to 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

User · Answer

This is not the code  but the algorithm for very fast searching   If your list and the value you are looking for are all numbers  this is pretty straightforward  If strings  look at the bottom    -Let  n  be the length of your list -Optional step  if you need the index of the element  add a second column to the list with current index of elements  0 to n-1  - see later Order your list or a copy of it   sort    Loop through    Compare your number to the n 2th element of the list   If larger  loop again between indexes n 2-n If smaller  loop again between indexes 0-n 2 If the same  you found it   Keep narrowing the list until you have found it or only have 2 numbers  below and above the one you are looking for  This will find any element in at most 19 steps for a list of 1 000 000  log 2 n to be precise    If you also need the original position of your number  look for it in the second  index column   If your list is not made of numbers  the method still works and will be fastest  but you may need to define a function which can compare order strings   Of course  this needs the investment of the sorted   method  but if you keep reusing the same list for checking  it may be worth it

User · Answer

Because the question is not always supposed to be understood as the fastest technical way - I always suggest the most straightforward fastest way to understand write  a list comprehension  one-liner   i for i in list from which to search if i in list to search in    I had a list to search in with all the items  and wanted to return the indexes of the items in the list from which to search   This returns the indexes in a nice list   There are other ways to check this problem - however list comprehensions are quick enough  adding to the fact of writing it quick enough  to solve a problem

User · Answer

Code to check whether two elements exist in array whose product equals k   n   len arr1  for i in arr1      if k i  0          print i

User · Answer

def check availability element  collection  iter       return element in collection   Usage  check availability  a    1 2 3 4  a   b   c      I believe this is the fastest way to know if a chosen value is in an array

User · Answer

Be aware that the in operator tests not only equality      but also identity  is   the in logic for lists is roughly equivalent to the following  it s actually written in C and not Python though  at least in 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    In most circumstances this detail is irrelevant  but in some circumstances it might leave a Python novice surprised  for example  numpy NAN has the unusual property of being not being equal to itself    gt  gt  gt  import numpy  gt  gt  gt  numpy NAN    numpy NAN False  gt  gt  gt  numpy NAN is numpy NAN True  gt  gt  gt  numpy NAN in  numpy NAN  True   To distinguish between these unusual cases you could use any   like    gt  gt  gt  lst    numpy NAN  1   2   gt  gt  gt  any element    numpy NAN for element in lst  False  gt  gt  gt  any element is numpy NAN for element in lst  True    Note the in logic for lists with any   would be   any element is target or element    target for element in lst    However  I should emphasize that this is an edge case  and for the vast majority of cases the in operator is highly optimised and exactly what you want of course  either with a list or with a set

User · Answer

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    This will only be a good idea if a doesn t change and thus we can do the dict   part once and then use it repeatedly  If a does change  please provide more detail on what you are doing

[python] Fastest way to check if a value exists in a list

Examples related to python

Examples related to performance

Examples related to list