Meilleure façon de trouver le godet Kademlia correct

Question

Dans les ID de nœud protocole Kademlia sont de 160 nombres de bits. Les nœuds sont stockées dans des seaux, seau 0 stocke tous les noeuds qui ont le même ID que ce noeud, sauf pour le dernier bit, le godet 1 stocke tous les noeuds qui ont le même ID que ce noeud, sauf pour les 2 derniers bits, et ainsi sur tous les 160 seaux.

Quelle est la façon la plus rapide pour trouver un seau que je devrais mettre un nouveau nœud dans?

J'ai 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 le plus bas de bit de poids faible, la comparaison peu à peu jusqu'à ce que je trouve une différence, j'espère qu'il ya une meilleure approche basée autour de bidouilles intelligent bits.

Note pratique: Mon Int160 est stocké dans un tableau d'octets avec 20 éléments, des solutions qui fonctionnent bien avec ce genre de structure sera préférée.

Answer 1

Seriez-vous prêt à envisager un tableau de 5 entiers de 32 bits? (Ou 3 nombres 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 deux identifiants de noeuds, en commençant par la plus importante. Si le résultat XOR est égal à zéro, passer au prochain mot le plus important.

Dans le cas contraire, trouver le bit le plus significatif qui est défini dans ce résultat XOR en utilisant la balise méthode constante de temps de Delight Hacker. . Ce résultat de l'algorithme en 32 (64) est réglé si le bit le plus significatif, et 1 si le bit le moins significatif est défini, et ainsi de suite. Cet indice, combiné à l'indice du mot courant, va vous dira quel bit est différent.

Answer 2

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

Il semble vaguement peu plausible pour moi que l'ajout d'un nœud à un tableau de godets sera si rapide que cela importe si vous faites peu-tripotant intelligent pour trouver le premier bit de différence dans un octet (ou mot), ou tout simplement le taux de désabonnement 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 que vous aimez est un comportement moyen cas, pas le pire des cas, alors faites juste la chose stupide. Il est très peu probable que votre boucle fonctionnera longtemps

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

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