Entfernt Duplikate aus einer Liste von Listen
Habe ich eine Liste von Listen in Python:
k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]
Und ich wollen zum entfernen doppelter Elemente aus. War, wenn es eine normale Liste nicht Listen, ich könnte verwendet werden set
. Aber schade, dass die Liste nicht hashable und nicht eine Menge von Listen. Nur von Tupeln. So kann ich alle Listen in Tupel verwenden und wieder zu Listen. Aber das ist nicht schnell.
Wie kann dies in die effizienteste Art und Weise?
Dem Ergebnis der oben genannten Liste sollten sein:
k = [[5, 6, 2], [1, 2], [3], [4]]
I don ' T care zu bewahren, um.
Hinweis: diese Frage ist ähnlich, aber nicht ganz das, was ich brauche. Gesucht SO aber nicht finden Sie genaue doppelte.
Benchmarking:
import itertools, time
class Timer(object):
def __init__(self, name=None):
self.name = name
def __enter__(self):
self.tstart = time.time()
def __exit__(self, type, value, traceback):
if self.name:
print '[%s]' % self.name,
print 'Elapsed: %s' % (time.time() - self.tstart)
k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [5, 2], [6], [8], [9]] * 5
N = 100000
print len(k)
with Timer('set'):
for i in xrange(N):
kt = [tuple(i) for i in k]
skt = set(kt)
kk = [list(i) for i in skt]
with Timer('sort'):
for i in xrange(N):
ks = sorted(k)
dedup = [ks[i] for i in xrange(len(ks)) if i == 0 or ks[i] != ks[i-1]]
with Timer('groupby'):
for i in xrange(N):
k = sorted(k)
dedup = list(k for k, _ in itertools.groupby(k))
with Timer('loop in'):
for i in xrange(N):
new_k = []
for elem in k:
if elem not in new_k:
new_k.append(elem)
"loop-in" (quadratische Methode) am schnellsten von allen für kurze Listen. Für lange Listen, es ist schneller als alle außer groupby-Methode. Macht das Sinn?
Für kurze Liste (die in der "code"), 100000 Iterationen:
[set] Elapsed: 1.3900001049
[sort] Elapsed: 0.891000032425
[groupby] Elapsed: 0.780999898911
[loop in] Elapsed: 0.578000068665
Für längere Liste (die in der code dupliziert 5 mal):
[set] Elapsed: 3.68700003624
[sort] Elapsed: 3.43799996376
[groupby] Elapsed: 1.03099989891
[loop in] Elapsed: 1.85900020599
es scheint nur, wie zu viel kopieren werden die smart-Methode. sorry, Bauchgefühl. kopieren Sie die Listen Tupel, dann ins set und dann zurück auf die Liste der Listen (Kopie wieder Tupeln, Listen)
das ist nicht, wie Python funktioniert, nichts wird kopiert, nur neue Behälter für die vorhandenen Elemente ( obwohl für ints, es ist so ziemlich das gleiche )
1. die timings für die Methoden mit Sortierung sind Sie entlüftet werden, denn "k" ist der rebound, um die sortierte Variante. 2. Die Letzte Methode ist schneller, da die Art der Erzeugung der Testdaten lässt Sie mit höchstens 4 Elementen. Versuchen sth. wie K = [[int(u) für u in str(random.randrange(1, 1000))] for _ in range(100)]
behoben, danke. aber immer noch der loop-Methode ist schnell, auch wenn es nur ein Duplikat in der Liste der 10
InformationsquelleAutor zaharpopov | 2010-02-06
Du musst angemeldet sein, um einen Kommentar abzugeben.
itertools
bietet oft die Schnellste und leistungsstärkste Lösungen, um diese Art von Problemen, und ist gut lohnt sich auskennen!-)Bearbeiten: wie ich schon erwähnt in einem Kommentar, normalen Optimierungs-Anstrengungen konzentrieren sich auf die großen Eingänge (die big-O-Ansatz), weil es so viel einfacher, dass es bietet eine gute Rendite über die Bemühungen. Aber manchmal (im wesentlichen für "tragisch entscheidende Engpässe" im tiefen inneren Schleifen der code, der die Grenzen der Leistungsfähigkeit und Grenzen), die man brauchen kann um in viel mehr detail, die Bereitstellung von Wahrscheinlichkeitsverteilungen, die Entscheidung über die performance-Maßnahmen zu optimieren (vielleicht die Obere Grenze oder die 90te Perzentile ist wichtiger als ein Mittelwert oder median, je nach der eigenen apps), die möglicherweise-Heuristik prüft beim start, wählen Sie verschiedene algorithmen, die je nach input-Daten, Eigenschaften, und so weiter.
Sorgfältige Messungen von "Punkt" Leistung " (code vs code B für ein bestimmtes input) sind ein Teil dieser extrem teurer Prozess, und die standard-Bibliothek Modul
timeit
hilft hier. Jedoch, es ist einfacher, es an einem shell-prompt. Zum Beispiel, hier ist eine kurze Modul zu präsentieren, die den Allgemeinen Ansatz für dieses problem, speichern Sie es alsnodup.py
:Hinweis: die sanity-check (durchgeführt, wenn Sie nur tun
python nodup.py
) und die grundlegenden hochziehen Technik (kontinuierliche Globale Namen lokale, um jede Funktion für Geschwindigkeit), um die Dinge auf gleicher Augenhöhe.Nun können wir die Kontrollen auf die kleine Beispiel-Liste:
bestätigt, dass der quadratische Ansatz hat kleine genug Konstanten, um es attraktiver für kleine Listen mit wenigen duplizierte Werte. Mit einer kurzen Liste ohne Duplikate:
dem quadratischen Ansatz ist nicht schlecht, aber die Art und groupby sind besser. Etc, etc.
Wenn (wie die obsession mit der performance schlägt) diese operation ist bei einer core-innere Schleife von Ihr an-die-Grenzen-Anwendung, es ist einen Versuch Wert, die gleichen tests auf anderen repräsentativen input-Proben, möglicherweise erkennen einige einfache Maßnahme könnte heuristisch lassen Sie wählen eine oder der andere Ansatz (aber das Maß muss schnell sein, natürlich).
Es ist auch eine überlegung Wert halten, eine andere Darstellung für
k
-- warum muss es sein, eine Liste von Listen eher als eine Menge von Tupeln, die in den ersten Platz? Wenn die doppelte Entfernung Aufgabe ist Häufig, und die Profilerstellung zeigt, dass es die Leistung des Programms Engpass, halten eine Menge von Tupeln die ganze Zeit und bekommen eine Liste von Listen aus es nur, wenn und wo er gebraucht werden könnte insgesamt schneller, zum Beispiel.seltsam diese ist langsamer als eine naive quadratische Methode für kürzere Listen (siehe Frage Bearbeiten)
es ist auf diese Weise nur in deinem speziellen Fall, cf. mein Kommentar zu der Frage.
geben Sie eine Wahrscheinlichkeitsverteilung der Liste und Unterliste Längen und chance von Dubletten, ist es möglich (mit großen Aufwand) zu berechnen/Messen Sie die Laufzeiten Wahrscheinlichkeitsverteilung für jede gegebene code und optimieren, was zu Messen man braucht (median, Mittelwert, 90-Perzentile, was auch immer). Es ist kaum je gemacht, weil Sie von sehr niedrigen ROI: in der Regel konzentriert sich auf die viel-einfacher, bei großen Eingängen (der big-O-Ansatz), wo schlechter als die algorithmen würde wirklich wehtun, Leistung schrecklich. Und ich sehe nicht, Sie legen Sie eine beliebige Wahrscheinlichkeitsverteilungen in Ihrem Q sowieso;-).
tolle Antwort, danke
InformationsquelleAutor Alex Martelli
Ich weiß nicht, ob es unbedingt schneller, aber Sie haben nicht zu verwenden, um Tupel und sets.
Könnte man leicht testen, die schreiben beide deduping Methoden, erzeugen einige zufällige Listen mit
random
, und auch die Zeit mittime
.Sie Recht, diese Tat scheint schneller
InformationsquelleAutor danben
Es manuell zu tun, erstellen Sie eine neue
k
Liste und hinzufügen von Einträgen nicht gefunden bisher:Einfach zu begreifen, und Sie erhalten die Reihenfolge des ersten Vorkommens der einzelnen Elemente sollte das nützlich sein, aber ich denke, es ist der quadratische Komplexität, die Sie suchen ganz
new_k
für jedes element.Ich vermute, dass diese Methode nicht schneller sein für sehr lange Listen. Es hängt davon ab, Ihre Bewerbung: wenn Sie wirklich nur sechs-element-Listen mit zwei Duplikate dann ist jede Lösung ist wahrscheinlich schnell genug sein, und Sie sollten gehen Sie mit den klarsten code.
Es ist nicht quadratisch in Ihre benchmark, weil Sie duplizieren die gleiche Liste über und über. Sie sind benchmarking mit einem linearen Ecke Fall.
k = ([[1, 2], [4], [5, 6, 2], [1, 2], [3], [5, 2], [6], [8], [9]] +[[x] for x in range(1000)]) *5
wird zeigen, bis das quadratische Verhalten schönInformationsquelleAutor Paul Stephenson
Sogar Ihre "lange" Liste ist ziemlich kurz. Auch, habt Ihr Sie ausgewählt, um die tatsächlichen Daten? Die Leistung variiert mit dem, was diese Daten tatsächlich Aussehen. Zum Beispiel, Sie haben eine kurze Liste über wiederholt und über eine längere Liste. Dies bedeutet, dass die quadratische Lösung ist linear in Ihren benchmarks, aber nicht in der Realität.
Tatsächlich-große Listen, der set-code ist Ihre beste Wette—es ist linear (obwohl der Platz-hungrig). Die Art und groupby-Methoden sind O(n log n) und die Schleife in der Methode ist offensichtlich quadratisch, so dass Sie wissen, wie diese Waage als n wird wirklich groß. Wenn dies die tatsächliche Größe der Daten, die Sie analysieren, dann who cares? Es ist winzig.
Ich bin im übrigen sehen einen deutlichen Geschwindigkeitszuwachs, wenn ich nicht die form einer intermediate-Liste um den Satz, das heißt, wenn ich ersetzen
mit
Die wirkliche Lösung kann davon abhängen, weitere Informationen: Sind Sie sicher, dass eine Liste von Listen ist wirklich die Vertretung, die Sie brauchen?
InformationsquelleAutor Mike Graham
Liste der Tupel und die {} kann verwendet werden, um Duplikate entfernen
InformationsquelleAutor SuperNova
Alle
set
-bezogene Lösungen, um dieses problem so weit erforderlich eine ganzeset
vor der iteration.Ist es möglich zu machen, so faul, und zur gleichen Zeit zu bewahren, um, durch Durchlaufen der Liste von Listen und das hinzufügen zu einer "gesehen"
set
. Dann liefert nur eine Liste, wenn es nicht gefunden in dieser trackerset
.Diese
unique_everseen
Rezept ist erhältlich in denitertools
docs. Es ist auch in der 3rd-party -toolz
Bibliothek:Beachten Sie, dass
tuple
Konvertierung ist notwendig, da Listen nicht hashable.InformationsquelleAutor jpp
Sollte diese Arbeit.
InformationsquelleAutor Zoe L
Anderen wahrscheinlich mehr generische und einfachere Lösung ist, um ein Wörterbuch zu erstellen kodiert, durch die string-version der Objekte und die Werte von() am Ende:
Der Haken ist, dass dies funktioniert nur für Objekte, deren string-Darstellung ist ein gut-genug eindeutigen Schlüssel (das gilt für die meisten native Objekte).
InformationsquelleAutor jacmkno
Erstellen ein Wörterbuch mit Tupel als Schlüssel, und drucken Sie die Tasten.
InformationsquelleAutor SuperNova
Seltsam, die Antworten oben entfernt die "Duplikate" aber was ist, wenn ich wollen, entfernen Sie den doppelten Wert auch??
Folgendes sollte hilfreich sein und nicht erstellen Sie ein neues Objekt im Speicher!
und o/p ist:
InformationsquelleAutor zorze