Возможность использования MapReduce для случайного перемешивания 2 ^ 32 чисел

Question

Типичным алгоритмом сортировки 2 ³² чисел будет:

1. Создать массив из 2 ³² чисел и заполнить их от 0 до 2 ³² -1
2. Пусть n = количество элементов в массиве = 2 ³²
3. Случайным образом выбрать число от 0 до n-1, удалить число из массива и поместить его в стек
4. Теперь n уменьшается на 1, а размер стека увеличивается на 1
5. перейти к 3. до тех пор, пока массив не станет пустым, окончательный стек является решением

2 ³² = 4 294 967 296 единиц

2 ³² * 4 = 17 179 869 184 байта, если мы используем 4-байтовые целые числа без знака

Поскольку у меня не так много памяти на одной машине, использование memmap () может быть хорошим кандидатом (возможно, самый простой подход).

Из любопытства мне стало интересно, могу ли я использовать MapReduce для решения этой проблемы? Как бы выглядели функции Map и Reduce?

Эта идея пришла мне в голову, потому что, хотя у меня не так много памяти на одной машине, у меня определенно много памяти во всех блоках, которые есть в локальной сети. Распределенная природа данных в MapReduce может помочь.

Хотя альтернативные, эквивалентные алгоритмы, которые соответствуют MapReduce, приветствуются, может быть трудно найти такой, который не ухудшает случайность вышеупомянутого алгоритма.

Answer 1

В статье «MapReduce: упрощенная обработка данных на больших кластерах» описывается (страница 3, непосредственно перед разделом 3), как использовать MapReduce для выполнения распределенной сортировки. Один из способов сделать случайное перемешивание из 2 ^ 32 чисел состоит в том, чтобы присвоить каждому числу случайно сгенерированный 80-битный ключ, а затем отсортировать ключ + + по этому ключу. С 80-битными ключами будет очень мало связей (ожидаемое число около 2 ^ -17), и вы можете использовать последний проход, чтобы расположить их в случайном порядке.

Нет сомнений, что есть лучшие способы сделать это, если вы готовы к программированию на относительно низком уровне, но как случайное перемешивание, так и сортировка требуют серьезного перемещения данных между компьютерами, и, вероятно, Много работы будет потрачено на то, чтобы сделать сортировку разумной - таким образом, вы сможете использовать ее повторно.

Answer 2

Если вам просто нужно иметь возможность выбирать элементы из большой случайной перестановки, вам не нужно осознавать это, создавая и перемешивая все это.Прочтите этот пост , чтобы узнать, как сгенерировать «безопасную» (криптографически трудно угадываемую) перестановку из блочного шифра.

Answer 3

На вашем шаге отображения может быть применен алгоритм Фишера-Йейтса к подмассивам вашего ввода.

В этом шаге сокращения придется комбинировать перетасованные подмассивы путем случайного слияния (принимая во внимание оставшийся размер частейна каждом этапе).

Однако я не думаю, что это дает какое-либо преимущество по сравнению с простым выполнением тасования Фишера-Йейтса на диске на одной машине, поскольку все, что он делает, это заменяет узкое место случайного доступа к дискуузкое место скорости сети.

Answer 4

Мне нужен уникальный (неповторяющийся) 32-битный ключ для целей индексации

Почему бы вам не поддерживать счетчик в приложении и увеличивать его.

Если это распределенное приложение, то вы могли бы ZooKeeper .Существует аналогичный поток SO .

ZooKeeper работает на Java и имеет привязок для Java и C.