У меня есть 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 существует обширное сообщество разработчиков и ресурсы для обучения.
Если buckets
является константой (времени компиляции), вы можете использовать константное выражение для вычисления размера корзины: константы имеют произвольный размер. В противном случае вы можете использовать big.Int
для вычисления его во время выполнения и сохранения результата (так что вам не нужно постоянно использовать big.Int
вычисления).
Чтобы добиться округления при целочисленном делении в большую сторону, добавьте к делимому делитель - 1:
const (
max = math.MaxUint64 + 1
buckets = 3
bucketSize = uint64((max + buckets - 1) / buckets)
)
Мы можем использовать ту же логику выше и с 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))