Frage Entfernen Sie doppelte Diktat in Liste in Python


Ich habe eine Liste von Dicts, und ich möchte die Dicts mit identischen Schlüssel-Wert-Paaren entfernen.

Für diese Liste: [{'a': 123}, {'b': 123}, {'a': 123}]

Ich möchte dies zurückgeben: [{'a': 123}, {'b': 123}]

Ein anderes Beispiel:

Für diese Liste: [{'a': 123, 'b': 1234}, {'a': 3222, 'b': 1234}, {'a': 123, 'b': 1234}]

Ich möchte dies zurückgeben: [{'a': 123, 'b': 1234}, {'a': 3222, 'b': 1234}]


75
2018-02-24 07:46


Ursprung


Antworten:


Versuche dies:

[dict(t) for t in {tuple(d.items()) for d in l}]

Die Strategie besteht darin, die Liste der Wörterbücher in eine Liste von Tupeln zu konvertieren, in denen die Tupel die Elemente des Wörterbuchs enthalten. Da die Tupel gehashed werden können, können Sie mit set (Verwendung einer Verständnis festlegen hier wäre ältere Python-Alternative set(tuple(d.items()) for d in l)) und danach die Wörterbücher aus Tupeln mit neu erstellen dict.

woher:

  • l ist die ursprüngliche Liste
  • d ist eines der Wörterbücher in der Liste
  • t ist eines der Tupel, die aus einem Wörterbuch erstellt wurden

Edit: Wenn Sie die Bestellung beibehalten möchten, wird das oben genannte Einzeiler nicht funktionieren set werde das nicht tun. Mit ein paar Zeilen Code können Sie das aber auch tun:

l = [{'a': 123, 'b': 1234},
        {'a': 3222, 'b': 1234},
        {'a': 123, 'b': 1234}]

seen = set()
new_l = []
for d in l:
    t = tuple(d.items())
    if t not in seen:
        seen.add(t)
        new_l.append(d)

print new_l

Beispielausgabe:

[{'a': 123, 'b': 1234}, {'a': 3222, 'b': 1234}]

Hinweis: Wie von @alexis gezeigt, kann es vorkommen, dass zwei Wörterbücher mit denselben Schlüsseln und Werten nicht zum selben Tupel führen. Das könnte passieren, wenn sie einen anderen Verlauf des Hinzufügen / Entfernens von Schlüsseln durchlaufen. Wenn dies für Ihr Problem der Fall ist, dann überlegen Sie sich, ob Sie sortieren möchten d.items() wie er es vorschlägt.


131
2018-02-24 07:51



Ein weiterer One-Liner basiert auf Listenkompressen:

>>> d = [{'a': 123}, {'b': 123}, {'a': 123}]
>>> [i for n, i in enumerate(d) if i not in d[n + 1:]]
[{'b': 123}, {'a': 123}]

Hier, da wir es benutzen können dict Im Vergleich behalten wir nur die Elemente, die nicht im Rest der ursprünglichen Liste enthalten sind (dieser Begriff ist nur über den Index zugänglich n, daher die Verwendung von enumerate).


28
2018-02-24 09:05



Manchmal sind alte Loops immer noch nützlich. Dieser Code ist etwas länger als jcollado, aber sehr einfach zu lesen:

a = [{'a': 123}, {'b': 123}, {'a': 123}]
b = []
for i in range(0, len(a)):
    if a[i] not in a[i+1:]:
        b.append(a[i])

11
2018-02-24 08:10



Andere Antworten funktionieren nicht, wenn Sie geschachtelte Wörterbücher wie deserialisierte JSON-Objekte verwenden. Für diesen Fall könnten Sie verwenden:

import json
set_of_jsons = {json.dumps(d, sort_keys=True) for d in X}
X = [json.loads(t) for t in set_of_jsons]

8
2017-08-02 13:52



Wenn du den Orden erhalten willst, kannst du es tun

from collections import OrderedDict
print OrderedDict((frozenset(item.items()),item) for item in data).values()
# [{'a': 123, 'b': 1234}, {'a': 3222, 'b': 1234}]

Wenn die Reihenfolge keine Rolle spielt, können Sie es tun

