У меня есть 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
?
@icza, это мой вопрос, как найти max (который находится за пределами диапазона uint64)
другими словами, меня интересует (MaxUint64+1)/пакеты
подумайте об этом key / (max / buckets)
если вы сделаете key * buckets / max
- вы сразу же получите 0, потому что это похоже на сдвиг всех битов uint64 на 64 позиции в младший бит, очистку всех его битов из памяти uint64...
Если 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))
Интересный способ, но мне нужно во время выполнения, и я боюсь, что big.NewInt
потребует аллоков и дорогих преобразований.. И мне нужно быстро! что вы думаете о работе с двумя 64-битными целыми, делая mult
, как здесь? github.com/davidminor/uint128/blob/master/uint128.go#L72
@ xakepp35 Да, это, вероятно, будет быстрее, чем big.Int
. Но обратите внимание, что если buckets
имеет ограниченное количество значений, вы можете предварительно вычислить и кэшировать размеры корзины результата, вам не нужно вычислять каждый раз. Предварительные вычисления и кэширование также превзойдут вычисления с 2 64-битными целыми числами.
Если значение buckets
мало, вы также можете сохранить результаты в срезе и использовать buckets
в качестве индекса среза!
да, lut vs calc, в зависимости от множества факторов. проверю как дела..
Также обратите внимание, что сохранение и индексирование фрагмента также будет работать, если buckets
не мало, но может быть легко преобразовано в небольшое число. Например. скажем, возможные значения ведер 100
, 200
, 300
. Вы можете использовать срез с 3 (или 4) элементами для хранения рассчитанных размеров корзины и индексировать его с помощью buckets / 100
.
Используйте размер ведра
max / buckets
, округленный в большую сторону, и индекс ведра будетkey / bucketSize
. Тебе этого мало?