Como você remover duplicatas de uma lista, enquanto preservar a ordem?
https://stackoverflow.com/questions/480214
-
20-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Existe um built-in que remove duplicatas de lista em Python, enquanto preservar a ordem? Eu sei que eu posso usar um conjunto para remover duplicatas, mas que destrói a ordem original. Eu também sei que eu posso fazer a minha própria como esta:
def uniq(input):
output = []
for x in input:
if x not in output:
output.append(x)
return output
(graças a descontrair para que exemplo de código .)
Mas eu gostaria de me aproveitar de um built-in ou uma linguagem mais Pythonic se possível.
questão relacionada: Em Python, o que é o algoritmo mais rápido para a remoção de duplicatas de uma lista para que todos os elementos são únicos preservando fim ?
Solução
Aqui você tem algumas alternativas: http://www.peterbe.com/plog/uniqifiers- referência
Fastest um:
def f7(seq):
seen = set()
seen_add = seen.add
return [x for x in seq if not (x in seen or seen_add(x))]
Por atribuir seen.add para seen_add em vez de apenas chamar seen.add? Python é uma linguagem dinâmica, e resolver seen.add cada iteração é mais caro do que resolver uma variável local. seen.add poderia ter mudado entre as iterações, eo tempo de execução não é suficiente inteligente para descartar essa possibilidade. Para jogar pelo seguro, tem que verificar o objeto de cada vez.
Se você planeja usar essa função muito no mesmo conjunto de dados, talvez você seria melhor fora com um conjunto ordenado: http://code.activestate.com/recipes/528878/
O (1) de inserção, deleção e membro de verificação por operação.
(Small adicional nota: seen.add() sempre retorna None, de modo que o or acima é não apenas como uma maneira de tentar uma atualização de set, e não como parte integrante do teste lógico.)
Outras dicas
Editar 2016
Como Raymond apontou , em python 3.5+ onde OrderedDict é implementado em C, a abordagem compreensão da lista será mais lento que OrderedDict (a menos que você realmente precisa da lista no final - e mesmo assim, apenas se a entrada é muito curto). Portanto, a melhor solução para 3.5+ é OrderedDict.
Editar Importante 2015
Como @abarnert notas, a more_itertools biblioteca (pip install more_itertools) contém uma unique_everseen função que é construído para resolver este problema sem qualquer ilegível (not seen.add) mutações na lista compreensões. Esta também é a solução mais rápida demasiado:
>>> from more_itertools import unique_everseen
>>> items = [1, 2, 0, 1, 3, 2]
>>> list(unique_everseen(items))
[1, 2, 0, 3]
Apenas uma importação biblioteca simples e sem hacks.
Isto vem de uma implementação da receita itertools unique_everseen que parece :
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
Em Python 2.7+ o comuns aceites idioma (que funciona, mas não é otimizado para velocidade, eu iria agora usar unique_everseen ) para isso usa collections.OrderedDict :
Tempo de execução:
>>> from collections import OrderedDict
>>> items = [1, 2, 0, 1, 3, 2]
>>> list(OrderedDict.fromkeys(items))
[1, 2, 0, 3]
Isso parece muito melhor do que:
seen = set()
[x for x in seq if x not in seen and not seen.add(x)]
e não utiliza o gambiarra :
not seen.add(x)
que se baseia no fato de que set.add é um método in-place que sempre retorna None tão avalia not None para True.
nota, contudo, que a solução de corte é mais rápida em velocidade bruta que tem o mesmo tempo de execução complexidade O (N).
Em Python 2.7 , a nova maneira de remover duplicatas de uma iterable, mantendo-o na ordem original é:
>>> from collections import OrderedDict
>>> list(OrderedDict.fromkeys('abracadabra'))
['a', 'b', 'r', 'c', 'd']
Em Python 3.6 , o dict regular, tornou-se a pedidos e compacto. (Esta característica é segura para CPython e PyPy mas pode não presente em outras implementações). Isso nos dá uma nova maneira mais rápida de deduping mantendo ordem:
>>> list(dict.fromkeys('abracadabra'))
['a', 'b', 'r', 'c', 'd']
Em Python 3.7 , o dict regular é garantido para ambos solicitados em todas as implementações. Assim, a solução mais curta e mais rápida é:
>>> list(dict.fromkeys('abracadabra'))
['a', 'b', 'r', 'c', 'd']
Response to @Max: Uma vez que você passar para 3.6 ou 3.7 e utilizar o dict regular em vez de OrderedDict , você não pode realmente bater o desempenho de qualquer outra forma. O dicionário é denso e prontamente converte para uma lista com quase nenhuma sobrecarga. A lista de destino é pré-dimensionada para len (d), que guarda todas as redimensionamentos que ocorrem em uma compreensão da lista. Além disso, uma vez que a lista de chave interna é densa, copiando os ponteiros é sobre quase rápido como uma cópia lista.
sequence = ['1', '2', '3', '3', '6', '4', '5', '6']
unique = []
[unique.append(item) for item in sequence if item not in unique]
único ? ['1', '2', '3', '6', '4', '5']
from itertools import groupby
[ key for key,_ in groupby(sortedList)]
A lista não tem que mesmo ser ordenada , a condição suficiente é que valores iguais são agrupados.
Editar: Eu assumi que "preservar a ordem" implica que a lista é realmente encomendado. Se este não é o caso, então a solução de MizardX é o caminho certo.
editComunidade:. Esta é no entanto a maneira mais elegante para "duplicados elementos consecutivos compressa em um único elemento"
Não chutar um cavalo morto (esta pergunta é muito antiga e já tem um monte de boas respostas), mas aqui está uma solução usando pandas que é bastante rápido em muitas circunstâncias e é simples morto para uso.
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]
Eu acho que se você quer manter a ordem,
você pode tentar este:
list1 = ['b','c','d','b','c','a','a']
list2 = list(set(list1))
list2.sort(key=list1.index)
print list2
OR semelhante você pode fazer isso:
list1 = ['b','c','d','b','c','a','a']
list2 = sorted(set(list1),key=list1.index)
print list2
Você também pode fazer isso:
list1 = ['b','c','d','b','c','a','a']
list2 = []
for i in list1:
if not i in list2:
list2.append(i)`
print list2
Ela também pode ser escrito como este:
list1 = ['b','c','d','b','c','a','a']
list2 = []
[list2.append(i) for i in list1 if not i in list2]
print list2
Apenas para adicionar outra implementação (muito alto desempenho) da funcionalidade de um tal de um módulo externo 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]
Timings
Eu fiz alguns horários (Python 3.6) e estes mostram que é mais rápido do que todas as outras alternativas que eu testados, incluindo OrderedDict.fromkeys, f7 e 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()
E só para ter certeza que eu também fiz um teste com mais duplicatas apenas para verificar se ele faz a diferença:
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()
E um contendo apenas um valor:
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()
Em todos esses casos, a função iteration_utilities.unique_everseen é o mais rápido (no meu computador).
Esta função iteration_utilities.unique_everseen também pode lidar com valores unhashable na entrada (no entanto com uma desempenho O(n*n) em vez do desempenho O(n) quando os valores são Hashable).
>>> lst = [{1}, {1}, {2}, {1}, {3}]
>>> list(unique_everseen(lst))
[{1}, {2}, {3}]
1 Disclaimer:. Eu sou o autor desse pacote
Por outro resposta muito tarde para uma outra questão muito antiga:
O itertools receitas tem uma função que faz isso, usando a técnica de conjunto seen , mas:
- Manipula uma função
keypadrão. - não usa hacks indecorosas.
- Optimiza o loop por
seen.addpré-ligação, em vez de procurar-se que N vezes. (f7também faz isso, mas algumas versões não.) - Otimiza o loop usando
ifilterfalse, assim você só tem de varrer os elementos exclusivos em Python, em vez de todos eles. (Você ainda iterar sobre todos eles dentro deifilterfalse, é claro, mas isso é em C, e muito mais rápido.)
É realmente mais rápido do que f7? Depende de seus dados, assim você vai ter de testá-lo e ver. Se você quiser uma lista no final, f7 usa um listcomp, e não há nenhuma maneira de fazer isso aqui. (Você pode append diretamente em vez de yielding, ou você pode alimentar o gerador para a função list, mas nenhum deles pode ser tão rápido quanto o LIST_APPEND dentro de um listcomp.) De qualquer forma, normalmente, espremendo para fora de alguns microssegundos não vai ser tão importante como tendo uma função facilmente compreensível, reutilizável, já escrito que não requer DSU quando você quer decorar.
Tal como acontece com todas as receitas, é também disponível em more-iterools .
Se você quiser apenas o caso no-key, você pode simplificá-lo como:
def unique(iterable):
seen = set()
seen_add = seen.add
for element in itertools.ifilterfalse(seen.__contains__, iterable):
seen_add(element)
yield element
Em Python 3.7 e acima, os dicionários são garantida para lembrar sua ordem da chave de inserção. A resposta a esta questão resume o estado atual das coisas.
A solução OrderedDict, assim, torna-se obsoleto e sem quaisquer instruções de importação podemos simplesmente emitir:
>>> lst = [1, 2, 1, 3, 3, 2, 4]
>>> list(dict.fromkeys(lst))
[1, 2, 3, 4]
Para nenhum tipo Hashable (por exemplo lista de listas), com base em MizardX de:
def f7_noHash(seq)
seen = set()
return [ x for x in seq if str( x ) not in seen and not seen.add( str( x ) )]
O empréstimo a idéia recursiva usado em definining função nub de Haskell para listas, isso seria uma abordagem recursiva:
def unique(lst):
return [] if lst==[] else [lst[0]] + unique(filter(lambda x: x!= lst[0], lst[1:]))
por exemplo:.
In [118]: unique([1,5,1,1,4,3,4])
Out[118]: [1, 5, 4, 3]
Eu tentei-o para o cultivo de tamanhos de dados e serra sub-linear time-complexidade (não definitiva, mas sugere que isso deve ser bom para dados normal).
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
Eu também acho que é interessante que isso poderia ser facilmente generalizado para singularidade por outras operações. Como esta:
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)
Por exemplo, você poderia passar em uma função que usa a noção de arredondamento para o mesmo número inteiro como se fosse "igualdade" para fins de singularidade, como este:
def test_round(x,y):
return round(x) != round(y)
então único (some_list, test_round) iria fornecer os elementos exclusivos da lista onde singularidade não significava igualdade tradicional (que está implícito usando qualquer tipo de abordagem baseada em dict-chave baseada em conjunto ou para este problema), mas em vez destina-se a tomar apenas o primeiro elemento que rodadas para K para cada inteiro possível K que os elementos podem rodada para, por exemplo:
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]
5 x mais rápido reduzir variante, mas mais sofisticado
>>> 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]
Explicação:
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]
A resposta de MizardX dá uma boa coleção de múltiplas abordagens.
Isto é o que eu vim com pensando em voz alta:
mylist = [x for i,x in enumerate(mylist) if x not in mylist[i+1:]]
Você pode fazer referência a uma compreensão da lista, uma vez que está sendo construído pelo símbolo '_ [1]'.
Por exemplo, a seguinte função exclusiva-ifies uma lista de elementos sem alterar sua ordem, fazendo referência a sua compreensão da lista.
def unique(my_list):
return [x for x in my_list if x not in locals()['_[1]']]
Demonstração:
l1 = [1, 2, 3, 4, 1, 2, 3, 4, 5]
l2 = [x for x in l1 if x not in locals()['_[1]']]
print l2
Output:
[1, 2, 3, 4, 5]
Você poderia fazer uma espécie de feio corte compreensão da lista.
[l[i] for i in range(len(l)) if l.index(l[i]) == i]
abordagem relativamente eficaz com _sorted_ um numpy matrizes:
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]]])
Saídas:
array([ 1, 3, 8, 12])
l = [1,2,2,3,3,...]
n = []
n.extend(ele for ele in l if ele not in set(n))
A expressão gerador que utiliza a O (1) olhar para cima de um conjunto para determinar se deve ou não incluir um elemento na nova lista.
A solução recursiva simples:
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]]
Se você precisar de um forro então talvez isso iria ajudar:
reduce(lambda x, y: x + y if y[0] not in x else x, map(lambda x: [x],lst))
... deve funcionar, mas me corrija se eu estiver errado
Se você usa rotineiramente pandas , e estética é preferido sobre o desempenho, em seguida, considerar o built-in função 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
Timing:
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
Isto irá preservar a ordem ea prazo em O (n). Basicamente, a idéia é criar um buraco onde quer que haja um encontrado duplicados e afundá-lo até o fundo. faz uso de um ponteiro de leitura e escrita. sempre que um duplicado é encontrado somente os avanços ponteiro de leitura e gravação ponteiro estadias no dia entrada duplicada para substituí-lo.
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]
Uma solução sem o uso de módulos ou conjuntos importados:
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)
Dá saída:
['ask', 'not', 'what', 'your', 'country', 'can', 'do', 'for', 'you']
Um in-place método
Este método é quadrática, porque temos uma pesquisa linear na lista para cada elemento da lista (a que temos de adicionar o custo de reorganizar a lista por causa da del s).
Dito isto, é possível operar no lugar, se partimos do fim da lista e avance em direção a origem remoção de cada termo que está presente no sub-lista em sua esquerda
Esta ideia no código é simplesmente
for i in range(len(l)-1,0,-1):
if l[i] in l[:i]: del l[i]
Um teste simples da implementação
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]:
Eliminar os valores duplicados em uma seqüência, mas preservar a ordem dos itens restantes. Uso da função geral gerador de propósito.
# 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}]
lista abordagem utiliza a compreensão de ZMK que é muito rápido, ainda mantém a ordem natural. Para aplicar a caso cordas sensíveis que podem ser facilmente modificados. Isso também preserva a embalagem original.
def DelDupes(aseq) :
seen = set()
return [x for x in aseq if (x.lower() not in seen) and (not seen.add(x.lower()))]
funções intimamente associado são:
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())))
