La manera más fácil de encontrar el cubo Kademlia correcta

Question

En la ID de nodo href="http://xlattice.sourceforge.net/components/protocol/kademlia/specs.html" rel="nofollow noreferrer"> de protocolo son números de 160 bits. Los nodos se almacenan en cubos, cubo 0 tiendas de todos los nodos que tienen el mismo ID que este nodo, excepto para el último bit, de cubo 1 almacena todos los nodos que tienen el mismo ID que este nodo excepción de los últimos 2 bits, y por lo tanto por los 160 cubos.

¿Cuál es la manera más rápida de encontrar qué cubeta que debería poner un nuevo nodo en?

Tengo mis cubos almacenan simplemente en una matriz, y la necesidad de un método de este modo:

Bucket[] buckets; //array with 160 items

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

El enfoque obvio es trabajar desde el bit más significativo, comparando poco a poco hasta que encuentre una diferencia, estoy esperando que hay un mejor enfoque en torno inteligente cambio de bit.

Nota práctica: Mi Int160 se almacena en una matriz de bytes con 20 artículos, soluciones que funcionan bien con preferirá que tipo de estructura.

Answer 1

¿Usted estaría dispuesto a considerar una serie de 5 números enteros de 32 bits? (O 3 enteros de 64 bits)? Trabajar con palabras completas le puede dar un mejor rendimiento que trabajar con bytes, pero el método debería funcionar en cualquier caso.

XOR las palabras correspondientes de los dos ID de nodo, a partir de los más significativos. Si el resultado es cero XOR, pasar a la siguiente palabra más significativa.

De lo contrario, encontrar el bit más significativo que se establece en este resultado XOR con el método constante de tiempo de Hacker Delight. . Este algoritmo resultados en 32 (64) si se establece el bit más significativo, y 1 si el bit menos significativo es el conjunto, y así sucesivamente. Este índice, combinado con el índice de la palabra actual, se le dirá qué bit es diferente.

Answer 2

Para empezar se podría comparar byte por byte (o palabra por palabra), y cuando encuentre una búsqueda diferencia dentro de ese byte (o palabra) para el primer bit de diferencia.

Parece vagamente plausible para mí que la adición de un nodo a una serie de cubos será tan rápido es que importe si lo hace inteligente de bits haciendo girar para encontrar el primer bit de diferencia dentro de un byte (o palabra), o simplemente la rotación en un bucle hasta CHAR_BIT (o algo así). Es posible, sin embargo.

Además, si los identificadores son esencialmente aleatoria con una distribución uniforme, a continuación, se encuentra una diferencia en los primeros 8 bits unos 255/256 del tiempo. Si todo lo que importa es el comportamiento promedio de los casos, no peor de los casos, a continuación, sólo hacer lo estúpida:. Que es muy poco probable que el bucle se ejecutará por mucho tiempo

Para referencia, sin embargo, el primer bit de la diferencia entre los números x y y es el primer conjunto de bits en x ^ y. Si estaba programando en C de GNU, __builtin_clz podría ser su amigo. O posiblemente __builtin_ctz, estoy un poco sueño ...

Sus miradas de código como Java, aunque, por lo que supongo que la bitfoo que estás buscando es registro de número entero .