питона - Sort & Unique против Набора

Question

В Python 2.7, с тем чтобы получить набор уникальных строк из резервированного списка строк, то, что является предпочтительным (~ 10 миллионов строк длины ~ 20):

а) сортировать список и удалить повторяющиеся строки

sort(l) 
unique(l) #some linear time function 

б) просто положить их в наборе

set(l) 

Обратите внимание, что я не заботиться о порядке строк.

Answer 1

Я провел простой тест, чтобы проверить время работы обоих решений. Первый тест создает set, а второй тест сортирует список (он не удаляет дубликаты для простоты).

Как и ожидалось, создание набора выполняется намного быстрее, чем сортировка, поскольку его сложность O(n) при сортировке O(nlogn).

import random 
import string 
import time 


def random_str(): 
    size = random.randint(10, 20) 
    chars = string.ascii_letters + string.digits 
    return ''.join(random.choice(chars) for _ in range(size)) 


l = [random_str() for _ in xrange(1000000)] 

t1 = time.clock() 
for i in range(10): 
    set(l) 
t2 = time.clock() 
print(round(t2-t1, 3)) 

t1 = time.clock() 
for i in range(10): 
    sorted(l) 
t2 = time.clock() 
print(round(t2-t1, 3)) 

Выход я получил:

2.77 
11.83