Если я правильно понимаю, у вас есть около 100 ТБ данных или 13 743 895 347 200 64-битных целых чисел без знака, которые вы хотите распределить по нескольким сегментам.
Первым шагом может быть повторение ввода, глядя, например. старшие 24 бита каждого целого числа и их подсчет. Это даст вам список из 16 777 216 диапазонов, каждый со средним числом 819 200, поэтому их можно хранить в 32-битных целых числах без знака, что займет 64 МБ.
Затем вы можете использовать это для создания таблицы поиска, которая сообщает вам, в какое ведро входит каждый из этих 16 777 216 диапазонов. Вы вычисляете, сколько целых чисел должно войти в каждое ведро (входной размер, разделенный на количество ведер), и проходите по массиву, сохраняя промежуточный итог подсчета, и устанавливаете каждый диапазон в ведро 1, пока промежуточный итог не станет слишком большим. для ведра 1, затем вы устанавливаете диапазоны для ведра 2 и так далее...
Конечно, всегда будет диапазон, который должен быть разделен между сегментом n и сегментом n+1. Чтобы отслеживать это, вы создаете вторую таблицу, в которой хранится, сколько целых чисел в этих разделенных диапазонах должно попасть в корзину n+1.
Итак, теперь у вас есть, например:
HIGH 24-BIT RANGE BUCKET BUCKET+1
0 0 ~ 2^40-1 1 0
1 2^40 ~ 2*2^40-1 1 0
2 2*2^40 ~ 3*2^40-1 1 0
3 3*2^40 ~ 4*2^40-1 1 0
...
16 16*2^40 ~ 17*2^40-1 1 0
17 17*2^40 ~ 18*2^40-1 1 284,724 <- highest 284,724 go into bucket 2
18 18*2^40 ~ 19*2^40-1 2 0
...
Теперь вы можете снова перебрать ввод и для каждого целого числа посмотреть на старшие 24 бита и использовать таблицу поиска, чтобы увидеть, в какое ведро должно попасть целое число. Если диапазон не разделен, вы можете сразу же переместить целое число в правую корзину. Для каждого диапазона разделения вы создаете упорядоченный список или очередь приоритетов, которая может содержать столько целых чисел, сколько необходимо для перехода в следующую корзину; вы сохраняете только самые высокие значения в этом списке или очереди; любое меньшее целое число отправляется прямо в корзину, а если целое число добавляется в полный список или очередь, наименьшее значение перемещается в корзину. В конце этот список или очередь добавляется к следующему сегменту.
Количество диапазонов должно быть как можно больше с доступной памятью, потому что это минимизирует количество целых чисел в разделенных диапазонах. Имея огромные входные данные, вам может потребоваться сохранить разделенные диапазоны на диск, а затем просмотреть каждый из них отдельно, найти самые высокие значения x и соответствующим образом переместить их в сегменты.
Сложность этого составляет N для первого запуска, затем вы перебираете диапазоны R, затем N, когда вы снова перебираете ввод, а затем для разделенных диапазонов у вас будет что-то вроде M.logM для сортировки и M для распределения , так что в сумме 2*N + R + M.LogM + M. Использование большого количества диапазонов для уменьшения количества целых чисел в разделенных диапазонах, вероятно, будет лучшей стратегией для ускорения процесса.
На самом деле количество целых чисел M, которые находятся в разделенных диапазонах, зависит от количества сегментов B и диапазонов R, где M = N × B/R, так что, например, с тысячей сегментов и миллионом диапазонов 0,1% входных данных будут разделены на диапазоны и должны быть отсортированы. (Это средние значения, зависящие от фактического распределения.) Таким образом, общая сложность равна 2×N + R + (N×B/R).Log(N×B/R) + N×B /Р.
Другой пример:
Входные данные: N = 13 743 895 347 200 64-битных целых чисел без знака
Диапазоны: 232 (с использованием старших 32 битов каждого целого числа)
Целых чисел в диапазоне: 3200 (в среднем)
Список счетчиков: 232 16-битных целых чисел = 8 ГБ
Таблица поиска: 232 16-битных целых чисел = 8 ГБ
Разделить таблицу диапазонов : B 16-битных целых чисел = 2×B байтов
С 1024 сегментами это будет означать, что B/R = 1/222, и есть 1023 разделенных диапазона с примерно 3200 целыми числами в каждом, или всего около 3 276 800 целых чисел; затем их нужно будет отсортировать и распределить по ведрам.
С 1 048 576 сегментами это будет означать, что B/R = 1/212, и существует 1 048 575 разделенных диапазонов с примерно 3 200 целыми числами в каждом, или около 3 355 443 200 целых чисел в целом. (Конечно, для более чем 65 536 сегментов потребуется таблица поиска с 32-битными целыми числами.)
(Если вы обнаружите, что общее количество счетчиков в диапазоне не равно общему размеру входных данных, в списке счетчиков произошло переполнение, и вам следует переключиться на более крупный целочисленный тип для счетчиков.)< /я>
Давайте рассмотрим крошечный пример: 50 целых чисел в диапазоне от 1 до 100 должны быть распределены по 5 корзинам. Мы выбираем количество диапазонов, скажем, 20, и перебираем входные данные, чтобы подсчитать количество целых чисел в каждом диапазоне:
2 9 14 17 21 30 33 36 44 50 51 57 69 75 80 81 87 94 99
1 9 15 16 21 32 40 42 48 55 57 66 74 76 88 96
5 6 20 24 34 50 52 58 70 78 99
7 51 69
55
3 4 2 3 3 1 3 2 2 3 5 3 0 4 2 3 1 2 1 3
Затем, зная, что каждое ведро должно содержать 10 целых чисел, мы перебираем список счетчиков для каждого диапазона и назначаем каждый диапазон ведру:
3 4 2 3 3 1 3 2 2 3 5 3 0 4 2 3 1 2 1 3 <- count/range
1 1 1 1 2 2 2 2 3 3 3 4 4 4 4 5 5 5 5 5 <- to bucket
2 1 1 <- to next
Когда диапазон необходимо разделить между двумя сегментами, мы сохраняем количество целых чисел, которые должны перейти к следующему сегменту, в отдельной таблице.
Затем мы можем снова перебрать ввод и переместить все целые числа в неразделенных диапазонах в корзины; целые числа в разделенных диапазонах временно перемещаются в отдельные сегменты:
bucket 1: 9 14 2 9 1 15 6 5 7
temp 1/2: 17 16 20
bucket 2: 21 33 30 32 21 24 34
temp 2/3: 36 40
bucket 3: 44 50 48 42 50
temp 3/4: 51 55 52 51 55
bucket 4: 57 75 69 66 74 57 57 70 69
bucket 5: 81 94 87 80 99 88 96 76 78 99
Затем мы смотрим на временные корзины одну за другой, находим x наибольших целых чисел, как указано во второй таблице, перемещаем их в следующую корзину и то, что осталось в предыдущей корзине:
temp 1/2: 17 16 20 (to next: 2) bucket 1: 16 bucket 2: 17 20
temp 2/3: 36 40 (to next: 1) bucket 2: 36 bucket 3: 40
temp 3/4: 51 55 52 51 55 (to next: 1) bucket 3: 51 51 52 55 bucket 4: 55
И конечный результат:
bucket 1: 9 14 2 9 1 15 6 5 7 16
bucket 2: 21 33 30 32 21 24 34 17 20 36
bucket 3: 44 50 48 42 50 40 51 51 52 55
bucket 4: 57 75 69 66 74 57 57 70 69 55
bucket 5: 81 94 87 80 99 88 96 76 78 99
Итак, из 50 целых чисел нам пришлось отсортировать группу из 3, 2 и 5 целых чисел.
На самом деле вам не нужно создавать таблицу с количеством целых чисел в разделенных диапазонах, которые должны перейти в следующее ведро. Вы знаете, сколько целых чисел должно попасть в каждое ведро, поэтому после начального распределения вы можете посмотреть, сколько целых чисел уже находится в каждом ведре, а затем добавить необходимое количество целых чисел (наименьшее значение) из диапазона разделения. В приведенном выше примере, который ожидает 10 целых чисел на ведро, это будет:
3 4 2 3 3 1 3 2 2 3 5 3 0 4 2 3 1 2 1 3 <- count/range
1 1 1 / 2 2 2 / 3 3 / 4 4 4 4 5 5 5 5 5 <- to bucket
bucket 1: 9 14 2 9 1 15 6 5 7 <- add 1
temp 1/2: 17 16 20 <- 3-1 = 2 go to next bucket
bucket 2: 21 33 30 32 21 24 34 <- add 3-2 = 1
temp 2/3: 36 40 <- 2-1 = 1 goes to next bucket
bucket 3: 44 50 48 42 50 <- add 5-1 = 4
temp 3/4: 51 55 52 51 55 <- 5-4 = 1 goes to next bucket
bucket 4: 57 75 69 66 74 57 57 70 69 <- add 1-1 = 0
bucket 5: 81 94 87 80 99 88 96 76 78 99 <- add 0
Вычисление того, какая часть входных данных будет находиться в разделенных диапазонах и должна быть отсортирована, приведенная выше как M = N × B/R, представляет собой среднее значение для примерно равномерно распределенных входных данных. Небольшое смещение с большим количеством значений в определенной части входного пространства не будет иметь большого эффекта, но действительно было бы возможно создать наихудший ввод, чтобы помешать алгоритму.
Давайте еще раз посмотрим на этот пример:
Входные данные: N = 13 743 895 347 200 64-битных целых чисел без знака
Диапазоны: 232 (с использованием старших 32 битов каждого целого числа)
Целых чисел в диапазоне: 3200 (в среднем)
Сегменты: 1 048 576
Целых чисел на сегмент: 13 107 200
Для начала, если есть диапазоны, содержащие более 232 целых чисел, вам придется использовать 64-битные целые числа для таблицы подсчета, поэтому ее размер будет 32 ГБ, что может заставить вас использовать меньше диапазонов, в зависимости от доступной памяти.
Кроме того, каждый диапазон, который содержит больше целых чисел, чем целевой размер на сегмент, автоматически становится разделенным диапазоном. Поэтому, если целые числа распределены по множеству локальных кластеров, вы можете обнаружить, что большая часть входных данных находится в разделенных диапазонах, которые необходимо отсортировать.
Если у вас достаточно памяти для выполнения первого шага с использованием 232 диапазонов, то каждый диапазон будет иметь 232 различных значений, и вы можете распределить разделенные диапазоны по сегментам, используя сортировка подсчетом (имеющая линейную сложность).
Если у вас недостаточно памяти для использования 232 диапазонов, и вы получаете проблемно большие разделенные диапазоны, вы можете снова использовать полный алгоритм для разделенных диапазонов. Допустим, вы использовали 228 диапазонов, ожидая, что каждый диапазон будет содержать около 51 200 целых чисел, и в итоге вы получили неожиданно большой разделенный диапазон с 5 120 000 000 целых чисел, которые необходимо распределить по 391 сегменту. Если вы снова запустите алгоритм для этого ограниченного диапазона, у вас будет 228 диапазонов (каждый из которых содержит в среднем 19 целых чисел с максимум 16 различными значениями) всего для 391 корзины и лишь небольшой риск снова оказаться с большими разделенными диапазонами.
Примечание. Диапазоны, которые должны быть разделены на два или более сегмента, не обязательно должны быть отсортированы. Вы можете, например. используйте рекурсивную версию алгоритма голландского национального флага Дейкстры, чтобы разделить диапазон на часть с наименьшими значениями x и часть с наибольшими значениями. Средняя сложность разбиения будет линейной (при использовании случайного поворота) по сравнению со сложностью сортировки O(N.LogN).
person
m69 ''snarky and unwelcoming''
schedule
20.06.2017