print {frozenset(item.items()):item for item in data}.values()
# [{'a': 3222, 'b': 1234}, {'a': 123, 'b': 1234}]

7
2018-04-29 07:52



Sie können ein Set verwenden, aber Sie müssen die Dicts in einen hashbaren Typ umwandeln.

seq = [{'a': 123, 'b': 1234}, {'a': 3222, 'b': 1234}, {'a': 123, 'b': 1234}]
unique = set()
for d in seq:
    t = tuple(d.iteritems())
    unique.add(t)

Unique ist jetzt gleich

set([(('a', 3222), ('b', 1234)), (('a', 123), ('b', 1234))])

Um dicts zurück zu bekommen:

[dict(x) for x in unique]

0
2018-02-24 08:03



Keine universelle Antwort, aber wenn deine Liste zufällig ist sortiert durch einen Schlüssel, so:

l=[{'a': {'b': 31}, 't': 1},
   {'a': {'b': 31}, 't': 1},
 {'a': {'b': 145}, 't': 2},
 {'a': {'b': 25231}, 't': 2},
 {'a': {'b': 25231}, 't': 2}, 
 {'a': {'b': 25231}, 't': 2}, 
 {'a': {'b': 112}, 't': 3}]

dann ist die Lösung so einfach wie:

import itertools
result = [a[0] for a in itertools.groupby(l)]

Ergebnis:

[{'a': {'b': 31}, 't': 1},
{'a': {'b': 145}, 't': 2},
{'a': {'b': 25231}, 't': 2},
{'a': {'b': 112}, 't': 3}]

Funktioniert mit verschachtelten Wörterbüchern und bewahrt (offensichtlich) die Reihenfolge.


0
2018-06-14 07:49



Wenn die Verwendung eines Drittanbieter-Pakets in Ordnung wäre, könnten Sie es verwenden iteration_utilities.unique_everseen:

>>> from iteration_utilities import unique_everseen
>>> l = [{'a': 123}, {'b': 123}, {'a': 123}]
>>> list(unique_everseen(l))
[{'a': 123}, {'b': 123}]

Es behält die Reihenfolge der ursprünglichen Liste bei und kann auch nicht abspeicherbare Elemente wie Wörterbücher behandeln, indem es auf einen langsameren Algorithmus zurückgreift (O(n*m) woher n sind die Elemente in der ursprünglichen Liste und m die einzigartigen Elemente in der ursprünglichen Liste statt O(n)). Wenn sowohl Schlüssel als auch Werte hashbar sind, können Sie die key Argument dieser Funktion zum Erstellen von hashbaren Elementen für den "Eindeutigkeitstest" (damit es in O(n)).

Im Fall eines Dictionary (das unabhängig von der Reihenfolge vergleicht) müssen Sie es einer anderen Datenstruktur zuordnen, die beispielsweise vergleichbar ist frozenset:

>>> list(unique_everseen(l, key=lambda item: frozenset(item.items())))
[{'a': 123}, {'b': 123}]

Beachten Sie, dass Sie kein einfaches verwenden sollten tupleAnsatz (ohne Sortierung), weil gleiche Wörterbücher nicht notwendigerweise die gleiche Reihenfolge haben (selbst in Python 3.7) Anzeigenauftrag - nicht absolute Reihenfolge - ist garantiert):

>>> d1 = {1: 1, 9: 9}
>>> d2 = {9: 9, 1: 1}
>>> d1 == d2
True
>>> tuple(d1.items()) == tuple(d2.items())
False

Und selbst das Sortieren des Tupels funktioniert möglicherweise nicht, wenn die Schlüssel nicht sortierbar sind:

>>> d3 = {1: 1, 'a': 'a'}
>>> tuple(sorted(d3.items()))
TypeError: '<' not supported between instances of 'str' and 'int'

Benchmark

Ich dachte, es wäre nützlich zu sehen, wie sich die Leistung dieser Ansätze vergleicht, also habe ich einen kleinen Benchmark gemacht. Die Benchmark-Graphen sind Zeit und Listengröße basierend auf einer Liste, die keine Duplikate enthält (die willkürlich ausgewählt wurde, die Laufzeit ändert sich nicht signifikant, wenn ich einige oder viele Duplikate hinzufüge). Es ist ein Protokoll-Log-Diagramm, so dass der gesamte Bereich abgedeckt ist.

