Алгоритм для распечатки перетасованного списка на месте и с O (1) памятью

StackOverflow https://stackoverflow.com/questions/1866684

  •  18-09-2019
  •  | 
  •  

Вопрос

После прочтения этот вопрос Я начал задаваться вопросом:возможно ли иметь алгоритм перетасовки, который не изменяет и не копирует исходный список?

Чтобы было ясно:

Представьте, что вам дают список объектов.Размер списка может быть произвольным, но предположим, что он довольно большой (скажем, 10 000 000 элементов).Вам нужно распечатать элементы списка в случайном порядке, и сделать это нужно как можно быстрее.Однако вам не следует:

  • Скопируйте исходный список, потому что он очень большой и копирование привело бы к трате БОЛЬШОГО объема памяти (вероятно, превышению пределов доступной оперативной памяти).;
  • Измените исходный список, потому что он каким-то образом отсортирован, а какая-то другая часть позже зависит от его сортировки.
  • Создайте список индексов, потому что, опять же, список очень большой, а копирование занимает слишком много времени и памяти.(Уточнение:имеется в виду любой другой список, который содержит то же количество элементов, что и исходный список).

Возможно ли это?

Добавленный: Дополнительные разъяснения.

  1. Я хочу, чтобы список был перетасован истинно случайным образом со всеми равновероятными перестановками (конечно, при условии, что у нас есть правильная функция Rand() для начала).
  2. Предложения о том, чтобы я составил список указателей, или список индексов, или любой другой список, который содержал бы то же количество элементов, что и исходный список, явно считаются неэффективными в соответствии с исходным вопросом.Вы можете создать дополнительные списки, если хотите, но они должны быть на порядки меньше исходного списка.
  3. Исходный список похож на массив, и вы можете извлечь из него любой элемент по его индексу в O(1).(Так что никаких двусвязных списков, где вам приходится перебирать весь список, чтобы добраться до нужного элемента.)

Добавлено 2:Хорошо, давайте сформулируем это так:У вас есть жесткий диск емкостью 1 ТБ, заполненный элементами данных, каждый размером 512 байт (один сектор).Вы хотите скопировать все эти данные на другой жесткий диск емкостью 1 ТБ, одновременно перетасовывая все элементы.Вы хотите сделать это как можно быстрее (однократный проход по данным и т.д.).У вас доступно 512 МБ оперативной памяти, и не рассчитывайте на подкачку.(Это теоретический сценарий, у меня нет ничего подобного на практике.Я просто хочу найти идеальный алгоритм.item.)

Это было полезно?

Решение

Вот очень простое доказательство того, что никакая схема PRNG не может работать:

Идея PRNG состоит из двух этапов:сначала выберите PRNG и его начальное состояние;во-вторых, используйте PRNG для перетасовки выходных данных.Что ж, есть Н! возможных перестановок, поэтому вам нужно по крайней мере Н! различные возможные начальные состояния, переходящие в фазу 2.Это означает, что в начале фазы 2 у вас должно быть по крайней мере журнал2 Н! биты состояния, которые недопустимы.

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

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

Поскольку алгоритм корректен и гарантированно завершается, существует функция f который, учитывая сохраненное состояние программы плюс любую достаточно длинную строку битов, производит допустимую последовательность операций чтения и записи с диска, завершающих перемешивание.Компьютер сам реализует эту функцию.Но рассматривайте это как математическую функцию:

f : (S × биты) → последовательность операций чтения и записи

Тогда, тривиально, существует функция g который, учитывая Только сохраненное состояние программы создает набор местоположений на диске, которые еще предстоит прочитать и записать.(Просто передайте некоторую произвольную строку битов в f, затем посмотрите на результаты.)

g : S → набор местоположений для чтения и записи

Оставшаяся часть доказательства состоит в том, чтобы показать, что область g содержит по крайней мере NCN/2 разные наборы независимо от выбора алгоритма.Если это правда, то должно быть по крайней мере столько элементов S, и поэтому состояние программы должно содержать по крайней мере журнал2 NCN/2 биты на полпути к отметке, в нарушение требований.

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

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

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

Существуют математические способы создания "произвольно выглядящих" перестановок из N целых чисел, поэтому, если P является такой перестановкой от 0 ..N-1 до 0 ..N-1, вы можете просто выполнить итерацию x от 0 до N-1 и вывести элемент списка L (P (x)) вместо L (x), и вы получите перетасовку.Такие перестановки могут быть получены, напримериспользуя модульную арифметику.Например, если N является простым, P(x)=(x * k) mod N является перестановкой для любого 0 < k < N (но сопоставляет 0 с 0).Аналогично для простого числа N, например P (x)= (x ^ 3) mod N должно быть перестановкой (но отображает 0 в 0 и 1 в 1).Это решение может быть легко расширено до не простого N, выбрав наименьшее простое число выше N (назовем его M), переставив до M и отбросив переставленные индексы выше N (аналогично ниже).

Следует отметить , что модульное возведение в степень является основой для многих криптографических алгоритмов (напримерRSA, Диффи-Хеллман) и рассматривается экспертами в этой области как сильно псевдослучайная операция.

Другой простой способ (не требующий простых чисел) - сначала расширить область так, чтобы вместо N вы рассматривали M, где M - наименьшая степень двух над N.Так , например ,если N = 12, вы устанавливаете M= 16.Затем вы используете биективные битовые операции, например

