New course! Every coder should learn Generative AI!
Try a free lesson+ 12
Set is implemented by a hash-table data structure. For this reason, checking if a specific value exists in the set, is instant O(1) time, requires no iteration. On the other hand to check if a value is included in a list, all elements must be checked in a loop, so that is O(n) time.
But the elements of the set are not ordered, not indexed. So sometimes a list is a better choice, depending what you want to use it for.
+ 10
There is big difference between set and list.
set don't allows duplicate values and set is unordered where list is ordered.
So when we iterate list it iterates by queue where set iterates in random order
https://code.sololearn.com/cCjHJ2NTY87T/?ref=app
+ 10
tuple and set are faster than lists because:
tuple: immutable, which means it has only 2 methods(count and index). immutability makes it the fastest
set: mutable, not as fast as tuple, it doesn't allow duplicates and has no index method
+ 10
Lokesh Belekar. Hash table reference:
https://www.sololearn.com/learn/668/?ref=app
+ 6
Tibor Santa is exactly correct
+ 5
Sets in Python are often used for two purposes:
1. Removing the duplicate entries in a collection
2. For membership testing.
By membership, here we mean to find existence of element in a collection
The focus of this post is to evaluate performance of list, tuple and set data structures with respect to each other on the basis of membership testing.
How do I do it? Well, some code, some data collection and some analysis
[sourcecode language=”python”]
from datetime import datetime
listA = range(10000000)
setA = set(listA)
tupA = tuple(listA)
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)
[/sourcecode]
Below is the average of 10 iterations for the time taken by lists/tuples and sets for testing membership of 9999, 99999, 999999 in 10000000
Search 9999 in 10000000
list tuple set
0.8 0.8 1.9
Search 99999 in 10000000
list tuple set
2.6 2.8 1.7
Search 999999 in 10000000
list tuple set
21.4 21.6 0.8
Conclusions
1. for testing membership of elements at the beginning of the collection, lists or tuples perform more than 100% better than sets
2. As soon as you start testing membership of elements that are in the middle or end of the collection, sets perform 40% – 1800% better than lists or tuples
You now have a fair idea why you should think of using sets for large collections…
+ 4
The python wiki says: "Membership testing with sets and dictionaries is much faster, O(1), than searching sequences, O(n). When testing "a in b", b should be a set or dictionary instead of a list or tuple."
I've been using sets in place of lists whenever speed is important in my code, but lately I've been wondering why sets are so much faster than lists. Could anyone explain, or point me to a source that would explain, what exactly is going on behind the scenes in python to make sets faster?