Как мне удалить дубликаты из списка с сохранением порядка?
Как мне удалить дубликаты из списка с сохранением порядка? Использование набора для удаления дубликатов разрушает исходный порядок. Существует ли встроенная идиома Pythonic?
Переведено автоматически
Ответ 1
Здесь у вас есть несколько альтернатив: 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
приведенное выше приведено только как способ попытаться обновить набор, а не как неотъемлемая часть логического теста.)
Ответ 2
Наилучшее решение зависит от версии 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), но поскольку dict
s упорядочены для вставки, dict.fromkeys
порядок не теряется. Это медленнее, чем list(set(items))
(обычно занимает на 50-100% больше времени), но намного быстрее, чем любое другое решение для сохранения порядка (занимает примерно половину времени взломов, связанных с использованием set
s в 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 и более ранних версий, если производительность критична и сторонние модули недоступны
У вас есть два варианта:
Скопируйте и вставьте
unique_everseen
рецепт в свой код и используйте его вmore_itertools
примере вышеИспользуйте уродливые хаки, чтобы позволить одному 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
sonot None
, равноеTrue
.
Обратите внимание, что все из приведенных выше решений являются O(n)
(за исключением вызова unique_everseen
для итерации нехешируемых элементов, который является O(n²)
, в то время как другие немедленно завершились бы неудачей с TypeError
), поэтому все решения достаточно производительны, когда они не являются самым популярным путем кода. Какой из них использовать, зависит от того, на какие версии языковой спецификации / интерпретатора / модулей сторонних производителей вы можете положиться, важна ли производительность (не думайте, что это так; обычно это не так), и, самое главное, от удобочитаемости (потому что, если человек, который поддерживает этот код, позже окажется в убийственном настроении, ваша хитроумная микрооптимизация, вероятно, того не стоила).
Ответ 3
В 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']
Ответ 4
В Python 3.7 и выше, словари гарантированно запоминают порядок вставки ключей. Ответ на этот вопрос кратко описывает текущее положение дел.
Таким образом, OrderedDict
решение становится устаревшим, и без каких-либо инструкций импорта мы можем просто выдавать:
>>> lst = [1, 2, 1, 3, 3, 2, 4]
>>> list(dict.fromkeys(lst))
[1, 2, 3, 4]