Доброго времени суток!

Задача такая. Есть набор из N элементов (N достаточно велико, порядка сотен тысяч).

Требуется извлекать элементы из набора в случайном порядке. При этом, извлечение может быть приостановлено, и впоследствии возобновлено с того же места (т.е. нужно иметь возможность сохранять/восстанавливать текущий порядок перетасованных элементов, а также не выдавать повторно уже извлеченные до приостановки элементы). Объем сохраняемых данных должен быть минимальным по отношению к N -- в идеале, O(1).

Текущая идея реализации использует рабочую таблицу перестановок:

Подготовка:

Переменные:
   N -- кол-во элементов
   x0 -- начальное состояние ГПСЧ
   cnt -- счетчик уже выданных элементов

1. Выделяем память под рабочую таблицу индексов T[N] // размер зависит от N -- хотелось бы избежать
2. Инициализируем ГПСЧ (a la randomize()) и сохраняем его состояние в переменной x0
3. Заполняем T[i] := i, i in [0, N)
4. Перемешиваем таблицу T, используя ГПСЧ
5. Устанавливаем cnt := 0

Получение элемента:

1. Вернуть элемент ElementTable[ T[cnt] ]
2. cnt := cnt + 1

При приостановке требуется сохранить только x0 и cnt.
При восстановлении используется такая же процедура, как и при подготовке, только на шагах 2 и 5 используются сохраненные значения x0 и cnt вместо randomize() и 0, соответственно.

Собственно, вопрос: нельзя ли как-нибудь избавиться от таблицы T с размером O(N)?

Большое спасибо всем дочитавшим до конца

А>Собственно, вопрос: нельзя ли как-нибудь избавиться от таблицы T с размером O(N)?
А может сам набор данных перемешать случайным образом, а потом выбирать по порядку? Тогда только счётчик придётся сохранять

Здравствуйте, Аноним, Вы писали:

А>Доброго времени суток!

А>Задача такая. Есть набор из N элементов (N достаточно велико, порядка сотен тысяч).

А>Требуется извлекать элементы из набора в случайном порядке. При этом, извлечение может быть приостановлено, и впоследствии возобновлено с того же места (т.е. нужно иметь возможность сохранять/восстанавливать текущий порядок перетасованных элементов, а также не выдавать повторно уже извлеченные до приостановки элементы). Объем сохраняемых данных должен быть минимальным по отношению к N -- в идеале, O(1).

http://en.wikipedia.org/wiki/Linear_congruential_generator

Cохраняешь коэффиценты и текущий seed и радуешься...

Здравствуйте, <Аноним>, Вы писали:

А>Собственно, вопрос: нельзя ли как-нибудь избавиться от таблицы T с размером O(N)?

Если генератор случайных чисел честный, то, фактически, ты порождаешь случайное число в диапазоне 1..N! — его разрядность равна log(N!) = log((N/e)^N) = N*log(N/e) ~ O(N*log(N)).
При том, что разрядность таблицы перестановок имеет такой же порядок: N элементов, каждый из которых имеет разрядность log(N), т.е. O(N*log(N)).

Теоретически, выход можно поискать в том, что ГСЧ имеет ограниченную разрядность. То есть, вместо N! вариантов мы реально имеем min(N!,2^w) где w — разрядность "зерна случайности" (random seed).

На практике же всё равно придётся хранить как минимум N-битную таблицу (отлично! уже избавились от log(N)) и текущее состояние ГСЧ (на которое можно наплевать, если нам не нужна воспроизводимость).
Правда, цена — это время порождения очередного элемента O(N).


Кстати говоря, перетасовывать можно не сразу (потратив O(N) времени), а на каждый акт чтения.
— изначально таблица заполняется последовательно: e[t] = t
— выборка очередного (t-го) элемента: r = random(n-t); swap(e[t], e[t+r]); return e[t]

Здравствуйте, Spalex, Вы писали:

S>А может сам набор данных перемешать случайным образом, а потом выбирать по порядку? Тогда только счётчик придётся сохранять

К сожалению, это невозможно: набор данных находится "снаружи" и не может изменяться; может потребоваться несколько независимых перестановок на одном наборе данных.

Здравствуйте, Pavel Chikulaev, Вы писали:

PC>http://en.wikipedia.org/wiki/Linear_congruential_generator
PC>Cохраняешь коэффиценты и текущий seed и радуешься...

Хм, подбирать параметры генератора, так чтобы он давал полный период на произвольном N? Интересная мысль, надо с ней поэкспериментировать.
Придется доставать с полки Кнута

Спасибо!

Здравствуйте, Кодт, Вы писали:

К>Если генератор случайных чисел честный,...
На самом деле, к генератору, скорее всего, особых требований нет (просто в системе уже есть один генератор, предполагалось его переиспользовать, но это не догма). Поэтому пока что мне нравится предложение Павла использовать "custom" линейно-конгруэнтный генератор с периодом, равным N (я, правда, еще не понял, подойдет ли).

К>На практике же всё равно придётся хранить как минимум N-битную таблицу (отлично! уже избавились от log(N)) и текущее состояние ГСЧ (на которое можно наплевать, если нам не нужна воспроизводимость).
К>Правда, цена — это время порождения очередного элемента O(N).
Воспроизводимость нужна, но и хранение состояния ГСЧ -- не проблема. А N-битная таблица -- с чем? Массив битовых флагов, отмечающих уже выданные элементы?

