Duplikate aus Datensätzen entfernen, die nicht in den Speicher passen?

Nehmen wir an, es gibt einen String-Datensatz, der nicht alle zusammen in den Speicher passen kann, und wir möchten alle Duplikate entfernen.Duplikate aus Datensätzen entfernen, die nicht in den Speicher passen?

ich suche nicht für Code, sondern der Hoffnung, jemand mich durch diese gehen kann.

Wenn ich die gesamte Datenmenge in dem Speicher passen könnte, würde ich den Satz sortieren, so iteriert Elemente durch und entfernen (wenn das aktuelle Element gleiche wie vorherige Element ist).

In diesem tatsächlichen Fall, ich dachte, laden Sie jede funktionsfähige "Chunk" des Datasets in den Speicher, sortieren Sie es, entfernen Sie Dupes, und tun Sie dies iterativ über jeden Chunk. Dies scheint ziemlich ineffizient zu sein, und es funktioniert nur, wenn ich den gesamten Datensatz in den Speicher einpassen kann, um verbleibende Duplikate in der letzten Iteration zu entfernen.

Vorschläge?

Edit: Die Art, wie ich dies früher für ein kleines Problem angegangen ist, war eine Hash-Tabelle im Speicher zu pflegen, durchlaufen jeden Teil des Datensatzes, der in den Speicher passen kann, die Zeichenfolge der Hash-Tabelle hinzufügen, wenn es nicht tut t existieren, sonst überspringen Sie es. Können wir es besser machen?

Quelle

2016-05-02 Beebunny

Wahrscheinlich nicht performant, aber: erster String bekommen, den Rest des Datensatz suchen (in Stücken oder einer nach der anderen) und Betrogenen entfernen, um zum nächsten zu bewegen, spülen, wiederholen. Das ist natürlich zu weit, und wie es zu tun ist, hängt davon ab, wo Sie die Daten tatsächlich laden, und was die Leistungsengpässe wären (würde es laden? Senden? Sortieren?). Paralellisierung kann helfen, abhängig von der Herkunft des Datensatzes – Jcl

Dies ist die Brute-Force-Lösung, die ich vermeiden möchte. – Beebunny

Nun, es werden mehr Details zum Datenursprung benötigt: Ist Ihr Datensatz sortiert? Kann der Ursprung es mithilfe von Indizes sortieren (wie eine Datenbank)? "Ein Dataset" ist einfach zu weit ... Wenn es sich bei Ihrem Dataset um einen Stream zufälliger Strings handelt, die sequentiell oder mit einem Cursor gelesen werden müssen, gibt es keine Möglichkeit, Duples außer Bruteforcing zu entfernen (zumindest bei der Anzahl der nicht gleichen Strings) passt auch nicht in den Speicher) ... wenn es indiziert oder sortiert ist, sind andere Ansätze möglich. – Jcl

Was ich suchte externe Sortierung genannt wird.

https://en.wikipedia.org/wiki/External_sorting

Auch ist meine Frage ist ein Duplikat dieser: Efficient Out-Of-Core Sorting

Quelle

2016-05-02 07:19:27 Beebunny

Wenn die Anzahl der Strings, die mehr als einmal in der Liste auftreten nicht zu groß ist dies versuchen könnte:

Annahme:
ich nehme die Anzahl der verschiedenen Strings in der Liste so klein ist, dass diese Strings in den Speicher passen.

Lösung:
Sie über die Datei laufen könnte und halten Sie einfach eine Menge aller bereits gelesenen Strings in einem Set und überspringen alle Strings lesen, die bereits im Set sind (weil sie Duplikate sind).

Quelle

2016-05-02 08:27:48 MrSmith42

Wenn der Datensatz in den Speicher passen kann, ja - prüfen Sie, ob eine Zeichenfolge in der Menge vorhanden ist (Hash-Tabelle). Wenn nicht, fügen Sie es der Karte hinzu. Wenn es bereits existiert, überspringen Sie es. Das ist jedoch NICHT die Frage. Die Frage war, mit großen Mengen zu arbeiten, die nicht in den Speicher passen. – Beebunny

@Beebunny: Soweit ich die Frage verstehe, passen alle Einträge (einschließlich der Duplikate) nicht in den Speicher. Das bedeutet nicht, dass eine Menge aller Einträge OHNE DUPLIKATE auch nicht in den Speicher passen würde. – MrSmith42

Ob der Datensatz ohne Duplikate alle gleichzeitig in den Speicher passt, ist neben dem Punkt. Die Frage bezieht sich auf das Entfernen von Duplikaten aus einem Datensatz, der nicht in den Speicher passt. Wie auch immer, es gibt einen Wiki-Link, wenn Sie an der markierten Antwort interessiert sind. – Beebunny

Duplikate aus Datensätzen entfernen, die nicht in den Speicher passen?

Antwort

Verwandte Themen