Как вы удаляете дубликаты из списка, сохраняя порядок?

Question

Есть ли встроенная функция, которая удаляет дубликаты из списка в Python, сохраняя при этом порядок? Я знаю, что могу использовать набор для удаления дубликатов, но это разрушает первоначальный порядок. Я также знаю, что я могу катиться так:

def uniq(input):
  output = []
  for x in input:
    if x not in output:
      output.append(x)
  return output

(Спасибо за за это образец кода .)

Но я бы хотел использовать встроенную или более Pythonic идиому, если это возможно.

Смежный вопрос: В Python, какой самый быстрый алгоритм удаления дубликатов из списка, чтобы все элементы были уникальными при сохранении порядка ?

Answer 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 на seen_add вместо простого вызова seen.add? Python является динамическим языком, и разрешение seen.add каждой итерации обходится дороже, чем разрешение локальной переменной. seen.add мог бы измениться между итерациями, и среда выполнения недостаточно умна, чтобы исключить это. Чтобы не рисковать, он должен каждый раз проверять объект.

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

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

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

Answer 2

Редактировать 2016

Как указал Раймонд , в python 3.5+, где OrderedDict реализован на C, подход к пониманию списка будет медленнее, чем OrderedDict (если только вам не нужен список в конце - и даже тогда, только если ввод очень короткий). Так что лучшее решение для 3.5+ это OrderedDict.

Важное редактирование 2015

Как отмечает @ 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

---

В Python 2.7+ принял общую идиому (которая работает, но не оптимизирована для скорости, я бы сейчас использовал unique_everseen) для этого использования collections.OrderedDict

Время выполнения: O (N)

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

Это выглядит намного лучше, чем:

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

и не использует безобразный хак :

not seen.add(x)

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

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

Answer 3

В Python 2.7 новый способ удаления дубликатов из итерируемого при сохранении его в исходном порядке:

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

В Python 3.5 OrderedDict имеет реализацию на языке C. Мои данные показывают, что сейчас это самый быстрый и самый короткий из различных подходов для Python 3.5.

В Python 3.6 обычный dict стал упорядоченным и компактным. (Эта функция поддерживается для CPython и PyPy, но может отсутствовать в других реализациях). Это дает нам самый быстрый способ дедупликации при сохранении порядка:

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

В Python 3.7 обычный dict гарантированно упорядочен для всех реализаций. Итак, самое короткое и быстрое решение:

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

---

Реакция на @max: как только вы перейдете на 3,6 или 3,7 и будете использовать обычный dict вместо OrderedDict , вы не сможете по-настоящему побить производительность любым другим способом. Словарь плотный и легко преобразуется в список практически без накладных расходов. Целевой список предварительно масштабируется до len (d), который сохраняет все изменения, которые происходят при понимании списка. Кроме того, поскольку внутренний список ключей плотный, копирование указателей происходит почти так же быстро, как копирование списка.

Answer 4

sequence = ['1', '2', '3', '3', '6', '4', '5', '6']
unique = []
[unique.append(item) for item in sequence if item not in unique]

уникальный → ['1', '2', '3', '6', '4', '5']

Answer 5

from itertools import groupby
[ key for key,_ in groupby(sortedList)]

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

Редактировать: я предположил, что "сохранение порядка" подразумевает, что список фактически упорядочен. Если это не так, то решение от MizardX является правильным.

Редактирование сообщества: это, однако, самый элегантный способ «сжать повторяющиеся последовательные элементы в один элемент».

Answer 6

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

import pandas as pd

my_list = [0, 1, 2, 3, 4, 1, 2, 3, 5]

>>> pd.Series(my_list).drop_duplicates().tolist()
# Output:
# [0, 1, 2, 3, 4, 5]

Answer 7

Я думаю, если вы хотите поддерживать порядок,

Вы можете попробовать это:

list1 = ['b','c','d','b','c','a','a']    
list2 = list(set(list1))    
list2.sort(key=list1.index)    
print list2

ИЛИ аналогично вы можете сделать это:

list1 = ['b','c','d','b','c','a','a']  
list2 = sorted(set(list1),key=list1.index)  
print list2 

Вы также можете сделать это:

