How do I remove duplicates from a list, while preserving order?

Как мне удалить дубликаты из списка с сохранением порядка? Использование набора для удаления дубликатов разрушает исходный порядок. Существует ли встроенная идиома Pythonic?

Здесь у вас есть несколько альтернатив: http://www.peterbe.com/plog/uniqifiers-benchmark

Самый быстрый:

def f7(seq):
    seen = set()
    seen_add = seen.add
    return [x for x in seq if not (x in seen or seen_add(x))]

Зачем присваивать seen.add to seen_add вместо простого вызова seen.add? Python - динамический язык, и разрешение seen.add каждой итерации обходится дороже, чем разрешение локальной переменной. seen.add могло измениться между итерациями, а среда выполнения недостаточно умна, чтобы исключить это. Чтобы обезопасить себя, она должна проверять объект каждый раз.

Если вы планируете часто использовать эту функцию для одного и того же набора данных, возможно, вам было бы лучше использовать упорядоченный набор: http://code.activestate.com/recipes/528878 /

O(1) вставка, удаление и проверка элементов для каждой операции.

(Небольшое дополнительное примечание: seen.add() всегда возвращается None, поэтому or приведенное выше приведено только как способ попытаться обновить набор, а не как неотъемлемая часть логического теста.)

Наилучшее решение зависит от версии Python и ограничений среды:

Python 3.7+ (и большинство интерпретаторов, поддерживающих 3.6, в качестве детали реализации):

Впервые представленный в PyPy 2.5.0 и принятый в CPython 3.6 в качестве детали реализации, прежде чем стать языковой гарантией в Python 3.7, plain dict упорядочен для вставки и даже более эффективен, чем (также C, реализованный в CPython 3.5) collections.OrderedDict. Таким образом, самое быстрое решение, безусловно, является и самым простым:

>>> items = [1, 2, 0, 1, 3, 2]
>>> list(dict.fromkeys(items))  # Or [*dict.fromkeys(items)] if you prefer
[1, 2, 0, 3]

Как list(set(items)) это переносит всю работу на уровень C (на CPython), но поскольку dicts упорядочены для вставки, dict.fromkeys порядок не теряется. Это медленнее, чем list(set(items)) (обычно занимает на 50-100% больше времени), но намного быстрее, чем любое другое решение для сохранения порядка (занимает примерно половину времени взломов, связанных с использованием sets в listcomp).

Важное примечание: unique_everseen Решение от more_itertools (см. Ниже) обладает некоторыми уникальными преимуществами с точки зрения лени и поддержки нехешируемых входных элементов; если вам нужны эти функции, это единственное решение, которое будет работать.

Python 3.5 (и все более старые версии, если производительность не критична)

Как указал Рэймонд, в CPython 3.5, где OrderedDict реализован на C, уродливые взломы понимания списка выполняются медленнее, чем OrderedDict.fromkeys (если вам действительно не нужен список в конце - и даже тогда, только если входные данные очень короткие). Итак, с точки зрения производительности и удобочитаемости лучшим решением для CPython 3.5 является OrderedDict эквивалент использования plain на уровне 3.6+ dict:

>>> from collections import OrderedDict
>>> items = [1, 2, 0, 1, 3, 2]
>>> list(OrderedDict.fromkeys(items))
[1, 2, 0, 3]

В CPython 3.4 и более ранних версиях это будет выполняться медленнее, чем в некоторых других решениях, поэтому, если профилирование покажет, что вам нужно решение получше, продолжайте читать.

Python 3.4 и более ранних версий, если производительность критична и модули сторонних производителей приемлемы

Как @abarnert отмечает, more_itertools библиотека (pip install more_itertools) содержит unique_everseen функцию, которая создана для решения этой проблемы без каких-либо нечитаемых (not seen.add) мутаций в понимании списка. К тому же это самое быстрое решение:

>>> from more_itertools import unique_everseen
>>> items = [1, 2, 0, 1, 3, 2]
>>> list(unique_everseen(items))
[1, 2, 0, 3]

