Ich habe eine CSV-Datei, von der ich doppelte Zeilen entfernen möchte, aber sie ist zu groß, um in den Speicher zu passen. Ich habe einen Weg gefunden, es zu erledigen, aber ich schätze, es ist nicht der beste Weg.
Jede Zeile enthält 15 Felder und mehrere hundert Zeichen, und alle Felder werden benötigt, um die Eindeutigkeit zu bestimmen. Anstatt die gesamte Zeile zu vergleichen, um ein Duplikat zu finden, vergleiche ich hash(row-as-a-string) , um Speicher zu sparen. Ich setze einen Filter, der die Daten in eine ungefähr gleiche Anzahl von Zeilen unterteilt (z. B. Wochentage), und jede Partition ist klein genug, dass eine Nachschlagetabelle von Hash-Werten für diese Partition in den Speicher passt. Ich durchlaufe die Datei einmal für jede Partition, suche nach eindeutigen Zeilen und schreibe sie in eine zweite Datei (Pseudocode):
Eine Möglichkeit, dies zu beschleunigen, ist die Suche nach einem besseren Filter, um die Anzahl der erforderlichen Durchgänge zu reduzieren. Angenommen, die Länge der Zeilen ist gleichmäßig verteilt, möglicherweise anstelle von
%Vor%und
%Vor%wir haben
%Vor%und
%Vor%wobei 'n' so klein ist wie der Speicher erlaubt. Aber das verwendet immer noch die gleiche Methode.
Wayne Werner bot unten eine gute praktische Lösung; Ich war neugierig, ob es eine bessere / schnellere / einfachere Möglichkeit gibt, dies aus einer Algorithmusperspektive zu tun.
P.S. Ich bin auf Python 2.5 beschränkt.
Wenn Sie eine wirklich einfache Möglichkeit haben, dies zu tun, erstellen Sie einfach eine SQLite-Datenbank:
%Vor%Dann müßten Sie sich keine Gedanken über die Vergleichslogik machen - lassen Sie sqlite sich darum kümmern. Es wird wahrscheinlich nicht viel schneller sein als die Streicher zu hashen, aber es ist wahrscheinlich viel einfacher. Natürlich würden Sie den Typ ändern, der in der Datenbank gespeichert ist, wenn Sie wollen oder nicht. Natürlich, da Sie die Daten bereits in eine Zeichenfolge konvertieren, könnten Sie stattdessen nur ein Feld haben. Viele Optionen hier.
Sie führen im Grunde eine Zusammenführung durch und entfernen doppelte Einträge.
Die Eingabe in speichergroße Stücke zu zerlegen, jedes Stück zu sortieren und dann die Stücke zu verschmelzen, während Duplikate entfernt werden, ist im Allgemeinen eine solide Idee.
Eigentlich würde ich bis zu ein paar Gigs das virtuelle Speichersystem damit umgehen lassen und einfach schreiben:
%Vor%Ihre aktuelle Methode funktioniert nicht garantiert.
Erstens gibt es die geringe Wahrscheinlichkeit, dass zwei Zeilen, die tatsächlich verschieden sind, denselben Hash-Wert erzeugen können. hash(a) == hash(b) bedeutet nicht immer a == b
Zweitens machen Sie die Wahrscheinlichkeit mit Ihrem "Reduzieren / Lambda" -Kapitel höher:
%Vor%Übrigens, würde "" .join (['foo', '1', '23']) etwas klarer sein?
BTW2, warum verwenden Sie nicht set anstelle von dict für htable ?
Hier ist eine praktische Lösung: Holen Sie sich das Paket "core utils" von der Website von GnuWin32 und installieren Sie es es. Dann:
c:\gnuwin32\bin\sort --unique -ooutfile.csv infile.csv Für jeden der Schritte 1 & amp; 3, könnten Sie ein Python-Skript oder einige der anderen GnuWin32-Dienstprogramme (Kopf, Schwanz, Tee, Katze, ...) verwenden.
Ihre ursprüngliche Lösung ist etwas inkorrekt: Sie könnten verschiedene Zeilen mit demselben Wert hashen (eine Hash-Kollision), und Ihr Code würde einen davon auslassen.
Im Hinblick auf die algorithmische Komplexität würde ich, wenn Sie relativ wenige Duplikate erwarten, die schnellste Lösung sein, die Datei zeilenweise zu scannen, den Hash jeder Zeile hinzuzufügen (wie Sie es getan haben), aber auch den Speicherort zu speichern von dieser Linie. Wenn Sie dann auf einen doppelten Hash stoßen, suchen Sie nach dem ursprünglichen Speicherort, um sicherzustellen, dass es sich um ein Duplikat und nicht nur um eine Hash-Kollision handelt. Wenn ja, suchen Sie die Zeile und überspringen Sie sie.
Übrigens, wenn die CSV-Werte normalisiert sind (dh Datensätze werden als gleich betrachtet, wenn die entsprechenden CSV-Zeilen Byte für Byte äquivalent sind), müssen Sie hier überhaupt kein CSV-Parsing einbeziehen, sondern nur mit einfachen Textzeilen arbeiten .
Da ich davon ausgehe, dass Sie dies regelmäßig tun müssen (oder Sie hätten ein einmaliges Skript gehackt) und Sie erwähnt hätten, dass Sie an einer theoretischen Lösung interessiert sind, ist hier eine Möglichkeit.
>Lesen Sie die Eingabezeilen in B-Trees, sortiert nach dem Hash-Wert jeder Eingabezeile, und schreiben Sie sie auf die Festplatte, wenn der Speicher voll ist. Wir sorgen dafür, dass auf den B-Trees die originalen Zeilen gespeichert werden, die an den Hash angehängt sind (als Set, da uns nur die einzigartigen Zeilen wichtig sind). Wenn wir ein doppeltes Element lesen, prüfen wir die Zeilen, die für das gespeicherte Element gesetzt sind, und fügen es hinzu, wenn es sich um eine neue Zeile handelt, deren Hash-Wert gleich ist.
Warum B-Bäume? Sie benötigen weniger Lesevorgänge, wenn Sie nur Teile davon im Speicher lesen können (oder möchten). Der Grad (Anzahl der Kinder) auf jedem Knoten hängt vom verfügbaren Speicher und der Anzahl der Zeilen ab, aber Sie möchten nicht zu viele Knoten haben.
Sobald wir diese B-Bäume auf der Festplatte haben, vergleichen wir das niedrigste Element von jedem von ihnen. Wir entfernen die niedrigsten von allen B-Bäumen, die sie haben. Wir fügen ihre Linien-Sets zusammen, was bedeutet, dass wir keine Duplikate mehr für diese Zeilen haben (und auch, dass wir keine Zeilen mehr haben, die auf diesen Wert hashen). Wir schreiben dann die Zeilen aus dieser Zusammenführung in die Ausgabe-CSV-Struktur.
Wir können die Hälfte des Speichers für das Lesen der B-Bäume trennen, und die Hälfte, um den ausgegebenen CSV einige Zeit im Speicher zu halten. Wir spülen den CSV auf die Festplatte, wenn seine Hälfte voll ist, und hängt an alles an, was bereits geschrieben wurde. Wie viel von jedem B-Baum, den wir in jedem Schritt lesen, kann grob berechnet werden durch (available_memory / 2) / number_of_btrees, gerundet, so dass wir vollständige Knoten lesen.
In Pseudo-Python:
%Vor%Wie wäre es mit dem heapq-Modul, Teile der Datei bis zum Speicherlimit zu lesen und die sortierten Teile auszugeben (heapq hält die Dinge immer in sortierter Reihenfolge).
Oder Sie könnten das erste Wort in einer Zeile fangen und die Datei dadurch in Stücke aufteilen. Dann können Sie die Zeilen lesen (vielleicht ".join (line.split ()), um den Abstand / Tabs in Zeile zu vereinheitlichen, wenn es OK ist, Abstand zu ändern) in alphabetischer Reihenfolge, die den Satz zwischen den Stücken löscht (Satz entfernt Duplikate), um die Dinge halb sortiert zu bekommen (Set ist nicht in Ordnung, wenn du willst, kannst du in Heap einlesen und schreiben, um sortierte Reihenfolge zu bekommen, letztes Vorkommen im Set ersetzt alte Werte wie du willst.) Alternativ kannst du das Stück auch sortieren und entfernen Sie doppelte Zeilen mit Joe Kobergs groupby Lösung. Schließlich können Sie Teile wieder zusammenfügen (Sie können natürlich das Schreiben tun, wie Sie Stück für Stück zur letzten Datei während des Sortierens von Stücken gehen)
Tags und Links python duplicates