Ich muss SHA256 Hashes von 2 ^ 25 zufälligen Strings finden. Und dann suchen Sie nach Kollision (mit Geburtstags-Paradox für die letzte, sagen wir, nur 50 Bits des Hash).
Ich speichere das string: hash-Paar in einer dict-Variablen. Sortieren Sie dann die Variable mit Werten (keine Schlüssel) und suchen Sie dann mit einer O (n) Schleife nach einer Kollision.
Das Problem ist, dass es 2 ^ 25 Strings und ihre 2 ^ 25 Hashes gibt, also enthält die dict Variable 2 ^ 50 Werte. Dies ist EXTREM Ressourcenintensiv. Also, wie mache ich das mit begrenztem RAM, etwa 1GB?
Was ich schon versucht habe:
1. Dies mit einem 6GB Swap Space ausführen. Das Programm lief über Nacht und war immer noch nicht fertig. Dies ist im Wesentlichen sogar langsamer als eine O (n_square) Suche! Die Hashes werden mit einer RAM-Nutzung von etwa 3,2 GB berechnet. Aber danach, wenn es um den Sortierbefehl geht, beginnt der verwendete RAM wieder zu schießen! Ich habe zwar die Python-Sortierung verwendet In-Place-Quicksort :(
2. Ich habe nur die Hashes gespeichert und eine Kollision gefunden. Aber die entsprechende Zeichenfolge konnte nicht gefunden werden, da sie nicht gespeichert wurde.
Ich soll keine Datenbanken benutzen, höchstens eine Textdatei, aber das hilft nicht. Außerdem bin ich ziemlich neu in Python, aber lass das nicht die Ebene deiner Antwort begrenzen.
PS: Das ist eine Aufgabe. Einige behaupten, die Kollisionen in weniger als einer Minute mit 300 MB RAM gefunden zu haben. Ich weiß nicht, ob das stimmt. Ich habe das Problem gelöst, aber die Antwort ist unerreichbar! Bei der Arbeit haben Sie gerade keinen Zugriff auf den Code. Wird bald hinzufügen.
Code:
%Vor%Ich würde für so etwas gehen:
Öffnen Sie 16 Dateien (geöffnet im binären Modus sollte in Ordnung sein; dies wird am einfachsten sein, wenn alle Ihre Strings die gleiche Länge haben). Generieren Sie Ihre Strings und Hashes und schreiben Sie sie in eine Datei, abhängig von den ersten 4 Bit des Hashs. Laden und verarbeiten Sie dann jede Datei einzeln. Dadurch wird die Speicherauslastung um den Faktor 16 reduziert. (Natürlich können Sie beliebig viele Dateien verwenden, solange Ihnen die Dateizugriffsnummern nicht ausgehen. Das Öffnen und Schließen jeder Datei bei jedem Zugriff wird ziemlich langsam.)
Wenn das Erzeugen der Strings und Hashes relativ kostengünstig ist, brauchen Sie die Dateien nicht einmal. Machen Sie einfach 16 Durchläufe, und behalten Sie in jedem Durchgang nur die Hashes, deren obere Nibbles mit der Durchlaufnummer übereinstimmen.
Eine Möglichkeit, das Problem zu lösen, besteht darin, ein sehr langes Bitfeld zu verwenden, so dass jeder Hash einer bestimmten Position in 2^25 Bits langen Speicherblock zugeordnet wird.
Eine bessere, aber nicht 100% ige Vorgehensweise zur Lösung dieser Art von Problemen findet über den Bloom-Filter oder andere probabilistische Datenstrukturen.
Ein Bloom-Filter ist eine platzsparende probabilistische Datenstruktur, die verwendet wird, um zu testen, ob ein Element Mitglied einer Menge ist. Falsche Positive sind möglich, falsche Negative hingegen nicht. d.h. eine Abfrage gibt entweder "innerhalb des Satzes (möglicherweise falsch)" oder "definitiv nicht im Satz" zurück.
Bloom-Filter haben einen starken Platzvorteil gegenüber anderen Datenstrukturen für die Darstellung von Mengen, wie z. B. selbstbalancierende binäre Suchbäume, Versuche, Hash-Tabellen oder einfache Arrays oder verknüpfte Listen der Einträge.
Ein Bloom-Filter mit 1% Fehler benötigt nur etwa 9,6 Bits pro Element - unabhängig von der Größe der Elemente.
Also werden 9,6 Bits pro 2 ^ 25 Elemente nur 38,4 MiB Speicher benötigen.
Ich denke, die Schlüsseleinblicke hier - die ich zugegeben habe, wichen mir für einige Zeit aus, bis ich ein paar Stunden später zurückkam - ist, dass der sha256 Hash Digest ein eigener Hash ist . Mit anderen Worten, Sie müssen keine zusätzliche Hashing- oder Set-Erstellung durchführen. Alles, was Sie tun müssen, ist eine benutzerdefinierte Hash-Tabelle mit dem sha256 Digest als Hash zu erstellen. Um Platz zu sparen, sollten Sie die Zeichenfolgen nicht speichern. Erstellen Sie einfach ein Bit-Array (mithilfe von Verschiebeoperationen für Ganzzahlen in einem mit table = numpy.zeros(table_size / bits_per_int + 1, dtype='i') erstellten Array von Ints), um Kollisionen zu erkennen, und speichern Sie dann kollidierende Strings in einem dict-Mapping-Hash für die Suche in einem zweiten Durchgang.
table_size sollte eine große Primzahl sein - ich wählte eine etwas größer als 2 ** 31, was für eine 268MB Tabelle sorgte - weil das nur wenige neue Kollisionen / falsch positive Ergebnisse (eingeführt durch die Modulooperation auf der Hash). Sie können die Strings selbst in einer Textdatei speichern, über die Sie iterieren können.
Für jede Zeichenfolge wäre der Index des entsprechenden Bits index = int(hashlib.sha256('foo').hexdigest(), base=16) % table_size . Dann berechne major_index = index / bits_in_int und minor_index = index % bits_in_int , verwende shift und bitweise Operationen auf minor_index , um das korrekte Bit im int at table[major_index] zu prüfen und zu speichern, und so weiter.
Führe jetzt einen Durchlauf durch die Strings durch. Wenn eine Zeichenfolge einen Hash generiert, der einem bereits gesetzten Bit entspricht, speichern Sie ein hash:string -Paar in einem Wörterbuch. Oder noch besser: Speichern Sie ein hash:[string_list] -Paar, und fügen Sie im Fall mehrerer Kollisionen neue Strings zur Liste hinzu. Für jedes kollidierende Zeichenpaar (a, b) enthält das Wörterbuch den Hash und den Wert von b. Führen Sie dann einen zweiten Durchlauf durch die Strings durch, indem Sie nacheinander jeden Hashing durchführen und das Wörterbuch für jeden Hash überprüfen. Wenn sich der Hash im Wörterbuch befindet und die Zeichenfolge nicht bereits in der entsprechenden Liste enthalten ist, fügen Sie die Zeichenfolge zur Liste hinzu. Einige der Strings im Wörterbuch entsprechen nicht echten Kollisionen. Das [string_list] für die meisten dieser Hashes wird nur ein Element lang sein, und diese hash:[string_list] -Paare können verworfen werden. Die anderen sind wahrscheinlich echte Kollisionen, die sich aus der Hash-Funktion selbst und nicht aus der Modulo-Operation ergeben. Es kann jedoch sein, dass Sie in den Fällen, in denen sowohl ein wahres als auch ein falsches positives Ergebnis vorhanden war, immer noch einige falsche positive Ergebnisse haben können. Sie müssen die resultierenden Listen auf Fehlalarme prüfen.
Der Vorschlag von BasicWolf , einen Bloom-Filter zu verwenden, ist ein guter und könnte zu einer kleineren Tabelle führen. Aber es fügt eine Menge Komplikationen hinzu; Ich habe mich nicht darum gekümmert. Ich habe die oben genannte Methode für newline-terminierte Strings von '0\n' bis '33554431\n' ausprobiert und zwei Hashes mit einer 54-Bit-Überlappung gefunden. Es dauerte 11 Minuten, und die maximale Speicherauslastung betrug etwa 350 MB (obwohl das wahrscheinlich reduziert werden könnte). Ich machte einige Profilerstellung und fand heraus, dass die meiste Zeit damit verbracht wurde, Offsets für die Bittabelle zu berechnen. Das Codieren in c würde wahrscheinlich zu einer erheblichen Beschleunigung führen, und das Vorhacken und Speichern der Hashes sowie der Strings würde ebenfalls helfen.
Tatsächlich habe ich versucht, die Strings vorzuspeichern und habe mein eher ad-hoc numpy -basiertes Bitarray durch ein bitarray vom c-basierten Erweiterungsmodul des name . Dies reduzierte die Laufzeit auf etwas mehr als 2 Minuten, während das Speicherprofil nur etwa 350 MB betrug.
Nahe genug für die Regierungsarbeit, denke ich. Da dies eine Aufgabe ist, werde ich den Code nicht veröffentlichen, aber ich bin glücklich, zusätzliche Hinweise zu geben.
Teilen Sie den Hash zum Beispiel in Gruppen von 10 Zeichen auf. Und verschachteln Sie die Werte so, dass Sie eine rekursive Suche durchführen, aber es sollte schneller sein
Tags und Links python dictionary ram hash