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

Question

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

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

(Благодаря размотать за это пример кода.)

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

Связанный с этим вопрос: В 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.

Однако обратите внимание, что решение hack быстрее по скорости raw, хотя оно имеет ту же сложность во время выполнения 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 вместо Упорядоченный запрет, на самом деле вы не можете превзойти производительность никаким другим способом.Словарь плотный и легко преобразуется в список практически без накладных расходов.Целевой список предварительно имеет размер 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

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

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

Просто для того, чтобы добавить еще одну (очень производительную) реализацию такой функциональности из внешнего модуля¹: 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 9

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

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

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

Действительно ли это быстрее, чем f7?Это зависит от ваших данных, поэтому вам придется протестировать их и посмотреть.Если вам нужен список в конце, f7 использует listcomp, и здесь нет никакого способа сделать это.(Вы можете напрямую append вместо того , чтобы yielding, или вы можете подключить генератор к 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 10

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

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

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

Answer 11

Для отсутствия хэшируемых типов (например,список списков), основанный на MizardX:

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

Answer 12

Заимствование рекурсивной идеи, используемой при определении Haskell's nub функция для списков, это был бы рекурсивный подход:

def unique(lst):
    return [] if lst==[] else [lst[0]] + unique(filter(lambda x: x!= lst[0], lst[1:]))

например ,:

In [118]: unique([1,5,1,1,4,3,4])
Out[118]: [1, 5, 4, 3]

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

In [122]: %timeit unique(np.random.randint(5, size=(1)))
10000 loops, best of 3: 25.3 us per loop

In [123]: %timeit unique(np.random.randint(5, size=(10)))
10000 loops, best of 3: 42.9 us per loop

In [124]: %timeit unique(np.random.randint(5, size=(100)))
10000 loops, best of 3: 132 us per loop

In [125]: %timeit unique(np.random.randint(5, size=(1000)))
1000 loops, best of 3: 1.05 ms per loop

In [126]: %timeit unique(np.random.randint(5, size=(10000)))
100 loops, best of 3: 11 ms per loop

Я также думаю, что интересно, что это может быть легко обобщено на уникальность с помощью других операций.Вот так:

import operator
def unique(lst, cmp_op=operator.ne):
    return [] if lst==[] else [lst[0]] + unique(filter(lambda x: cmp_op(x, lst[0]), lst[1:]), cmp_op)

Например, вы могли бы передать функцию, которая использует понятие округления до того же целого числа, как если бы это было "равенство" в целях уникальности, например:

def test_round(x,y):
    return round(x) != round(y)

тогда unique (some_list, test_round) предоставил бы уникальные элементы списка, где уникальность больше не означала традиционного равенства (что подразумевается при использовании любого подхода к этой проблеме на основе набора или диктанта на основе ключа), но вместо этого означало бы принимать только первый элемент, который округляется до K для каждого возможного целого числа K, до которого элементы могут округляться, например:

In [6]: unique([1.2, 5, 1.9, 1.1, 4.2, 3, 4.8], test_round)
Out[6]: [1.2, 5, 1.9, 4.2, 3]

Answer 13

вариант сокращения в 5 раз быстрее, но более сложный

>>> l = [5, 6, 6, 1, 1, 2, 2, 3, 4]
>>> reduce(lambda r, v: v in r[1] and r or (r[0].append(v) or r[1].add(v)) or r, l, ([], set()))[0]
[5, 6, 1, 2, 3, 4]

Объяснение:

default = (list(), set())
# use list to keep order
# use set to make lookup faster

def reducer(result, item):
    if item not in result[1]:
        result[0].append(item)
        result[1].add(item)
    return result

>>> reduce(reducer, l, default)[0]
[5, 6, 1, 2, 3, 4]

Answer 14

Ответ MizardX дает хорошую коллекцию из нескольких подходов.

Это то, к чему я пришел, размышляя вслух:

mylist = [x for i,x in enumerate(mylist) if x not in mylist[i+1:]]

Answer 15

Вы можете ссылаться на понимание списка при его построении с помощью символа "_[1]".
Например, следующая функция уникальна - создает список элементов без изменения их порядка, ссылаясь на понимание списка.

def unique(my_list): 
    return [x for x in my_list if x not in locals()['_[1]']]

ДЕМОНСТРАЦИЯ:

l1 = [1, 2, 3, 4, 1, 2, 3, 4, 5]
l2 = [x for x in l1 if x not in locals()['_[1]']]
print l2

Выходной сигнал:

[1, 2, 3, 4, 5]

Answer 16

Вы могли бы сделать что-то вроде уродливого взлома для понимания списка.

[l[i] for i in range(len(l)) if l.index(l[i]) == i]

Answer 17

Относительно эффективный подход с _sorted_ a numpy массивы:

b = np.array([1,3,3, 8, 12, 12,12])    
numpy.hstack([b[0], [x[0] for x in zip(b[1:], b[:-1]) if x[0]!=x[1]]])

Результаты:

array([ 1,  3,  8, 12])

Answer 18

l = [1,2,2,3,3,...]
n = []
n.extend(ele for ele in l if ele not in set(n))

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

Answer 19

Простое рекурсивное решение:

def uniquefy_list(a):
    return uniquefy_list(a[1:]) if a[0] in a[1:] else [a[0]]+uniquefy_list(a[1:]) if len(a)>1 else [a[0]]

Answer 20

Если вам нужен один вкладыш, то, возможно, это поможет:

reduce(lambda x, y: x + y if y[0] not in x else x, map(lambda x: [x],lst))

...должно сработать, но поправьте меня, если я ошибаюсь

Answer 21

Если вы регулярно используете pandas, и эстетика предпочтительнее производительности, тогда рассмотрим встроенную функцию pandas.Series.drop_duplicates:

    import pandas as pd
    import numpy as np

    uniquifier = lambda alist: pd.Series(alist).drop_duplicates().tolist()

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

    alist = np.random.randint(low=0, high=1000, size=10000).tolist()

    print uniquifier(alist) == f7(alist)  # True

Выбор времени:

    In [104]: %timeit f7(alist)
    1000 loops, best of 3: 1.3 ms per loop
    In [110]: %timeit uniquifier(alist)
    100 loops, best of 3: 4.39 ms per loop

Answer 22

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

def deduplicate(l):
    count = {}
    (read,write) = (0,0)
    while read < len(l):
        if l[read] in count:
            read += 1
            continue
        count[l[read]] = True
        l[write] = l[read]
        read += 1
        write += 1
    return l[0:write]

Answer 23

Решение без использования импортированных модулей или наборов:

text = "ask not what your country can do for you ask what you can do for your country"
sentence = text.split(" ")
noduplicates = [(sentence[i]) for i in range (0,len(sentence)) if sentence[i] not in sentence[:i]]
print(noduplicates)

Выдает результат:

['ask', 'not', 'what', 'your', 'country', 'can', 'do', 'for', 'you']

Answer 24

Метод на месте

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

Тем не менее, можно работать на месте, если мы начнем с конца списка и перейдем к источнику, удалив каждый термин, который присутствует в подсписке слева от него

Эта идея в коде просто

for i in range(len(l)-1,0,-1): 
    if l[i] in l[:i]: del l[i] 

---

Простой тест реализации

In [91]: from random import randint, seed                                                                                            
In [92]: seed('20080808') ; l = [randint(1,6) for _ in range(12)] # Beijing Olympics                                                                 
In [93]: for i in range(len(l)-1,0,-1): 
    ...:     print(l) 
    ...:     print(i, l[i], l[:i], end='') 
    ...:     if l[i] in l[:i]: 
    ...:          print( ': remove', l[i]) 
    ...:          del l[i] 
    ...:     else: 
    ...:          print() 
    ...: print(l)
[6, 5, 1, 4, 6, 1, 6, 2, 2, 4, 5, 2]
11 2 [6, 5, 1, 4, 6, 1, 6, 2, 2, 4, 5]: remove 2
[6, 5, 1, 4, 6, 1, 6, 2, 2, 4, 5]
10 5 [6, 5, 1, 4, 6, 1, 6, 2, 2, 4]: remove 5
[6, 5, 1, 4, 6, 1, 6, 2, 2, 4]
9 4 [6, 5, 1, 4, 6, 1, 6, 2, 2]: remove 4
[6, 5, 1, 4, 6, 1, 6, 2, 2]
8 2 [6, 5, 1, 4, 6, 1, 6, 2]: remove 2
[6, 5, 1, 4, 6, 1, 6, 2]
7 2 [6, 5, 1, 4, 6, 1, 6]
[6, 5, 1, 4, 6, 1, 6, 2]
6 6 [6, 5, 1, 4, 6, 1]: remove 6
[6, 5, 1, 4, 6, 1, 2]
5 1 [6, 5, 1, 4, 6]: remove 1
[6, 5, 1, 4, 6, 2]
4 6 [6, 5, 1, 4]: remove 6
[6, 5, 1, 4, 2]
3 4 [6, 5, 1]
[6, 5, 1, 4, 2]
2 1 [6, 5]
[6, 5, 1, 4, 2]
1 5 [6]
[6, 5, 1, 4, 2]

In [94]:                                                                                                                             

Answer 25

Устраните повторяющиеся значения в последовательности, но сохраните порядок остальных элементов.Использование функции генератора общего назначения.

# for hashable sequence
def remove_duplicates(items):
    seen = set()
    for item in items:
        if item not in seen:
            yield item
            seen.add(item)

a = [1, 5, 2, 1, 9, 1, 5, 10]
list(remove_duplicates(a))
# [1, 5, 2, 9, 10]



# for unhashable sequence
def remove_duplicates(items, key=None):
    seen = set()
    for item in items:
        val = item if key is None else key(item)
        if val not in seen:
            yield item
            seen.add(val)

a = [ {'x': 1, 'y': 2}, {'x': 1, 'y': 3}, {'x': 1, 'y': 2}, {'x': 2, 'y': 4}]
list(remove_duplicates(a, key=lambda d: (d['x'],d['y'])))
# [{'x': 1, 'y': 2}, {'x': 1, 'y': 3}, {'x': 2, 'y': 4}]

Answer 26

подход zmk использует понимание списка, которое выполняется очень быстро, но при этом сохраняет естественный порядок.Для применения к строкам, чувствительным к регистру, его можно легко изменить.Это также сохраняет оригинальный корпус.

def DelDupes(aseq) :
    seen = set()
    return [x for x in aseq if (x.lower() not in seen) and (not seen.add(x.lower()))]

Тесно связанными функциями являются:

def HasDupes(aseq) :
    s = set()
    return any(((x.lower() in s) or s.add(x.lower())) for x in aseq)

def GetDupes(aseq) :
    s = set()
    return set(x for x in aseq if ((x.lower() in s) or s.add(x.lower())))