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

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

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

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

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

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

+709
источник поделиться
38 ответов
  • 1
  • 2

Здесь у вас есть несколько альтернатив: 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 выше есть только для попытки обновления набора, а не как неотъемлемая часть логического теста.)

+718
источник

Изменить 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]

Просто один простой импорт библиотеки и никаких хаков. Это происходит от реализации рецепта 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).

+326
источник
другие ответы

Связанные вопросы


Похожие вопросы

В 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), который сохраняет все размеры, которые возникают при понимании списка. Кроме того, поскольку внутренний список ключей плотен, копирование указателей почти быстро происходит в виде копии списка.

+96
источник
sequence = ['1', '2', '3', '3', '6', '4', '5', '6']
unique = []
[unique.append(item) for item in sequence if item not in unique]

unique → ['1', '2', '3', '6', '4', '5']

+40
источник

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

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]
+25
источник
from itertools import groupby
[ key for key,_ in groupby(sortedList)]

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

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

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

+23
источник

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

вы можете попробовать следующее:

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 
+22
источник

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

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

>>> lst = [1, 2, 1, 3, 3, 2, 4]
>>> list(dict.fromkeys(lst))
[1, 2, 3, 4]
+12
источник

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

В рецептах itertools есть функция, которая делает это, используя метод set seen, но:

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

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

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

Если вам просто нужен случай no- key, вы можете упростить его как:

def unique(iterable):
    seen = set()
    seen_add = seen.add
    for element in itertools.ifilterfalse(seen.__contains__, iterable):
        seen_add(element)
        yield element
+11
источник

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

enter image description here

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

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()

enter image description here

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

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()

enter image description here

Во всех этих случаях функция 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}]

1 Отказ от ответственности: я автор этого пакета.

+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 ) )]
+6
источник

Заимствуя рекурсивную идею, используемую для определения функции Haskell 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)

тогда уникальный (some_list, test_round) предоставит уникальные элементы списка, где уникальность больше не означает традиционное равенство (что подразумевается с помощью любого подхода, основанного на наборе или на основе dict-key), но вместо этого предназначенный для того, чтобы взять только первый элемент, который округляется до 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]
+3
источник

5 x быстрее сокращают вариант, но сложнее

>>> 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]
+3
источник

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

Это то, что я придумал, думая вслух:

mylist = [x for i,x in enumerate(mylist) if x not in mylist[i+1:]]
+2
источник

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

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]
+2
источник

Относительно эффективный подход с массивами _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])
+1
источник

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

[l[i] for i in range(len(l)) if l.index(l[i]) == i]
+1
источник
l = [1,2,2,3,3,...]
n = []
n.extend(ele for ele in l if ele not in set(n))

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

+1
источник

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

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]]
+1
источник

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

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

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

0
источник

Это быстро, но...

l = list(set(l))

... это не работает, если элементы списка не хешируются.

Более общий подход:

l = reduce(lambda x, y: x if y in x else x + [y], l, [])

... он должен работать для всех случаев.

0
источник

Поместите дубликат в список и сохраните uniques в списке источников:

>>> list1 = [ 1,1,2,2,3,3 ]
>>> [ list1.pop(i) for i in range(len(list1))[::-1] if list1.count(list1[i]) > 1 ]
[1, 2, 3]

Я использую [::-1] для списка чтения в обратном порядке.

0
источник

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

Скажем, у вас есть цикл, который вытаскивает данные и использует list1.append(item)...

list1 = [0, 2, 4, 9]
for x in range(0, 7):
  list1.append(x)

Это дает вам несколько дубликатов:  [0, 2, 4, 9, 0, 1, 2, 3, 4, 5, 6]

Но если вы это сделали:

list1 = [0, 2, 4, 9]
for x in range(0, 7)
  if x not in list1:
    list1.append(x)

Вы не получаете дубликатов и порядок сохраняется:  [0, 2, 4, 9, 1, 3, 5, 6]

0
источник

Вот рекурсивная версия для O (N 2):

def uniquify(s):
    if len(s) < 2:
        return s
    return uniquify(s[:-1]) + [s[-1]] * (s[-1] not in s[:-1])
0
источник

Если вы обычно используете 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
0
источник

это сохранит порядок и запустится в 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]
0
источник

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

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']
0
источник

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

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

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

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

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]:                                                                                                                             
0
источник

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

# 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}]
0
источник

Подход 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())))
0
источник
  • 1
  • 2

Посмотрите другие вопросы по меткам или Задайте вопрос