Der einfachste Weg, die richtige Kademlia Eimer zu finden

Question

In dem Kademlia Protokoll Knoten-IDs sind 160-Bit-Zahlen. Knoten werden in Eimern gespeichert, Eimer 0 speichert alle Knoten, die die gleiche ID wie dieser Knoten mit Ausnahme des letzten Bit haben, Eimer 1 speichert alle Knoten, die die gleiche ID wie dieser Knoten mit Ausnahme der letzten 2 Bits haben, und so auf für alle 160 Eimer.

Was ist der schnellste Weg zu finden, die ich Eimer einen neuen Knoten in setzen sollte?

Ich habe meine Eimer einfach in einem Array gespeichert sind, und benötigen eine Methode, wie so:

Bucket[] buckets; //array with 160 items

public Bucket GetBucket(Int160 myId, Int160 otherId)
{
    //some stuff goes here
}

Der offensichtliche Ansatz ist von dem höchstwertigen Bit an der Arbeit, Stück für Stück zu vergleichen, bis ich einen Unterschied finden, ich hoffe, es ist ein besserer Ansatz auf Basis klug Bit Fummel.

Praktische Anmerkung: Meine Int160 mit 20 Elementen in einem Byte-Array gespeichert ist, Lösungen, das mit dieser Art von Struktur gut funktionieren werden bevorzugt.

Answer 1

Sie sei bereit, eine Reihe von 5 32-Bit-Integer zu beachten? (Oder 3 64-Bit-Integer)? Arbeiten mit ganzen Worten können Sie ein bessere Leistung als mit Bytes arbeiten, aber die Methode sollte in jedem Fall arbeiten.

XOR die entsprechenden Worte der beiden Knoten-IDs, mit dem höchstwertigen beginnen. Wenn das XOR-Ergebnis Null ist, bewegen sich auf das nächste höchstwertige Wort.

Ansonsten findet den höchstwertigen Bits, die in diesem XOR-Ergebnis mit dem konstante Zeit Methode von Hacker Delight. . Dieser Algorithmus führt in 32 (64), wenn das höchstwertige Bit gesetzt ist, und 1, wenn das niedrigstwertige Bit gesetzt ist, und so weiter. Dieser Index, mit dem Index des aktuellen Wortes kombiniert, wird Ihnen sagen, welches Bit unterschiedlich ist.

Answer 2

Für den Anfang können Sie Byte-für-Byte-Vergleich (oder Wort-für-Wort), und wenn Sie in diesem Byte einen Unterschied Suche finden (oder Wort) für das erste Bit der Differenz.

Es scheint mir vage unplausibel, dass zu einer Reihe von Eimern Hinzufügen eines Knotens so schnell sein wird, dass es darauf ankommt, ob Sie tun klug Bit-twiddling das erste Bit Differenz innerhalb eines Bytes (oder Wort) zu finden, oder einfach nur Churn in einer Schleife CHAR_BIT up (oder so). Möglich, aber.

Auch wenn IDs im Wesentlichen zufällig mit gleichmäßiger Verteilung ist, dann werden Sie einen Unterschied in den ersten 8 Bits über 255/256 der Zeit zu finden. Wenn alles um dich kümmern ist durchschnittlicher Fall Verhalten, nicht ungünstigsten Fall ist, dann tut nur die dumme Sache. Es sehr unwahrscheinlich ist, dass Ihre Schleife für lange laufen

Als Referenz, obwohl das erste Bit der Differenz zwischen den Zahlen x und y ist das erste Bit gesetzt in x ^ y. Wenn Sie in GNU C Programmierung wurden, könnte __builtin_clz dein Freund sein. Oder vielleicht __builtin_ctz, ich bin ein bisschen müde ...

Der Code sieht aus wie Java, obwohl, so dass ich die bitfoo erraten Sie suchen ist integer log .