Removing duplicates from a list

drochom drochom at googlemail.com
Thu Sep 15 17:33:49 CEST 2005


thanks, nice job. but this benchmark is pretty deceptive:

try this:
(definition of unique2 and unique3 as above)

>>> import timeit
>>> a = range(1000)
>>> t = timeit.Timer('unique2(a)','from __main__ import unique2,a')
>>> t2 = timeit.Timer('stable_unique(a)','from __main__ import stable_unique,a')
>>> t2.timeit(2000)
1.8392596235778456
>>> t.timeit(2000)
51.52945844819817

unique2 has quadratic complexity
unique3 has amortized linear complexity
what it means?
it means that speed of your algorithm strongly depends on
len(unique2(a)). the greater distinct elements in a the greater
difference in execution time of both implementations

regards
przemek




More information about the Python-list mailing list