Python Sets vs Lists

Question

In Python  which data structure is more efficient speedy  Assuming that order is not important to me and I would be checking for duplicates anyway  is a Python set slower than a Python list

User · Answer

Set wins due to near instant  contains  checks  https   en wikipedia org wiki Hash table List implementation  usually an array  low level close to the metal good for iteration and random access by element index  Set implementation  https   en wikipedia org wiki Hash table  it does not iterate on a list  but finds the element by computing a hash from the key  so it depends on the nature of the key elements and the hash function  Similar to what is used for dict  I suspect list could be faster if you have very few elements   lt  5   the larger element count the better the set will perform for a contains check  It is also fast for element addition and removal  Also always keep in mind that building a set has a cost   NOTE  If the list is already sorted  searching the list could be quite fast on small lists  but with more data a set is faster for contains checks

User · Answer

I would recommend a Set implementation where the use case is limit to referencing or search for existence and Tuple implementation where the use case requires you to perform iteration  A list is a low-level implementation and requires significant memory overhead

User · Answer

I was interested in the results when checking  with CPython  if a value is one of a small number of literals  set wins in Python 3 vs tuple  list and or   from timeit import timeit  def in test1      for i in range 1000       if i in  314  628         pass  def in test2      for i in range 1000       if i in  314  628         pass  def in test3      for i in range 1000       if i in  314  628         pass  def in test4      for i in range 1000       if i    314 or i    628        pass  print  tuple   print timeit  in test1     setup  from   main   import in test1   number 100000   print  list   print timeit  in test2     setup  from   main   import in test2   number 100000   print  set   print timeit  in test3     setup  from   main   import in test3   number 100000   print  or   print timeit  in test4     setup  from   main   import in test4   number 100000     Output   tuple 4 735646052286029 list 4 7308746771886945 set 3 5755991376936436 or 4 687681658193469   For 3 to 5 literals  set still wins by a wide margin  and or becomes the slowest   In Python 2  set is always the slowest  or is the fastest for 2 to 3 literals  and tuple and list are faster with 4 or more literals  I couldn t distinguish the speed of tuple vs list   When the values to test were cached in a global variable out of the function  rather than creating the literal within the loop  set won every time  even in Python 2   These results apply to 64-bit CPython on a Core i7

User · Answer

from datetime import datetime listA   range 10000000  setA   set listA  tupA   tuple listA   Source Code  def calc data  type   start   datetime now   if data in type  print    end   datetime now   print end-start  calc 9999  listA  calc 9999  tupA  calc 9999  setA    Output after comparing 10 iterations for all 3   Comparison

User · Answer

Sets are faster  morover you get more functions with sets  such as lets say you have two sets    set1     Harry Potter    James Bond    Iron Man   set2     Captain America    Black Widow    Hulk    Harry Potter    James Bond     We can easily join two sets   set3   set1 union set2    Find out what is common in both   set3   set1 intersection set2    Find out what  is different in both   set3   set1 difference set2    And much more  Just try them out  they are fun  Moreover if you have to work on the different values within 2 list or common values within 2 lists  I prefer to convert your lists to sets  and many programmers do in that way  Hope it helps you  -

User · Answer

tl dr  Data structures  DS  are important because they are used to perform operations on data which basically implies  take some input  process it  and give back the output   Some data structures are more useful than others in some particular cases  Therefore  it is quite unfair to ask which  DS  is more efficient speedy  It is like asking which tool is more efficient between a knife and fork  I mean all depends on the situation   Lists  A list is mutable sequence  typically used to store collections of homogeneous items   Sets  A set object is an unordered collection of distinct hashable objects  It is commonly used to test membership  remove duplicates from a sequence  and compute mathematical operations such as intersection  union  difference  and symmetric difference   Usage  From some of the answers  it is clear that a list is quite faster than a set when iterating over the values  On the other hand  a set is faster than a list when checking if an item is contained within it  Therefore  the only thing you can say is that a list is better than a set for some particular operations and vice-versa

User · Answer

List performance    gt  gt  gt  import timeit  gt  gt  gt  timeit timeit stmt  10  6 in a   setup  a   range 10  6    number 100000  0 008128150348026608   Set performance    gt  gt  gt  timeit timeit stmt  10  6 in a   setup  a   set range 10  6     number 100000  0 005674857488571661   You may want to consider Tuples as they re similar to lists but can   t be modified  They take up slightly less memory and are faster to access  They aren   t as flexible but are more efficient than lists  Their normal use is to serve as dictionary keys   Sets are also sequence structures but with two differences from lists and tuples  Although sets do have an order  that order is arbitrary and not under the programmer   s control  The second difference is that the elements in a set must be unique   set by definition   python   wiki      gt  gt  gt  x   set  1  1  2  2  3  3    gt  gt  gt  x  1  2  3

User · Answer

It depends on what you are intending to do with it   Sets are significantly faster when it comes to determining if an object is present in the set  as in x in s   but are slower than lists when it comes to iterating over their contents   You can use the timeit module to see which is faster for your situation

User · Answer

Lists are slightly faster than sets when you just want to iterate over the values   Sets  however  are significantly faster than lists if you want to check if an item is contained within it  They can only contain unique items though   It turns out tuples perform in almost exactly the same way as lists  except for their immutability   Iterating   gt  gt  gt  def iter test iterable           for i in iterable              pass      gt  gt  gt  from timeit import timeit  gt  gt  gt  timeit           iter test iterable            setup  from   main   import iter test  iterable   set range 10000             number 100000  12 666952133178711  gt  gt  gt  timeit           iter test iterable            setup  from   main   import iter test  iterable   list range 10000             number 100000  9 917098999023438  gt  gt  gt  timeit           iter test iterable            setup  from   main   import iter test  iterable   tuple range 10000             number 100000  9 865639209747314   Determine if an object is present   gt  gt  gt  def in test iterable           for i in range 1000               if i in iterable                  pass      gt  gt  gt  from timeit import timeit  gt  gt  gt  timeit           in test iterable            setup  from   main   import in test  iterable   set range 1000             number 10000  0 5591847896575928  gt  gt  gt  timeit           in test iterable            setup  from   main   import in test  iterable   list range 1000             number 10000  50 18339991569519  gt  gt  gt  timeit           in test iterable            setup  from   main   import in test  iterable   tuple range 1000             number 10000  51 597304821014404

[python] Python Sets vs Lists

Examples related to python

Examples related to list

Examples related to performance

Examples related to data-structures

Examples related to set