tfox
А зачем здесь использовать множество?
Все прекрасно работает и без множества.
Множества в Pythone реализованы через Хеш-таблицу.
Т.е поиск, вставка элементов в среднем выполняются за время O(1).
Поиск в списке выполняется за время O(n) n = количество элементов в списке.
Получается, вариант с множеством выполняется за ~ O(n), со списком за O(n^2).
def bench_unique_set(lst):
seen = set()
result = []
for x in lst:
if x in seen:
continue
seen.add(x)
result.append(x)
return result
def bench_unique_list(lst):
result = []
for x in lst:
if x in result:
continue
result.append(x)
return result
import timeit
import random
for elem in (10000, 30000, 50000, 100000):
mylist = [random.randint(0, elem) for i in range(elem)]
print elem, len(set(mylist))
for name, func in [(k,v) for k,v in globals().items()
if k.startswith('bench')]:
print " %-20s %s" % (name, timeit.timeit(
lambda: func(mylist),number = 1))
10000 6328
bench_unique_set 0.00341678590387
bench_unique_list 0.853494333394
30000 19064
bench_unique_set 0.00928298693915
bench_unique_list 7.69523085824
50000 31700
bench_unique_set 0.0212902408726
bench_unique_list 21.3993917074
100000 63186
bench_unique_set 0.047203690252
bench_unique_list 87.1938787334