К>Кстати говоря, перетасовывать можно не сразу (потратив O(N) времени), а на каждый акт чтения.
К>- изначально таблица заполняется последовательно: e[t] = t
К>- выборка очередного (t-го) элемента: r = random(n-t); swap(e[t], e[t+r]); return e[t]
Спасибо, полезная оптимизация, приму на вооружение.

Здравствуйте, <Аноним>, Вы писали:

К>>На практике же всё равно придётся хранить как минимум N-битную таблицу (отлично! уже избавились от log(N)) и текущее состояние ГСЧ (на которое можно наплевать, если нам не нужна воспроизводимость).
К>>Правда, цена — это время порождения очередного элемента O(N).

А>Воспроизводимость нужна, но и хранение состояния ГСЧ -- не проблема. А N-битная таблица -- с чем? Массив битовых флагов, отмечающих уже выданные элементы?

Да.

Здравствуйте, Аноним, Вы писали:

А>Задача такая. Есть набор из N элементов (N достаточно велико, порядка сотен тысяч).

А>Требуется извлекать элементы из набора в случайном порядке. При этом, извлечение может быть приостановлено, и впоследствии возобновлено с того же места (т.е. нужно иметь возможность сохранять/восстанавливать текущий порядок перетасованных элементов, а также не выдавать повторно уже извлеченные до приостановки элементы). Объем сохраняемых данных должен быть минимальным по отношению к N -- в идеале, O(1).

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

А в исходной же постановке задачи Вам могут помочь следующие рассуждения:

1) Имеется некая последовательность данных, порядок которой назовём каноническим.
2) Индексы элементов данной последовательности [0,N) сами образуют начальную перестановку ранга 0 (лексикографический порядок).
3) Любая последовательность, полученная перетасовкой, как колода карт, элементов начальной последовательности характеризуется последовательностью индексов элементов начальной последовательности. Заметим, что если в начальной последовательности имеются одинаковые элементы, то могут существовать несколько перестановок, которые будут приводить к одинаковым результатам.
4) Последовательность индексов однозначно характеризуется своим рангом. Следовательно, для указания/генерации/сохранения последовательности неких элементов достаточно указать ранг данной перестановки.
5) Для продолжения выборки из указанной последовательности достаточно указать номер текущего элемента (количество уже сданых карт из перетасованной по рангу r колоды).

Трудности:
1) Ранг перестановки может быть большим числом n!, но всё же его хранение, вероятно, требует места менее, чем вся последовательность индексов.
2) Генерация k-го элемента перестановки ранга r может быть трудной для объектной системы проблемой (Увы! C++ STL <algorithm> даёт только std::prev_permutation/std::next_permutation). Как реализовать UnrankPermutation — лучше бы посмотреть в пакете Combinatorica Wolfram Matematica

Здравствуйте, Аноним, Вы писали:

А>Хм, подбирать параметры генератора, так чтобы он давал полный период на произвольном N? Интересная мысль, надо с ней поэкспериментировать.
А>Придется доставать с полки Кнута

А без Кнута (и без пряника тоже) ?
Сделать генератор периода N можно из генератора с периодом >N достаточно просто — нужно только пропускать "неподходящие" значения .
Важно другое:
1) "плотность" — все значения [0,N) должны реализовываться
2) один такой генератор задаёт максимум N перетасовок (вид генератора задаёт одну перетасовку, а начальный seed -операцию "снятия" k из [0,N) карт этой перетасованной колоды). Т.е. невозможно реализовать все возможные перестановки, а лишь перестановки, полученные циклическим сдвигом одной и той же перестановки.

Последнее — наиболее важно.

Здравствуйте, Кодт, Вы писали:

К>На практике же всё равно придётся хранить как минимум N-битную таблицу (отлично! уже избавились от log(N)) и текущее состояние ГСЧ (на которое можно наплевать, если нам не нужна воспроизводимость).

На практике же честный способ реализуется в следующем виде:
1) Из входной базы случайно выбирается один элемент ("случайность" может быть и воспроизводимой ), которого ещё нет в выходной базе.
2) Элемент обрабатывается и результаты сохраняются в выходной базе (а что, результаты обработки никому не нужны?).

Всё!

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

Ваш вариант соответствует "дереву" без "узлов" с одним "листом". Другой же экстремальный вариант — дерево с однобитовыми "листьями", которые просто "обстригаются" после использования.
На различных стадиях работы (и в различных "ветвях" дерева) могут подбираться наилучшие способы хранения информации. Например, начальные состояния дерева (почти все "карты" доступны — дешевле хранить индекс "разыгранных" карт) симметрично конечным состояниям (почти все карты "разыграны" — дешевле хранить список оставшихся). Способов же хранения, сворачивания, доступа для битовой маски — уйма. Например, тот же RLE, если уж так важна память...

Способы восстановления вычислений:
1) Считываются результаты обработки и регенерируется индекс "сыгранных"/"оставшихся" карт.
2) При "воспроизводимом ГПСЧ" — восстановление индекса выбранных элементов может производиться и без считывания выходных данных на основании начального параметра (seed) генератора и количества обработанных элементов.