Il modo più semplice per trovare il secchio Kademlia corretta

Question

Nel nodo ID Kademlia protocollo sono numeri 160 bit. I nodi sono memorizzati in secchi, secchio 0 memorizza tutti i nodi che hanno lo stesso ID di questo nodo tranne l'ultimo bit, secchio 1 memorizza tutti i nodi che hanno lo stesso ID di questo nodo eccezione per gli ultimi 2 bit, e così on per tutti i 160 secchi.

Qual è il modo più veloce per trovare quale secchio dovrei mettere un nuovo nodo in?

Ho le mie secchi semplicemente memorizzati in un array, e bisogno di un metodo in questo modo:

Bucket[] buckets; //array with 160 items

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

L'approccio più ovvio è quello di lavorare verso il basso dal bit più significativo, il confronto a poco a poco fino a trovare una differenza, spero ci sia un approccio migliore, basata soprattutto intelligente po giocherellando.

nota pratica: Mio Int160 è memorizzato in una matrice di byte con 20 elementi, soluzioni che funzionano bene con sarà preferito questo tipo di struttura.

Answer 1

sareste disposti a prendere in considerazione una serie di 5 interi a 32 bit? (O 3 interi a 64 bit)? Lavorare con parole intere può dare prestazioni migliori rispetto a lavorare con i byte, ma il metodo dovrebbe funzionare in ogni caso.

XOR corrispondenti parole dei due ID di nodo, iniziando con la più significativa. Se il risultato XOR è pari a zero, spostare alla prossima parola più significativa.

In caso contrario, trovare il bit più significativo che si trova in questo risultato XOR utilizzando il metodo costante di tempo da Hacker Delight. . L'algoritmo crea 32 (64) se il bit più significativo è impostato, e 1 se il bit meno significativo è impostato, e così via. Questo indice, in combinazione con l'indice della parola corrente, vi dirà quale bit è diverso.

Answer 2

Per cominciare si potrebbe confrontare byte per byte (o parola per parola), e quando si trova una ricerca all'interno di differenza che di byte (o una parola) per la prima po 'di differenza.

Sembra vagamente plausibile a me che l'aggiunta di un nodo a una serie di benne sarà così veloce che importa se si fa intelligente bit-giocherellando per trovare la prima po 'di differenza all'interno di un byte (o una parola), o semplicemente zangola in un ciclo fino a CHAR_BIT (o qualcosa del genere). Possibile, però.

Inoltre, se gli ID sono essenzialmente casuale con distribuzione uniforme, allora troverete una differenza nei primi 8 bit di circa 255/256 del tempo. Se tutto ciò che interessa è il comportamento nel caso medio, non peggiore, poi basta fare la cosa stupida:. È molto improbabile che il vostro ciclo avrà una durata di tempo

Per riferimento, tuttavia, il primo bit della differenza tra i numeri x e y è il primo bit impostato a x ^ y. Se stavate programmando in GNU C, __builtin_clz potrebbe essere tuo amico. O forse __builtin_ctz, io sono una specie di sonno ...

Il tuo aspetto di codice come Java, però, quindi credo che la bitfoo che stai cercando è registro intero .