Die absoluten Zeiten:

enter image description here

Die Timings relativ zum schnellsten Ansatz:

enter image description here

Der zweite Ansatz von das Auge ist hier am schnellsten. Das unique_everseen Annäherung mit dem key Funktion ist auf dem zweiten Platz, aber es ist der schnellste Ansatz, der Ordnung erhält. Die anderen Ansätze von jcollado und das Auge sind fast so schnell. Der Ansatz mit unique_everseen ohne Schlüssel und die Lösungen von Emmanuel und Scorpil sind für lange Listen sehr langsam und verhalten sich viel schlechter O(n*n) Anstatt von O(n). stpks Ansatz mit json ist nicht O(n*n) aber es ist viel langsamer als das ähnliche O(n) Ansätze.

Der Code zum Reproduzieren der Benchmarks:

from simple_benchmark import benchmark
import json
from collections import OrderedDict
from iteration_utilities import unique_everseen

def jcollado_1(l):
    return [dict(t) for t in {tuple(d.items()) for d in l}]

def jcollado_2(l):
    seen = set()
    new_l = []
    for d in l:
        t = tuple(d.items())
        if t not in seen:
            seen.add(t)
            new_l.append(d)
    return new_l

def Emmanuel(d):
    return [i for n, i in enumerate(d) if i not in d[n + 1:]]

def Scorpil(a):
    b = []
    for i in range(0, len(a)):
        if a[i] not in a[i+1:]:
            b.append(a[i])

def stpk(X):
    set_of_jsons = {json.dumps(d, sort_keys=True) for d in X}
    return [json.loads(t) for t in set_of_jsons]

def thefourtheye_1(data):
    return OrderedDict((frozenset(item.items()),item) for item in data).values()

def thefourtheye_2(data):
    return {frozenset(item.items()):item for item in data}.values()

def iu_1(l):
    return list(unique_everseen(l))

def iu_2(l):
    return list(unique_everseen(l, key=lambda inner_dict: frozenset(inner_dict.items())))

funcs = (jcollado_1, Emmanuel, stpk, Scorpil, thefourtheye_1, thefourtheye_2, iu_1, jcollado_2, iu_2)
arguments = {2**i: [{'a': j} for j in range(2**i)] for i in range(2, 12)}
b = benchmark(funcs, arguments, 'list size')

%matplotlib widget
import matplotlib as mpl
import matplotlib.pyplot as plt
plt.style.use('ggplot')
mpl.rcParams['figure.figsize'] = '8, 6'

b.plot(relative_to=thefourtheye_2)

Der Vollständigkeit halber ist das Timing für eine Liste, die nur Duplikate enthält:

# this is the only change for the benchmark
arguments = {2**i: [{'a': 1} for j in range(2**i)] for i in range(2, 12)}

enter image description here

Die Zeiten ändern sich nicht signifikant außer für unique_everseen ohne key Funktion, die in diesem Fall die schnellste Lösung ist. Dies ist jedoch nur der beste Fall (also nicht repräsentativ) für diese Funktion mit nicht abspeicherbaren Werten, da die Laufzeit von der Anzahl der eindeutigen Werte in der Liste abhängt: O(n*m) was in diesem Fall nur 1 ist und somit hineinläuft O(n).


Haftungsausschluss: Ich bin der Autor von iteration_utilities.


0
2017-07-17 19:43



Wenn Sie Pandas in Ihrem Arbeitsablauf verwenden, besteht eine Möglichkeit darin, eine Liste von Wörterbüchern direkt an die pd.DataFrame Konstrukteur. Dann benutze drop_duplicates und to_dict Methoden für das gewünschte Ergebnis.

import pandas as pd

d = [{'a': 123, 'b': 1234}, {'a': 3222, 'b': 1234}, {'a': 123, 'b': 1234}]

d_unique = pd.DataFrame(d).drop_duplicates().to_dict('records')

print(d_unique)

[{'a': 123, 'b': 1234}, {'a': 3222, 'b': 1234}]

0
2017-08-01 13:34