Ich habe eine Menge von vielen langen Strings, für die ich Existenzeuchen durchführen möchte. Ich brauche nicht die ganze Saite, die jemals gespeichert wurde. Soweit ich das beurteilen kann, hat die set() tatsächlich die Saite gespeichert, die viel von meinem Gedächtnis verschlingt.
Existiert eine solche Datenstruktur?
%Vor%(Meine Warteschlange wird ständig von anderen Threads gefüllt, so dass ich am Anfang keine Möglichkeit habe, sie zu deduplizieren).
Es ist sicherlich möglich, eine Reihe von Hashes zu behalten:
%Vor%Beachten Sie, dass aufgrund von Hash-Kollisionen die Wahrscheinlichkeit besteht, dass ein Element als erledigt betrachtet wird, obwohl dies nicht der Fall ist.
Wenn Sie dieses Risiko nicht akzeptieren können, müssen Sie wirklich die vollständigen Zeichenfolgen speichern, um feststellen zu können, ob Sie es schon einmal gesehen haben. Alternativ: vielleicht könnte die Verarbeitung selbst sagen?
Alternativ: Wenn Sie nicht akzeptieren können, dass die Zeichenfolgen im Speicher bleiben, behalten Sie sie in einer Datenbank oder erstellen Sie Dateien in einem Verzeichnis mit demselben Namen wie die Zeichenfolge.
Sie können speziell für diesen Zweck eine Datenstruktur namens Bloom-Filter verwenden. Eine Python-Implementierung finden Sie hier .
BEARBEITEN : Wichtige Hinweise:
Die Wahrscheinlichkeit, dass dies passiert, kann jedoch bei richtiger Anwendung auf ein Minimum reduziert werden, und deshalb halte ich diese Datenstruktur für sehr nützlich.
Wenn Sie eine Hash-Funktion verwenden (wie SHA-256, in der hashlib -Modul gefunden), um die Strings zu hashen, ist es sehr unwahrscheinlich, dass Sie doppelte finden (und wenn Sie einige finden, können Sie wahrscheinlich einen Preis gewinnen als mit den meisten kryptografischen Hash-Funktionen).
Die eingebaute Methode __hash__() garantiert nicht, dass Sie keine Duplikate haben (und da sie nur 32 Bit verwendet, ist es sehr wahrscheinlich, dass Sie einige finden).
Sie müssen die ganze Zeichenfolge kennen, um 100% Sicherheit zu haben. Wenn Sie viele Zeichenfolgen mit ähnlichen Präfixen haben, können Sie Speicherplatz sparen, indem Sie einen Trie zum Speichern der Zeichenfolgen verwenden. Wenn Ihre Strings lang sind, können Sie auch Speicherplatz sparen, indem Sie eine große Hash-Funktion wie SHA-1 verwenden, um Hash-Kollisionen so unwahrscheinlich zu machen, dass sie irrelevant sind.
Wenn Sie die Funktion process() idempotent machen können - dh, dass ein doppeltes Aufrufen eines Elements nur ein Leistungsproblem darstellt, wird das Problem viel einfacher, und Sie können verlustreiche Datenstrukturen wie Bloom-Filter verwenden.
Sie müssten darüber nachdenken, wie die Suche durchgeführt werden soll, da es zwei Methoden gibt, die die Gruppe benötigt: __hash__ und __eq__ .
Der Hash ist ein "losen Teil", den Sie mitnehmen können, aber das __eq__ ist kein loses Teil, das Sie speichern können; Sie müssen zwei Zeichenfolgen für den Vergleich haben.
Wenn Sie nur eine negative Bestätigung benötigen (dieses Element ist nicht Teil der Menge), können Sie eine Set-Sammlung, die Sie selbst implementiert haben, mit Ihren Strings füllen. Dann "finalisieren" Sie den Satz, indem Sie alle Strings außer denen mit Kollisionen entfernen ( Diese werden für eq Tests beibehalten und Sie versprechen, dem Set keine weiteren Objekte hinzuzufügen. Jetzt haben Sie einen exklusiven Test zur Verfügung .. Sie können feststellen, ob ein Objekt nicht in Ihrem Set ist . Sie können nicht sicher sein, ob "obj in Set == True" falsch positiv ist oder nicht.
Bearbeiten: Dies ist im Grunde ein Bloom-Filter, der geschickt verknüpft wurde, aber ein Bloom-Filter könnte mehr als einen Hash pro Element verwenden, was wirklich schlau ist.
Edit2: Das ist mein 3-Minuten-Bloom-Filter:
%Vor%Wie schon angedeutet, wenn die hier angebotenen Antworten (die meistens angesichts von Hash-Kollisionen ausfallen) nicht akzeptabel sind, müssten Sie eine verlustfreie Darstellung der Strings verwenden.
Pythons zlib-Modul bietet integrierte String-Komprimierungsfunktionen und könnte verwendet werden, um die Strings vor dem Einfügen in das Set vorzuverarbeiten. Beachten Sie jedoch, dass die Strings sehr lang sein müssen (was Sie anmerken) und minimale Entropie haben, um viel Speicherplatz zu sparen. Andere Komprimierungsoptionen bieten möglicherweise bessere Platzeinsparungen, und einige Python-basierte Implementierungen finden Sie hier
Tags und Links python data-structures set hash