Python vs list dictionary which is faster?

Question

I encoded Euler's problem, and I came across a question of what aroused my curiosity. I have two pieces of code. One of them contains lists in which dictionaries are used.

using lists :

n=100000 num=[] suma=0 for i in range(n,1,-1): tmp=tuple(set([n for n in factors(i)])) if len(tmp) != 2: continue if tmp not in num: num.append(tmp) suma+=i 

using dictionaries :

 n=100000 num={} suma=0 for i in range(n,1,-1): tmp=tuple(set([n for n in factors(i)])) if len(tmp) != 2: continue if tmp not in num: num[tmp]=i suma+=i 

My only concern is performance. Why the second example, using dictionaries, is incredibly fast, faster than the first example with lists. the example with dictionaries works almost thirty times faster!

I tested these 2 codes using n = 1,000,000, and the first code started in 1032 seconds and the second only 3.3 seconds ,, amazin '!

Answer 1

In Python, the average time complexity of finding a dictionary word is O (1), as they are implemented as hash tables. The time complexity of searching a list is O (n) on average. In your code, this matters in the line if tmp not in num: since in the case of a Python list you need to search the entire list to determine membership, whereas in the case of dict this does not exclude the absolute worst case.

See TimeComplexity for more details.

Answer 2

If it's about speed, you shouldn't create lists:

 n = 100000 factors = ((frozenset(factors(i)), i) for i in range(2, n+1)) num = {k:v for k,v in factors if len(k)==2} suma = sum(num.values()) 

Answer 3

In the list, the code if tmp not in num: is O (n) , and O (lgn) is in dict .

Change The dictation is based on hashing, so it is much faster than finding a list of linear elements. Thanks @ user2357112 for this.

Answer 4

I am pretty sure that the "magic sauce" using the dictionary is that the dictionary consists of a key-> value pair.

in a list, you are dealing with arrays, which means that the for loop must start at index 0 inside your list in order to iterate over each entry.

the dictionary just has to find the key-> value pair in question in the first "reverse" and return it, therefore, the speed ...

basically, testing membership in a set of key-> value pairs is much faster than finding a whole list for a value. the larger your list will be slower, the larger it will be ... but this is not always the case, there are scenarios where the list will be faster ... but I believe that this may be the answer you are looking for