Maneira mais fácil de encontrar o balde Kademlia correto
-
27-09-2019 - |
Pergunta
No Protocolo Kademlia Os IDs dos nó são números de 160 bits. Os nós são armazenados em baldes, o balde 0 armazena todos os nós que têm o mesmo ID que este nó, exceto pelo último bit, o Bucket 1 armazena todos os nós que têm o mesmo ID que este nó, exceto nos últimos 2 bits, e assim para todos os 160 baldes.
Qual é a maneira mais rápida de descobrir em qual balde eu devo colocar um novo nó?
Eu tenho meus baldes simplesmente armazenados em uma matriz e preciso de um método como assim:
Bucket[] buckets; //array with 160 items
public Bucket GetBucket(Int160 myId, Int160 otherId)
{
//some stuff goes here
}
A abordagem óbvia é trabalhar com a parte mais significativa, comparando pouco a pouco até encontrar uma diferença, espero que haja uma abordagem melhor baseada em um bit giratório.
Nota prática: meu INT160 é armazenado em uma matriz de bytes com 20 itens, soluções que funcionam bem com esse tipo de estrutura serão preferidas.
Solução
Você estaria disposto a considerar uma matriz de 5 números inteiros de 32 bits? (ou 3 inteiros de 64 bits)? Trabalhar com palavras inteiras pode oferecer melhor desempenho do que trabalhar com bytes, mas o método deve funcionar em qualquer caso.
Xor as palavras correspondentes dos dois IDs de nós, começando com os mais significativos. Se o resultado do XOR for zero, passe para a próxima palavra mais significativa.
Caso contrário, encontre o bit mais significativo definido neste resultado XOR usando o Método de tempo constante do deleite de Hacker.. Esse algoritmo resulta em 32 (64) se o bit mais significativo for definido e 1 se o bit menos significativo for definido e assim por diante. Esse índice, combinado com o índice da palavra atual, dirá qual bit é diferente.
Outras dicas
Para iniciantes, você pode comparar byte por byte (ou palavra por palavra) e quando encontrar uma pesquisa de diferença nesse byte (ou palavra) pela primeira diferença.
Parece-me vagamente implausível que a adição de um nó a uma variedade de baldes seja tão rápido que importa se você faz uma variação inteligente para encontrar a primeira diferença dentro de um byte (ou palavra) ou apenas agitar em um loop até char_bit (ou algo assim). Possível, no entanto.
Além disso, se os IDs forem essencialmente aleatórios com distribuição uniforme, você encontrará uma diferença nos 8 primeiros bits cerca de 255/256 do tempo. Se tudo o que você se preocupa é um comportamento médio, não o pior caso, faça a coisa estúpida: é muito improvável que seu loop durar por muito tempo.
Para referência, porém, a primeira diferença entre os números x
e y
é o primeiro bit em x ^ y
. Se você estava programando no GNU C, __builtin_clz
pode ser seu amigo. Ou possivelmente __builtin_ctz
, Estou meio sonolento ...
Seu código se parece com Java, então acho que o bitfoo que você está procurando é Log inteiro.