Erstellen von verschiedenen Hash-Funktionen für Ganzzahlen in Python?

Question

Für meine Implementierung des Minhashing-Algorithmus muss ich viele zufällige Permutationen von ganzen Zahlen machen, die mit zufälligen Hash-Funktionen (so viele wie möglich) simuliert werden. Derzeit verwenden I Hash-Funktionen der Form:

h(x) = (a*x + b) % c 

wobei a und b Zahlen zufällig erzeugt wird, und c eine Primzahl größer als die den höchsten Wert von b. Wie auch immer, der Code läuft zu langsam und es ist unmöglich, mehr als 15 solcher Hash-Funktionen in angemessener Laufzeit zu verwenden. Kann jemand andere Methoden empfehlen, zufällige Hash-Funktionen für Ganzzahlen in Python zu verwenden? In anderen Posts stieß ich auf Vorschläge für die Verwendung bitweise shuffling und XOR Operation, aber ich habe nicht vollständig verstanden, wie man so etwas implementieren sollte (ich bin relativ neu in Python).

Answer 1

Leihen von my answer auf eine ähnliche Frage, und einen kurzen Blick auf Python-Dokumentation, die zu versuchen, gültige Syntax zu erraten ...

Der Code, den Sie geschrieben in Ordnung ist, aber es ist wahrscheinlich unterliegt in mehr Genauigkeit berechnet werden als ist optimal, und es beinhaltet eine Teilung, die auch die Dinge verlangsamt.

, um es schneller zu machen, Sie c bei einer Leistung von zwei beheben können, und Sie können binäre & (und) anstelle von Modulo verwenden, die Sie ergibt dies: die die gleiche ist

h(x) = (a * x + b) & ((1 << 32) - 1) 

als:

h(x) = (a * x + b) & (4294967296 - 1) 

die gleich wie:

h(x) = (a * x + b) % 4294967296 

und Sie müssen Stellen Sie sicher, dass a eine ungerade Zahl ist (das ist alles, was nötig ist, damit es mit c co-prime wird, wenn c eine Potenz von zwei ist). In diesem Beispiel wird der Ausgabebereich auf eine 32-Bit-Ganzzahl begrenzt. Sie können das ändern, wie Sie es für richtig halten. Ich weiß nicht, was Pythons Grenzen sind.

Wenn Sie mehr Parametrisierung wünschen oder feststellen, dass die Ergebnisse nicht "zufällig" genug sind (statistische Tests würden sehr schnell fehlschlagen, aber das ist normalerweise egal), können Sie weitere Operationen hinzufügen; aber Sie können nicht mehr von diese Operationen hinzufügen, weil eine Kette von Adds und Multiplies immer nur zu einem Paar addieren und multiplizieren, so dass die zusätzlichen Operationen nichts beheben würde.

Was Sie stattdessen tun können, ist bit shifts and exclusive-or zu verwenden, um die Linearität aufzubrechen; wie folgt:

def h(x): 
    x = x^(x >> 16) 
    x = (a * x + b) & ((1 << 32) - 1) 
    x = x^(x >> 16) 
    x = (c * x + d) & ((1 << 32) - 1) 
    x = x^(x >> 16) 
    return x 

Sie können mit Variationen experimentieren, wenn Sie möchten. Wenn Sie b und d auf Null gesetzt und ändern Sie die Mitte 16-13 dann erhalten Sie die MurmurHash3 finaliser Konstruktion, die für die meisten Zwecke nahe genug, um ideal ist, sofern Sie gute Pick a und c (leider können sie nicht nur zufällig sein).