P(x) = ((x ^ 0xf) ^ (x << 2) + 3) & 0xf

Затем, когда вы выводите свой список, вы повторяете x от 0 до M-1 и выводите L(P (x)) только в том случае, если P (x) на самом деле < N.

"Истинное, непредвзятое случайное" решение может быть построено путем исправления криптографически надежного блочного шифрования (напримерAES) и случайный ключ (k), а затем повторение последовательности

AES(k, 0), AES(k, 1), ...

и вывод соответствующего элемента из последовательности, если AES(k,i) < N.Это может быть сделано в постоянном пространстве (внутренняя память, необходимая шифру) и неотличимо от случайной перестановки (из-за криптографических свойств шифра), но, очевидно, выполняется очень медленно.В случае AES вам нужно было бы повторять до тех пор, пока i = 2^ 128.

Вам не разрешено создавать копии, изменять их или отслеживать, какие элементы вы посетили?Я собираюсь сказать, что это невозможно.Если только я не неправильно понимаю ваш третий критерий.

Я так понимаю, это означает, что вам не разрешено говорить: создайте массив из 10 000 000 соответствующих логических значений, значение которого равно true, когда вы напечатаете соответствующий элемент.И вам не разрешается составлять список из 10 000 000 индексов, перетасовывать список и распечатывать элементы в таком порядке.

Эти 10 000 000 элементов являются всего лишь ссылками (или указателями) на реальные элементы, поэтому ваш список не будет таким большим.Только ~ 40 МБ на 32-разрядной архитектуре для всех ссылок + размер внутренних переменных этого списка.В случае, если ваши элементы меньше эталонного размера, вы просто копируете весь список целиком.

Это невозможно сделать с помощью воистину генератор случайных чисел, так как вы либо должны:

  • запомните, какие числа уже были выбраны, и пропустите их (для этого требуется O (n) список логических значений и постепенно ухудшающееся время выполнения по мере того, как вы пропускаете все больше и больше чисел).;или
  • уменьшайте пул после каждого выбора (для чего требуется либо внести изменения в исходный список, либо изменить отдельный список O (n)).

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

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

Битовая маска будет существенно лучше, чем исходный список из 39 ГБ (10 миллионов бит - это всего около 1,2 млн), на много порядков меньше, чем вы просили, даже если это все еще O (n).

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

Это означает, что вы не будете слоняться без дела, отчаянно ожидая, что генератор случайных чисел выдаст вам номер, который еще не использовался.Время выполнения будет таким же плохим, как и время, затраченное на сканирование 1,2 млн данных.

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

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

Итог:Я не верю, что то, о чем вы просите, выполнимо, но имейте в виду, что я ошибался раньше, о чем быстро и часто будет свидетельствовать моя жена :-) Но, как и во всем остальном, обычно есть способы обойти такие проблемы.

Это звучит невозможно.

Но 10 000 000 64-битных указателей - это всего около 76 МБ.

Сдвиговый регистр с линейной обратной связью может делать практически все, что вы хотите - генерировать список чисел до некоторого предела, но в (разумно) случайном порядке.Создаваемые им шаблоны статистически аналогичны тем, которые вы ожидаете от try randomness, но это даже близко не соответствует криптографической безопасности.Алгоритм Берлекэмпа-Мэсси позволяет вам перепроектировать эквивалентный LFSR на основе выходной последовательности.

Учитывая ваше требование к списку из ~ 10 000 000 элементов, вам бы понадобился 24-битный LFSR максимальной длины и просто отбросьте выходные данные, превышающие размер вашего списка.

Как бы то ни было, LFSR, как правило, довольно быстр по сравнению с типичным линейным конгруэнтным PRNG того же периода.В аппаратном обеспечении LFSR - это чрезвычайно простой, состоящий из N-разрядного регистра и M2-входных XOR (где M - количество нажатий - иногда всего пара, и редко более полудюжины или около того).

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

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

Вы можете создать псевдослучайную, "безопасную" перестановку, используя блочный шифр - см. здесь.Их ключевое понимание заключается в том, что, учитывая блочный шифр длиной n бит, вы можете использовать "сворачивание", чтобы сократить его до m < n бит, тогда уже упоминавшийся трюк antti.huima позволяет сгенерировать из него меньшую перестановку, не тратя огромное количество времени на отбрасывание значений, выходящих за пределы диапазона.

По сути, то, что вам нужно, - это генератор случайных чисел, который выдает числа 0 .. n-1 ровно по одному разу каждое.

Вот наполовину испеченная идея:Вы могли бы преуспеть, выбрав простое число p, немного большее n, затем выбрав случайный x между 1 и p-1, порядок которого в мультипликативной группе mod p равен p-1 (выберите случайные xs и проверьте, какие из них удовлетворяют x ^ i ! = 1 для i < p-1, вам нужно будет протестировать только несколько, прежде чем вы найдете один).Поскольку x затем генерирует группу, просто вычислите x ^ i mod p для 1 <= я <= p-2, и это даст вам p-2 различных случайных числа от 2 до p-1.Вычтите 2 и выбросьте единицы >= n, и это даст вам последовательность индексов для печати.

Это не совсем случайно, но вы можете использовать один и тот же метод несколько раз, взяв приведенные выше индексы (+ 1) и используя их как показатели другого генератора x2 по модулю другого простого числа p2 (вам понадобится n < р2 < р), и так далее.Дюжина повторений должна сделать все довольно случайным образом.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top