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

У меня есть 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?

Используйте размер ведра max / buckets, округленный в большую сторону, и индекс ведра будет key / bucketSize. Тебе этого мало?

icza 06.02.2023 15:30

@icza, это мой вопрос, как найти max (который находится за пределами диапазона uint64)

xakepp35 06.02.2023 15:58

другими словами, меня интересует (MaxUint64+1)/пакеты

xakepp35 06.02.2023 15:59

подумайте об этом key / (max / buckets) если вы сделаете key * buckets / max - вы сразу же получите 0, потому что это похоже на сдвиг всех битов uint64 на 64 позиции в младший бит, очистку всех его битов из памяти uint64...

xakepp35 06.02.2023 16:01
Создание API ввода вопросов на разных языках программирования (Python, PHP, Go и Node.js)
Создание API ввода вопросов на разных языках программирования (Python, PHP, Go и Node.js)
API ввода вопросов - это полезный инструмент для интеграции моделей машинного обучения, таких как ChatGPT, в приложения, требующие обработки...
2
4
55
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 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))

Интересный способ, но мне нужно во время выполнения, и я боюсь, что big.NewInt потребует аллоков и дорогих преобразований.. И мне нужно быстро! что вы думаете о работе с двумя 64-битными целыми, делая mult, как здесь? github.com/davidminor/uint128/blob/master/uint128.go#L72

xakepp35 06.02.2023 22:06

@ xakepp35 Да, это, вероятно, будет быстрее, чем big.Int. Но обратите внимание, что если buckets имеет ограниченное количество значений, вы можете предварительно вычислить и кэшировать размеры корзины результата, вам не нужно вычислять каждый раз. Предварительные вычисления и кэширование также превзойдут вычисления с 2 64-битными целыми числами.

icza 06.02.2023 22:10

Если значение buckets мало, вы также можете сохранить результаты в срезе и использовать buckets в качестве индекса среза!

icza 06.02.2023 22:15

да, lut vs calc, в зависимости от множества факторов. проверю как дела..

xakepp35 06.02.2023 22:16

Также обратите внимание, что сохранение и индексирование фрагмента также будет работать, если buckets не мало, но может быть легко преобразовано в небольшое число. Например. скажем, возможные значения ведер 100, 200, 300. Вы можете использовать срез с 3 (или 4) элементами для хранения рассчитанных размеров корзины и индексировать его с помощью buckets / 100.

icza 06.02.2023 22:24

Другие вопросы по теме