list1 = ['b','c','d','b','c','a','a']    
list2 = []    
for i in list1:    
    if not i in list2:  
        list2.append(i)`    
print list2

Это также можно записать так:

list1 = ['b','c','d','b','c','a','a']    
list2 = []    
[list2.append(i) for i in list1 if not i in list2]    
print list2 

Answer 8

Еще один очень поздний ответ на еще один очень старый вопрос:

Рецепты itertools имеют функцию, которая делает это, используя методику набора seen, но:

• Обрабатывает стандартную key функцию.
• Не использует непристойных хаков.
• Оптимизирует цикл, предварительно связав seen.add вместо того, чтобы искать его N раз. (f7 также делает это, но некоторые версии этого не делают.)
• Оптимизирует цикл с помощью ifilterfalse, поэтому вам нужно только перебирать уникальные элементы в Python, а не все из них. (Конечно, вы все еще перебираете все из них внутри ifilterfalse, но это в C и намного быстрее.)

Это на самом деле быстрее, чем f7? Это зависит от ваших данных, поэтому вам придется проверить это и посмотреть. Если вам нужен список в конце, f7 использует listcomp, и здесь нет способа сделать это. (Вы можете напрямую append вместо yield ing, или вы можете подать генератор в функцию list, но ни один из них не может быть таким же быстрым, как LIST_APPEND внутри listcomp.) Во всяком случае, обычно, выжимая несколько микросекунд не будут столь важны, как наличие легко понятной, многократно используемой, уже написанной функции, которая не требует DSU, когда вы хотите украсить.

Как и во всех рецептах, он также доступен в more-iterools.

Если вы просто хотите использовать чехол без key, вы можете упростить его как:

def unique(iterable):
    seen = set()
    seen_add = seen.add
    for element in itertools.ifilterfalse(seen.__contains__, iterable):
        seen_add(element)
        yield element

Answer 9

Просто для добавления другой (очень производительной) реализации такой функциональности из внешнего модуля ¹ : iteration_utilities.unique_everseen:

>>> from iteration_utilities import unique_everseen
>>> lst = [1,1,1,2,3,2,2,2,1,3,4]

>>> list(unique_everseen(lst))
[1, 2, 3, 4]

Задержка

Я сделал несколько таймингов (Python 3.6), и они показывают, что это быстрее, чем все другие альтернативы, которые я тестировал, включая OrderedDict.fromkeys, f7 и more_itertools.unique_everseen:

%matplotlib notebook

from iteration_utilities import unique_everseen
from collections import OrderedDict
from more_itertools import unique_everseen as mi_unique_everseen

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

def iteration_utilities_unique_everseen(seq):
    return list(unique_everseen(seq))

def more_itertools_unique_everseen(seq):
    return list(mi_unique_everseen(seq))

def odict(seq):
    return list(OrderedDict.fromkeys(seq))

from simple_benchmark import benchmark

b = benchmark([f7, iteration_utilities_unique_everseen, more_itertools_unique_everseen, odict],
              {2**i: list(range(2**i)) for i in range(1, 20)},
              'list size (no duplicates)')
b.plot()

И просто чтобы убедиться, что я также провел тест с большим количеством дубликатов, просто чтобы проверить, имеет ли это значение:

import random

b = benchmark([f7, iteration_utilities_unique_everseen, more_itertools_unique_everseen, odict],
              {2**i: [random.randint(0, 2**(i-1)) for _ in range(2**i)] for i in range(1, 20)},
              'list size (lots of duplicates)')
b.plot()

И один, содержащий только одно значение:

b = benchmark([f7, iteration_utilities_unique_everseen, more_itertools_unique_everseen, odict],
              {2**i: [1]*(2**i) for i in range(1, 20)},
              'list size (only duplicates)')
b.plot()

Во всех этих случаях функция iteration_utilities.unique_everseen самая быстрая (на моем компьютере).

---

Эта функция iteration_utilities.unique_everseen также может обрабатывать нечитаемые значения на входе (однако с производительностью O(n*n) вместо производительности O(n), когда значения являются хэшируемыми).

>>> lst = [{1}, {1}, {2}, {1}, {3}]

>>> list(unique_everseen(lst))
[{1}, {2}, {3}]

---

¹ Отказ от ответственности: я являюсь автором этого пакета.

Answer 10

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

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

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