Как вы удаляете дубликаты из списка, сохраняя порядок?
Есть ли встроенная функция, которая удаляет дубликаты из списка в Python, сохраняя при этом порядок? Я знаю, что могу использовать набор для удаления дубликатов, но это разрушает первоначальный порядок. Я также знаю, что я могу катиться так:
def uniq(input):
output = []
for x in input:
if x not in output:
output.append(x)
return output
(Спасибо, что unwind этот пример кода.)
Но я хотел бы воспользоваться встроенной или более Pythonic идиом, если это возможно.
Смежный вопрос: Какой самый быстрый алгоритм удаления дубликатов из списка в Python, чтобы все элементы были уникальными при сохранении порядка?
39 ответов
Здесь у вас есть несколько альтернатив: 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) вставка, удаление и проверка члена для каждой операции.
Редактировать 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
В питоне 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).
В 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), который сохраняет все изменения, которые происходят при понимании списка. Кроме того, поскольку внутренний список ключей плотный, копирование указателей происходит почти так же быстро, как копирование списка.
В Python 3.7 и выше словари гарантированно запоминают порядок вставки ключей. Ответ на этот вопрос обобщает текущее состояние дел.
OrderedDict Таким образом, решение становится устаревшим, и без каких-либо операторов импорта мы можем просто выдать:
>>> lst = [1, 2, 1, 3, 3, 2, 4]
>>> list(dict.fromkeys(lst))
[1, 2, 3, 4]
Не бить мертвую лошадь (этот вопрос очень старый и уже имеет много хороших ответов), но вот решение, использующее панд, которое довольно быстро во многих обстоятельствах и очень просто в использовании.
import pandas as pd
my_list = 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]
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']
from itertools import groupby
[ key for key,_ in groupby(sortedList)]
Список даже не нужно сортировать, достаточным условием является то, что равные значения сгруппированы вместе.
Изменить: я предположил, что "сохранение порядка" подразумевает, что список на самом деле упорядочен. Если это не так, то решение от MizardX является правильным.
Редактирование сообщества: это, однако, самый элегантный способ "сжать повторяющиеся последовательные элементы в один элемент".
Я думаю, если вы хотите поддерживать порядок,
Вы можете попробовать это:
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
Просто чтобы добавить другую (очень производительную) реализацию такой функциональности из внешнего модуля 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()
И просто чтобы убедиться, что я также провел тест с большим количеством дубликатов, просто чтобы проверить, имеет ли это значение:
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}]
1 Отказ от ответственности: я автор этого пакета.
Еще один очень поздний ответ на еще один очень старый вопрос:
itertools рецепты имеют функцию, которая делает это, используя seen установить технику, но:
- Ручки стандарт
keyфункция. - Не использует непристойных хаков.
- Оптимизирует цикл путем предварительной привязки
seen.addвместо того, чтобы искать его N раз. (f7также делает это, но некоторые версии этого не делают.) - Оптимизирует цикл с помощью
ifilterfalseТаким образом, вам нужно только перебрать уникальные элементы в Python, а не все из них. (Вы все еще перебираете их все внутриifilterfalse, конечно, но это в Си, и намного быстрее.)
Это на самом деле быстрее, чем f7? Это зависит от ваших данных, поэтому вам придется проверить это и посмотреть. Если вы хотите список в конце, f7 использует listcomp, и здесь нет способа сделать это. (Вы можете напрямую append вместо yield или вы можете подать генератор в 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
Для отсутствующих типов (например, списков), основанных на 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 ) )]
Вот простой способ сделать это:
list1 = ["hello", " ", "w", "o", "r", "l", "d"]
sorted(set(list1 ), key=lambda x:list1.index(x))
что дает результат:
["hello", " ", "w", "o", "r", "l", "d"]
Пользователи pandas должны проверить pandas.unique.
>>> import pandas as pd
>>> lst = [1, 2, 1, 3, 3, 2, 4]
>>> pd.unique(lst)
array([1, 2, 3, 4])
Функция возвращает массив NumPy. При необходимости вы можете преобразовать его в список с tolist метод.
В 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]
Заимствование рекурсивной идеи, использованной при определении Хаскелла 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]
Вы можете ссылаться на понимание списка, поскольку оно строится символом '_[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]
Ответ MizardX дает хорошую коллекцию нескольких подходов.
Вот что я придумал, думая вслух:
mylist = [x for i,x in enumerate(mylist) if x not in mylist[i+1:]]
Для удаления дубликатов при сохранении порядка отличное решение, предложенное в другом месте на этой странице ...
seen = set()
[x for x in seq if not (x in seen or seen.add(x))]
и его эквивалентные вариации ...
seen = set()
[x for x in seq if x not in seen and not seen.add(x)]
действительно популярны, потому что они просты, минималистичны и используют правильное хеширование для оптимальной эффективности. Основная жалоба заключается в том, что использование
not seen.add(x)как неработающее, инвариантное выражение является взломанным, раздутым и / или запутанным.
Удивительно, учитывая количество обсуждений и дебатов по этой теме, на самом деле в коде есть существенное улучшение, которое, кажется, было упущено из виду. Как показано, для каждой итерации требуется два поиска по хешу: первый для проверки членства
x not in seen а затем снова, чтобы добавить значение
seen.add(x). Второе усилие всегда бывает успешным и, как правило, является бесполезным дублированием. Поскольку общая методика здесь настолько эффективна, эти поиски хэшей будут одной из самых дорогих частей того немногое, что осталось.
Я предлагаю следующую версию, которая сокращает количество поисков хэша на итерацию вдвое - с двух до одного. Это значительно улучшает производительность и без того быстрого подхода.
seen = set()
[x for x in seq if len(seen) < len(seen.add(x) or seen)]
Что касается неприятного взлома, который теперь немного видоизменился по сравнению с предыдущим, он, похоже, доживет до следующего дня.
Относительно эффективный подход с _sorted_ 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])
Я сравнил все соответствующие ответы с perfplot и обнаружил, что
list(dict.fromkeys(data))
самый быстрый. Это также верно для небольших массивов numpy. Для больших массивов numpy,pandas.uniqueна самом деле быстрее всего.
Код для воспроизведения сюжета:
from collections import OrderedDict
from functools import reduce
from itertools import groupby
import numpy as np
import pandas as pd
import perfplot
from more_itertools import unique_everseen as ue
def dict_fromkeys(data):
return list(dict.fromkeys(data))
def unique_everseen(data):
return list(ue(data))
def seen_add(data):
seen = set()
seen_add = seen.add
return [x for x in data if not (x in seen or seen_add(x))]
def ordereddict_fromkeys(data):
return list(OrderedDict.fromkeys(data))
def pandas_drop_duplicates(data):
return pd.Series(data).drop_duplicates().tolist()
def pandas_unique(data):
return pd.unique(data)
def itertools_groupby(data):
return [key for key, _ in groupby(data)]
def reduce_tricks(data):
return reduce(
lambda r, v: v in r[1] and r or (r[0].append(v) or r[1].add(v)) or r,
data,
([], set()),
)[0]
b = perfplot.bench(
setup=lambda n: np.random.randint(100, size=n).tolist(),
kernels=[
dict_fromkeys,
unique_everseen,
seen_add,
ordereddict_fromkeys,
pandas_drop_duplicates,
pandas_unique,
reduce_tricks,
],
n_range=[2**k for k in range(20)],
)
b.save("out.png")
b.show()
Если вам нужен один лайнер, то, возможно, это поможет:
reduce(lambda x, y: x + y if y[0] not in x else x, map(lambda x: [x],lst))
... должно работать, но поправьте меня, если я ошибаюсь
Вы могли бы сделать что-то вроде уродливого взлома понимания списка.
[l[i] for i in range(len(l)) if l.index(l[i]) == i]
l = [1,2,2,3,3,...]
n = []
n.extend(ele for ele in l if ele not in set(n))
Выражение генератора, которое использует поиск O(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]]
x = [1, 2, 1, 3, 1, 4]
# brute force method
arr = []
for i in x:
if not i in arr:
arr.insert(x[i],i)
# recursive method
tmp = []
def remove_duplicates(j=0):
if j < len(x):
if not x[j] in tmp:
tmp.append(x[j])
i = j+1
remove_duplicates(i)
remove_duplicates()
Понимание одного списка строк:
values_non_duplicated = [value for index, value in enumerate(values) if value not in values[ : index]]
Просто добавьте условие, чтобы убедиться, что значение не находится на предыдущей позиции
Исключая дублирующиеся значения в последовательности, но сохраняйте порядок оставшихся элементов. Использование функции генератора общего назначения.
# 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}]
Это сохранит порядок и будет выполняться за 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]
Благодарим @wjandrea за идею метода dict.fromdict:
def solve(arr):
return list(dict.fromkeys(arr[::-1]))[::-1]
Это изменит ввод и вывод для правильной итерации.
Подход 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())))