Frage Speichereffiziente Möglichkeit, doppelte Zeilen in einer Textdatei mit C ++ zu entfernen


Was ist der effizienteste Weg, um doppelte Zeilen in einer großen Textdatei mit C ++ zu entfernen?

Lassen Sie mich klarstellen, ich frage nicht nach Code, nur nach der besten Methode. Die doppelten Zeilen sind nicht garantiert, dass sie benachbart sind. Mir ist klar, dass ein Ansatz, der für minimale Speicherauslastung optimiert ist, zu langsameren Geschwindigkeiten führen würde, aber das ist meine Einschränkung, da die Dateien viel zu groß sind.


13
2018-03-18 03:13


Ursprung


Antworten:


Ich würde jede Zeile Hash-und dann zurück zu Zeilen, die nicht-eindeutige Hashes und vergleichen sie einzeln (oder in einer gepufferten Weise). Dies würde bei Dateien mit einem relativ geringen Auftreten von Duplikaten gut funktionieren.

Wenn Sie einen Hash verwenden, können Sie den verwendeten Speicher auf einen konstanten Wert setzen (dh Sie könnten eine winzige Hash-Tabelle mit nur 256 Slots oder etwas Größerem haben. In jedem Fall kann die Speichermenge auf einen konstanten Betrag beschränkt werden. ) Die Werte in der Tabelle sind der Offset der Zeilen mit diesem Hash. Sie brauchen also nur line_count * sizeof (int) plus eine Konstante, um die Hash-Tabelle zu pflegen.

Noch einfacher (aber viel langsamer) wäre es, die gesamte Datei für jede Zeile zu scannen. aber ich bevorzuge die erste Option. Dies ist die speicherfreundlichste Option, die möglich ist. Sie müssten nur 2 Offsets und 2 Bytes speichern, um den Vergleich durchzuführen.


6
2018-03-18 03:19



So minimieren Sie die Speichernutzung:

Wenn Sie unbegrenzte (oder sehr schnelle) Platten-E / A haben, könnten Sie jede Zeile in eine eigene Datei schreiben, wobei der Dateiname der Hash-Code und ein bestimmter Bezeichner ist (oder keine Reihenfolge, wenn die Reihenfolge irrelevant ist). Auf diese Weise verwenden Sie das Dateisystem als Erweiterungsspeicher. Dies sollte viel schneller als das erneute Scannen der gesamten Datei für jede Zeile sein.

Als eine Ergänzung von dem, was diese unten gesagt haben, wenn Sie eine hohe Duplikatsrate erwarten, könnten Sie einige Schwellenwerte der Hashes sowohl im Speicher als auch in der Datei beibehalten. Dies würde viel bessere Ergebnisse für hohe Wiederholraten liefern. Da die Datei so groß ist, bezweifle ich n^2 ist in der Verarbeitungszeit akzeptabel. Meine Lösung ist O(n) in Verarbeitungsgeschwindigkeit und O(1) in Erinnerung. Es ist O(n) im zur Laufzeit benötigten Speicherplatz, die andere Lösungen jedoch nicht haben.

Es hört sich so an, als würden Sie auf eingeschränkter Hardware mit unterschiedlichen Spezifikationen laufen. Daher sollten Sie eine Reihe von Duplikat-Entfernungsalgorithmen und -profilen testen, bevor Sie entscheiden, welches für die langfristige Implementierung am besten ist.


3
2018-03-18 03:19



Sie können eine E / A-effiziente Sortierung verwenden (wie den Unix-Sortierbefehl) und dann die Datei zeilenweise lesen und jede Zeile mit der zuvor gelesenen vergleichen. Wenn die beiden gleich sind, gib nichts aus, wenn sie die Linie nicht ausgeben.

Auf diese Weise ist die vom Algorithmus verwendete Speichermenge konstant.


2
2018-03-18 03:29



Einfache Brute-Force-Lösung (sehr wenig Speicherverbrauch): Führen Sie einen n ^ 2 durch die Datei und entfernen Sie doppelte Zeilen. Geschwindigkeit: O (n ^ 2), Speicher: konstant

Schnell (aber schlecht, Speicherverbrauch): Stefan Kendalls Lösung: Hash jede Zeile, speichern Sie sie in einer Art Karte und entfernen Sie eine Zeile, die bereits existiert. Geschwindigkeit: O (n), Speicher: O (n)

Wenn Sie bereit sind, die Dateireihenfolge zu opfern (ich nehme nicht an, aber ich füge es hinzu): Sie können die Zeilen sortieren und dann Dubletten entfernen. Geschwindigkeit: O (n * log (n)), Speicher: konstant

bearbeiten: Wenn Sie die Idee nicht mögen, den Dateiinhalt zu sortieren oder eindeutige Hashes beizubehalten, aber O (n) Speicherverbrauch bewältigen können: Sie können jede Zeile mit ihrer 32-Bit- oder 64-Bit-Positionsmarkierung (abhängig von der Dateigröße) identifizieren und sortieren die Dateipositionen anstelle des Dateiinhalts.

Edit # 2: Vorbehalt: In-Memory-Sortierung Linien unterschiedlicher Länge ist schwieriger als es zu sagen, eine Reihe von Ints ... tatsächlich, darüber nachzudenken, wie die Erinnerung würde verschieben und bewegen in einem Merge-Schritt, ich bin zweites Raten meine Fähigkeit, eine Datei wie das in n * log (n) zu sortieren


2
2018-03-18 03:29



Warum nicht einfach konsultieren Knuth, Sortieren und Suchen? Das gibt Ihnen einen guten Hintergrund für eine ausgewogene Entscheidung.


2
2018-03-18 03:32