Самый быстрый способ получить отсортированный уникальный список в python?

Ответ 1

Я считаю, что sorted(set(sequence)) является самым быстрым способом сделать это. Да, set итерации по последовательности, но цикл C-уровня, который намного быстрее, чем любой цикл, который вы делаете на уровне python.

Обратите внимание, что даже с groupby вас все еще есть O(n) + O(nlogn) = O(nlogn) и что наихудшее для этой groupby будет требовать цикл на уровне питона, что резко увеличивает константы в этом O(n) таким образом, в вы получите худшие результаты.

Говоря о CPython, способ оптимизировать вещи - это делать как можно больше на уровне C (см. Этот ответ, чтобы иметь другой пример антиинтуитивной производительности). Чтобы иметь более быстрое решение, вы должны переопределить сортировку в C-расширениях. И даже тогда, удачи с получением чего-то так же быстро, как python Timsort!

Небольшое сравнение "канонического решения" против groupby решения:

>>> import timeit
>>> sequence = list(range(500)) + list(range(700)) + list(range(1000))
>>> timeit.timeit('sorted(set(sequence))', 'from __main__ import sequence', number=1000)
0.11532402038574219
>>> import itertools
>>> def my_sort(seq):
...     return list(k for k,_ in itertools.groupby(sorted(seq)))
... 
>>> timeit.timeit('my_sort(sequence)', 'from __main__ import sequence, my_sort', number=1000)
0.3162040710449219

Как вы можете видеть это в 3 раза медленнее.

Версия, предоставляемая jdm, на самом деле еще хуже:

>>> def make_unique(lst):
...     if len(lst) <= 1:
...         return lst
...     last = lst[-1]
...     for i in range(len(lst) - 2, -1, -1):
...         item = lst[i]
...         if item == last:
...             del lst[i]
...         else:
...             last = item
... 
>>> def my_sort2(seq):
...     make_unique(sorted(seq))
... 
>>> timeit.timeit('my_sort2(sequence)', 'from __main__ import sequence, my_sort2', number=1000)
0.46814608573913574

Почти в 5 раз медленнее. Обратите внимание, что использование seq.sort() а затем make_unique(seq) и make_unique(sorted(seq)) на самом деле одно и то же, поскольку Timsort использует O(n) пространство, которое всегда имеет некоторое перераспределение, поэтому использование sorted(seq) не на самом деле сильно меняют тайминги.

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

Ответ 2

Возможно, это не тот ответ, который вы ищете, но в любом случае вы должны принять это во внимание.

В принципе, у вас есть 2 операции над списком:

unique_list = set(your_list)       # O(n) complexity
sorted_list = sorted(unique_list)  # O(nlogn) complexity

Теперь вы говорите: "Мне кажется, что первая проверка на уникальность, а затем сортировка расточительна", и вы правы. Но насколько же на самом деле это лишний шаг? Возьмите n = 1000000:

# sorted(set(a_list))
O(n) => 1000000
o(nlogn) => 1000000 * 20 = 20000000
Total => 21000000

# Your fastest way
O(nlogn) => 20000000
Total: 20000000

Коэффициент усиления: (1 - 20000000/21000000) * 100 = 4,76%

При n = 5000000 коэффициент усиления: ~ 1,6%

Теперь стоит ли оптимизировать?

Ответ 3

>>> import itertools
>>> a=[2,3,4,1,2,7,8,3]
>>> list(k for k,_ in itertools.groupby(sorted(a)))
[1, 2, 3, 4, 7, 8]

Ответ 4

Это всего лишь кое-что, что я взбивал через пару минут. Функция изменяет список на месте и удаляет последовательные повторы:

def make_unique(lst):
    if len(lst) <= 1:
        return lst
    last = lst[-1]
    for i in range(len(lst) - 2, -1, -1):
        item = lst[i]
        if item == last:
            del lst[i]
        else:
            last = item

Некоторые репрезентативные входные данные:

inp = [
(u"Tomato", "de"), (u"Cherry", "en"), (u"Watermelon", None), (u"Apple", None),
(u"Cucumber", "de"), (u"Lettuce", "de"), (u"Tomato", None), (u"Banana", None),
(u"Squash", "en"), (u"Rubarb", "de"), (u"Lemon", None),
]

Убедитесь, что оба варианта работают по желанию:

print inp
print sorted(set(inp))
# copy because we want to modify it in place
inp1 = inp[:]
inp1.sort()
make_unique(inp1)
print inp1

Теперь на тестирование. Я не использую timeit, так как не хочу копировать список, только сортировка. time1 будет sorted(set(...), time2 является list.sort() с последующим make_unique и time3 является решение с itertools.groupby Авинаш Y.

import time
def time1(number):
    total = 0
    for i in range(number):
        start = time.clock()
        sorted(set(inp))
        total += time.clock() - start
    return total

def time2(number):
    total = 0
    for i in range(number):
        inp1 = inp[:]
        start = time.clock()
        inp1.sort()
        make_unique(inp1)
        total += time.clock() - start
    return total

import itertools 

def time3(number): 
    total = 0 
    for i in range(number): 
        start = time.clock() 
        list(k for k,_ in itertools.groupby(sorted(inp))) 
        total += time.clock() - start 
    return total

sort + make_unique примерно так же быстро, как и sorted(set(...)). Мне пришлось бы сделать еще несколько итераций, чтобы посмотреть, какая из них потенциально быстрее, но в рамках вариантов они очень похожи. Версия itertools немного медленнее.

# done each 3 times
print time1(100000)
# 2.38, 3.01, 2.59
print time2(100000)
# 2.88, 2.37, 2.6
print time3(100000)
# 4.18, 4.44, 4.67

Теперь с большим списком (+ str(i) - для предотвращения дублирования):

old_inp = inp[:]
inp = []
for i in range(100):
    for j in old_inp:
        inp.append((j[0] + str(i), j[1]))

print time1(10000)
# 40.37
print time2(10000)
# 35.09
print time3(10000)
# 40.0

Обратите внимание, что если в списке много дубликатов, первая версия намного быстрее (поскольку она меньше сортирует).

inp = []
for i in range(100):
    for j in old_inp:
        #inp.append((j[0] + str(i), j[1]))
        inp.append((j[0], j[1]))

print time1(10000)
# 3.52
print time2(10000)
# 26.33
print time3(10000)
# 20.5

Ответ 5

import numpy as np
np.unique(...)

он возвращает массив уникальным и отсортированным.