Как разделить целочисленный хэш на диапазоны

У меня есть 64-битное число без знака, представляющее мантиссу или дробь (которые представляют собой диапазон от [0..1), где 0.0 сопоставляется с 0, а 0xffffff.. сопоставляется с числом «непосредственно перед 1.0»)

Теперь я хочу разбить этот диапазон на равные buckets - и ответить - задано случайное число key, в какую часть диапазона он попадет?

Его проще получить из следующего кода:

func BucketIndex(key, buckets uint64) uint64 {
    return uint64(float64(key) / ((math.Pow(2, 64) / float64(buckets)))
}

Моя попытка «взломать это» заключалась в том, чтобы разделить 2 ^ 64 на два, например, если я уменьшу диапазон до 32 бит и буду работать в 64-битном режиме, чтобы проводить математику:

// ~=key / ((1 << 64) / buckets)
return ((key >> 32) * buckets) >> 32

но диапазоны перестали быть равными.. например, одна треть (buckets==3) будет в 0x5555555600000000, а не в 0x5555555555555556 это грустная история, поэтому я спрашиваю, знаете ли вы лучшие методы поиска (1 << 64) / buckets?

🤔 А знаете ли вы, что...
В Go существует обширное сообщество разработчиков и ресурсы для обучения.


2
55
1

Ответ:

Решено

Если buckets является константой (времени компиляции), вы можете использовать константное выражение для вычисления размера корзины: константы имеют произвольный размер. В противном случае вы можете использовать big.Int для вычисления его во время выполнения и сохранения результата (так что вам не нужно постоянно использовать big.Int вычисления).

Использование константного выражения во время компиляции

Чтобы добиться округления при целочисленном делении в большую сторону, добавьте к делимому делитель - 1:

const (
    max        = math.MaxUint64 + 1
    buckets    = 3
    bucketSize = uint64((max + buckets - 1) / buckets)
)

Использование big.Int во время выполнения

Мы можем использовать ту же логику выше и с big.Int. Альтернативой может быть использование Int.DivMod() (вместо добавления buckets -1), и если mod больше нуля, увеличить результат на 1.

func calcBucketSize(max, buckets *big.Int) uint64 {
    max = max.Add(max, buckets)
    max = max.Add(max, big.NewInt(-1))
    return max.Div(max, buckets).Uint64()
}

var bucketSize = calcBucketSize(new(big.Int).SetUint64(math.MaxUint64), big.NewInt(3))