I checked the reference speed when using python list, dictionary, and set type in.
Introduction
The following site describes the following. Element validation (O (1)) using sets and dictionaries is faster than array retrieval (O (n)). When looking up a in b, b should be sets or dictionaries, not lists or tuples. http://www.peignot.net/python-speed
Is it true? How different is it from what I thought? I was curious, so I actually tried it.
Execution environment
python2.7 windows7 Intel Core i5 CPU 2.4GHz Memory 4.0 GB
Execution condition
In a list, dictionary, and set type, I made an integer sequence (1 million elements) for each multiple of 1, every multiple of 2, and every multiple of 3, and referenced in in from 1 to 10,000. The reason why we created integer sequences for each multiple of 1, every multiple of 2, and every multiple of 3 is to investigate the effect of the hit rate on the processing speed. The total number of tests is 10 times. See the code below for details.
result
While the list reference was slow enough to die, the dictionary and set type were super fast. In the list, it was found that the processing speed was clearly slower when the hit rate was low than when the hit rate was high. The unit is seconds, which is the total time when executed 10 times.
On the other hand, the processing speed of the dictionary type and the set type did not decrease so much. (3/5 8:08 Corrected the figure because the range was incorrect)
Conclusion
In a list with a large number of elements Element in list Sentences should be avoided as much as possible. Really slow enough to die.
Experimental codes
def lists(q,h):
ls = [i for i in range(0,q*h,h)]
for i in range(q): i in ls
def dicts(q,h):
dc = {i:i for i in range(0,q*h,h)}
for i in range(q): i in dc
def setts(q,h):
st = set(i for i in range(0,q*h,h))
for i in range(q): i in st
def exe(func,num=100):
from timeit import timeit
setup = 'from __main__ import ' + func[:5]
print "%s: %s" % (func, timeit(func, setup, number=num))
if __name__=='__main__':
q = 10**4
funcs = ['lists','dicts','setts']
hits = [1,2,3]
for h in hits:
for f in funcs:
func = '%s(%s, %s)' % (f,q,h)
print func
exe(func,10)
Recommended Posts