Всего один простой импорт библиотеки и никаких взломов.

Модуль адаптирует рецепт itertools unique_everseen который выглядит следующим образом:

def unique_everseen(iterable, key=None):
    "List unique elements, preserving order. Remember all elements ever seen."
    # unique_everseen('AAAABBBCCDAABBB') --> A B C D
    # unique_everseen('ABBCcAD', str.lower) --> A B C D
    seen = set()
    seen_add = seen.add
    if key is None:
        for element in filterfalse(seen.__contains__, iterable):
            seen_add(element)
            yield element
    else:
        for element in iterable:
            k = key(element)
            if k not in seen:
                seen_add(k)
                yield element

но в отличие от itertools recipe, он поддерживает элементы, не поддающиеся хэшированию (за счет снижения производительности; если все элементы в iterable не поддаются хэшированию, алгоритм становится O(n²), по сравнению с O(n) если все они поддаются хэшированию).

Важное примечание: в отличие от всех других решений здесь, unique_everseen может использоваться лениво; максимальное использование памяти будет таким же (в конечном итоге базовый set увеличится до того же размера), но если вы не list получите результат, вы просто повторите его, вы сможете обрабатывать уникальные элементы по мере их нахождения, а не ждать, пока весь ввод будет дедуплицирован перед обработкой первого уникального элемента.

Python 3.4 и более ранних версий, если производительность критична и сторонние модули недоступны

У вас есть два варианта:

1. Скопируйте и вставьте unique_everseen рецепт в свой код и используйте его в more_itertools примере выше

   
   



2. Используйте уродливые хаки, чтобы позволить одному listcomp проверять и обновлять a set для отслеживания того, что было замечено:

   
   

   seen = set()
   [x for x in seq if x not in seen and not seen.add(x)]
   

   
   

   за счет использования уродливого взлома:

   
   

    not seen.add(x)
   

   
   

   который основан на том факте, что set.add это метод на месте, который всегда возвращает значение None so not None , равное True.

   
   

Обратите внимание, что все из приведенных выше решений являются O(n) (за исключением вызова unique_everseen для итерации нехешируемых элементов, который является O(n²), в то время как другие немедленно завершились бы неудачей с TypeError), поэтому все решения достаточно производительны, когда они не являются самым популярным путем кода. Какой из них использовать, зависит от того, на какие версии языковой спецификации / интерпретатора / модулей сторонних производителей вы можете положиться, важна ли производительность (не думайте, что это так; обычно это не так), и, самое главное, от удобочитаемости (потому что, если человек, который поддерживает этот код, позже окажется в убийственном настроении, ваша хитроумная микрооптимизация, вероятно, того не стоила).

В CPython 3.6+ (и всех других реализациях Python, начиная с Python 3.7+) словари упорядочены, поэтому способ удалить дубликаты из итерируемого объекта, сохраняя его в исходном порядке, заключается в следующем:

>>> list(dict.fromkeys('abracadabra'))
['a', 'b', 'r', 'c', 'd']

В Python 3.5 и ниже (включая Python 2.7) используйте OrderedDict. Мои тайминги показывают, что сейчас это самый быстрый и сокращенный из различных подходов для Python 3.5 (когда он получил реализацию на C; до версии 3.5 это все еще самое простое решение, хотя и не самое быстрое).

>>> from collections import OrderedDict
>>> list(OrderedDict.fromkeys('abracadabra'))
['a', 'b', 'r', 'c', 'd']

В Python 3.7 и выше, словари гарантированно запоминают порядок вставки ключей. Ответ на этот вопрос кратко описывает текущее положение дел.

Таким образом, OrderedDict решение становится устаревшим, и без каких-либо инструкций импорта мы можем просто выдавать:

>>> lst = [1, 2, 1, 3, 3, 2, 4]
>>> list(dict.fromkeys(lst))
[1, 2, 3, 4]