Как разделить пространство UUID на N разделов одинакового размера? - PullRequest
Новая
       9

Как разделить пространство UUID на N разделов одинакового размера?

0 голосов
/ 27 июня 2018

Взять UUID в его шестнадцатеричном представлении: '123e4567-e89b-12d3-a456-426655440000'

У меня много таких UUID, и я хочу разделить их на N сегментов, где N выбрал я, и я хочу сгенерировать границы этих сегментов.

Я могу легко создать 16 блоков с этими границами: 

00000000-0000-0000-0000-000000000000
10000000-0000-0000-0000-000000000000
20000000-0000-0000-0000-000000000000
30000000-0000-0000-0000-000000000000
...
e0000000-0000-0000-0000-000000000000
f0000000-0000-0000-0000-000000000000
ffffffff-ffff-ffff-ffff-ffffffffffff

, просто перебирая опции для первой шестнадцатеричной цифры.

Предположим, я хочу 50 блоков одинакового размера (равных по количеству возможностей UUID, содержащихся в каждом сегменте), или 2000 блоков, или N блоков.

Как мне сгенерировать такие оценки как функцию от N?

Ответы [ 2 ]

0 голосов
/ 04 ноября 2018

Если N - степень 2, то решение очевидно: вы можете разбить битовые границы, как для 16 сегментов в вашем вопросе.

Если N не является степенью 2, то математически ведра не могут иметь точно одинакового размера, поэтому возникает вопрос, насколько неравны вы готовы терпеть во имя эффективности.

До тех пор, пока N <2 ^ 24 или около того, самое простое, что нужно сделать, - это просто выделить UUID на основе первых 32 битов в N блоков, каждый из которых имеет размер 2 ^ 32 / N. Это должно быть достаточно быстрым и одинаковым для большинства приложений, и если N должно быть больше, чем позволяет, вы можете легко удвоить биты с небольшим штрафом. </p>

0 голосов
/ 28 июня 2018

Ваши UUID выше имеют длину 32 шестнадцатеричных числа. Это означает, что у вас есть 16 ^ 32 ≈ 3.4e38 возможных UUID. Простым решением было бы использовать большую библиотеку int (или собственный метод) для хранения этих очень больших значений как фактических чисел. Затем вы можете просто поделить число возможных UUID на N (назовите это значение k), дав вам границы сегмента 0, k, 2 * k, ... (N-1) * k, UMAX.

Это приводит к проблеме, если N не делит число возможных UUID. Очевидно, что не все сегменты будут иметь одинаковое количество UUID, но в этом случае они даже не будут равномерно распределены. Например, если число возможных UUID равно 32, и вы хотите 7 сегментов, тогда k будет равно 4, поэтому у вас будут сегменты размером 4, 4, 4, 4, 4, 4 и 8. Это, вероятно, не ' т идеал. Чтобы исправить это, вместо этого вы можете установить границы сегмента в 0, (1 * UMAX) / N, (2 * UMAX) / N, ... ((N-1) * UMAX) / N, UMAX. Затем в вышеописанном неудобном случае вы получите границы 0, 4, 9, 13, 18, 22, 27, 32 - с размерами сегментов 4, 5, 4, 5, 4, 5, 5.

Вероятно, вам понадобится большая библиотека int или какой-либо другой метод для хранения больших целых чисел, чтобы использовать этот метод. Для сравнения, long long в C ++ (в некоторых реализациях) может хранить только до 2 ^ 64 ≈ 1.8e19.

...