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.
Generally the lists are faster than sets. But in the case of searching for an element in a collection, sets are faster because sets have been implemented using hash tables. So basically Python does not have to search the full set, which means that the time complexity in average is O(1).
Sets cannot contain duplicates, and they will simply disappear. Sets use hashing to perform look ups which makes them way faster than lists in this regard.
Sets are used to store multiple items in a single variable. Set is one of 4 built-in data types in Python used to store collections of data, the other 3 are List, Tuple, and Dictionary, all with different qualities and usage. A set is a collection which is unordered, unchangeable*, and unindexed.
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.
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
>>> def iter_test(iterable):
... for i in iterable:
... pass
...
>>> from timeit import timeit
>>> timeit(
... "iter_test(iterable)",
... setup="from __main__ import iter_test; iterable = set(range(10000))",
... number=100000)
12.666952133178711
>>> timeit(
... "iter_test(iterable)",
... setup="from __main__ import iter_test; iterable = list(range(10000))",
... number=100000)
9.917098999023438
>>> timeit(
... "iter_test(iterable)",
... setup="from __main__ import iter_test; iterable = tuple(range(10000))",
... number=100000)
9.865639209747314
Determine if an object is present
>>> def in_test(iterable):
... for i in range(1000):
... if i in iterable:
... pass
...
>>> from timeit import timeit
>>> timeit(
... "in_test(iterable)",
... setup="from __main__ import in_test; iterable = set(range(1000))",
... number=10000)
0.5591847896575928
>>> timeit(
... "in_test(iterable)",
... setup="from __main__ import in_test; iterable = list(range(1000))",
... number=10000)
50.18339991569519
>>> timeit(
... "in_test(iterable)",
... setup="from __main__ import in_test; iterable = tuple(range(1000))",
... number=10000)
51.597304821014404
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 (< 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.
List performance:
>>> import timeit
>>> timeit.timeit(stmt='10**6 in a', setup='a = range(10**6)', number=100000)
0.008128150348026608
Set performance:
>>> 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].
>>> x = set([1, 1, 2, 2, 3, 3])
>>> x
{1, 2, 3}
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.
A list is mutable sequence, typically used to store collections of homogeneous items.
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.
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.
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.
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 :-)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With