Самый простой способ найти правильное ведро kademlia

Question

В протоколе Kademlia идентификаторы узла - это 160-битные числа. Узлы хранятся в сегментах, в сегменте 0 хранятся все узлы с таким же идентификатором, что и у этого узла, за исключением самого последнего бита, в сегменте 1 хранятся все узлы с таким же идентификатором, как у этого узла, за исключением последних 2 битов и т. Д. включен для всех 160 ковшей.

Какой самый быстрый способ найти, в какую корзину я должен поместить новый узел?

Мои корзины просто хранятся в массиве, и мне нужен такой метод:

Bucket[] buckets; //array with 160 items

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

Очевидный подход состоит в том, чтобы переходить от наиболее значимого бита, сравнивая по крупицам, пока я не найду разницу, я надеюсь, что есть лучший подход, основанный на умном переключении битов.

Практическое примечание: Мой Int160 хранится в байтовом массиве с 20 элементами, предпочтение отдается решениям, которые хорошо работают с такой структурой.

Answer 1

Хотели бы вы рассмотреть массив из 5 32-битных целых чисел?(или 3 64-битных целых числа)?Работа с целыми словами может дать вам лучшую производительность, чем работа с байтами, но метод должен работать в любом случае.

XOR соответствующие слова идентификаторов двух узлов, начиная с самого значимого.Если результат XOR равен нулю, переходите к следующему наиболее значимому слову.

В противном случае найдите старший значащий бит, установленный в этом результате XOR, используя метод с постоянным временем из восхищения Хакера. .Этот алгоритм приводит к 32 (64), если установлен старший значащий бит, и 1, если установлен младший значащий бит, и так далее.Этот индекс в сочетании с индексом текущего слова скажет вам, какой бит отличается.

Answer 2

Для начала вы можете сравнить побайтно (или пословно), и когда вы найдете поиск различий в пределах этого байта (или слова) для первого бита разности.

Мне кажется немного неправдоподобным, что добавление узла к массиву сегментов будет настолько быстрым, что это имеет значение, будь то умное переключение битов, чтобы найти первый бит разницы внутри байта (или слова), или просто отток в цикле до CHAR_BIT (или что-то). Возможно, однако.

Кроме того, если идентификаторы в основном случайные с равномерным распределением, то вы обнаружите разницу в первых 8 битах примерно в 255/256 случаев. Если все, что вас волнует, это поведение в среднем случае, а не в худшем случае, просто сделайте глупость: очень маловероятно, что ваш цикл будет работать долго.

Для справки, однако, первый бит разности между числами x и y является первым битом, установленным в x ^ y. Если вы программировали в GNU C, __builtin_clz может быть вашим другом. Или, может быть, __builtin_ctz, я немного сонный ...

Ваш код выглядит как Java, поэтому, я думаю, вы ищете bitfoo integer log .