Le moyen le plus simple de trouver le bon godet kademlia

Question

Dans les Kademlia protocol, les ID de nœud sont des nombres de 160 bits. Les nœuds sont stockés dans des compartiments, le compartiment 0 stocke tous les nœuds qui ont le même ID que ce nœud, sauf pour le tout dernier bit, le compartiment 1 stocke tous les nœuds ayant le même ID que ce nœud sauf pour les 2 derniers bits. pour tous les 160 seaux.

Quel est le moyen le plus rapide pour trouver dans quel seau je devrais mettre un nouveau noeud?

Je mes seaux simplement stockées dans un tableau, et ont besoin d'une méthode comme ceci:

Bucket[] buckets; //array with 160 items 

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

L'approche évidente consiste à travailler en bas du bit le plus significatif, la comparaison peu à peu jusqu'à ce que je trouve une différence , J'espère qu'il y aura une meilleure approche basée autour de twittling intelligent. Mon Int160 est stocké dans un tableau d'octets avec 20 articles, des solutions qui fonctionnent bien avec ce type de structure seront préférées.

Answer 1

Seriez-vous prêt à considérer un tableau de 5 entiers de 32 bits? (ou 3 entiers de 64 bits)? Travailler avec des mots entiers peut vous donner de meilleures performances que de travailler avec des octets, mais la méthode devrait fonctionner dans tous les cas.

XOR les mots correspondants des ID de deux nœuds, en commençant par le plus significatif. Si le résultat XOR est zéro, passez au mot suivant le plus significatif.

Sinon, recherchez le bit le plus significatif défini dans ce résultat XOR à l'aide de constant time method from Hacker's Delight.. Cet algorithme donne 32 (64) si le bit le plus significatif est mis, et 1 si le bit le moins significatif est activé, et ainsi de suite. Cet index, combiné avec l'index du mot courant, vous dira quel bit est différent.

Answer 2

Pour commencer, vous pouvez comparer octet par octet (ou mot par mot), et lorsque vous trouvez une recherche de différence dans cet octet (ou mot) pour le premier bit de différence.

Il me semble vaguement invraisemblable que l'ajout d'un nœud à une série de compartiments soit si rapide que cela importe que vous fassiez des astuces pour trouver le premier bit de différence dans un octet (ou un mot), ou juste baratter dans une boucle jusqu'à CHAR_BIT (ou quelque chose). Possible, cependant. En outre, si les ID sont essentiellement aléatoires avec une distribution uniforme, alors vous trouverez une différence dans les 8 premiers bits sur 255/256 du temps. Si tout ce qui vous intéresse est un comportement moyen, pas le pire des cas, alors faites la bêtise: il est très improbable que votre boucle fonctionne longtemps.

Pour référence, cependant, le premier bit de différence entre les numéros x et y est le premier bit défini dans x^y. Si vous programmiez en GNU C, __builtin_clz pourrait être votre ami. Ou peut-être __builtin_ctz, je suis un peu endormi ...

Votre code ressemble à Java, donc je suppose que le bitfoo que vous cherchez est integer log.