Реализация перемешивания на небесном музыкальном автомате

Question

Как можно было бы использовать перемешивание для "Небесного музыкального автомата"?

Точнее, в каждый момент времени t возвращать равномерное случайное число в диапазоне 0..n (t), чтобы во всей последовательности не было повторений, а n () увеличивалось с течением времени.

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

идеальное решение было бы возможно на существующем оборудовании - как бы я заполучил список из шести миллионов песен в 8 МБ DRAM? Точно так же большое количество песен усугубляет O (n) выбор времени.

- Для генератора LCG, с учетом частично исчерпанного LCG на 0..N ₀ , это может быть переведено на другой LCG на 0..N ₁ (где N1> N0), которые не повторяют исчерпанную последовательность.
- Проверка того, что конкретная песня уже сыграна, кажется, быстро выходит из-под контроля, хотя это может быть единственным способом? Есть ли эффективная структура данных для этого?

Answer 1

Я предпочитаю делать такой случайный случайный выбор, чтобы иметь список, и каждый раз, когда я выбираю случайный элемент в диапазоне от [0-N), я удаляю его из этого списка. В вашем случае, когда новые элементы будут добавлены в каталог, он также будет добавлен в еще не выбранный список. Как только вы дойдете до конца, просто перезагрузите все песни обратно в список.

EDIT:

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

Вот резюме:

1. Добавить начальные элементы в список
2. Индекс выбора i в случайном порядке (из набора [0,N))
3. Удалить элемент по индексу i
4. Заменить отверстие в i на элемент Nth (или ноль, если i == Nth) и уменьшить N
5. Для новых предметов просто добавьте в конец списка и при необходимости увеличьте N
6. Если вам когда-нибудь удастся воспроизвести все песни (что я сомневаюсь, если у вас есть песни 6M), то добавьте все песни обратно в список, вспените, промойте и повторите.

Поскольку вы пытаетесь работать с довольно большими наборами, я бы порекомендовал использовать БД. Простая таблица, состоящая в основном из двух полей: id и "pointer" (где "pointer" - это то, что говорит вам о песне для воспроизведения, которая может быть GUID, FileName и т. Д., В зависимости от того, как вы хотите это сделать ). Имейте индекс на id, и вы должны получить очень приличную производительность с постоянством между запусками приложения.

РЕДАКТИРОВАТЬ для предела 8 МБ:

Хм, это немного усложняет ... В 8 МБ вы можете хранить максимум ~ 2M записей с использованием 32-битных ключей.

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

Answer 2

С ограничением в 8 МБ для 6 миллионов песен, явно нет места для хранения даже одного 32-битного целого числа для каждой песни. Если вы не готовы сохранить список на диске (в этом случае см. Ниже).

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

Если вы готовы ослабить требование оперативной памяти 8 МБ для 6 миллионов песен или перейти на диск (например, с помощью отображения памяти), вы можете сгенерировать последовательность из 1..n в начале, перемешать ее с fisher-yates и всякий раз, когда добавляется новая песня, выберите случайный элемент из пока не воспроизведенного раздела, вставьте туда новый идентификатор и добавьте оригинальный идентификатор в конец списка.

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

Answer 3

Вы можете использовать связанный список внутри массива: Чтобы создать начальный список воспроизведения, используйте массив, содержащий что-то вроде этого:

 struct playlistNode{
  songLocator* song;
  playlistNode  *next;
};
struct playlistNode arr[N];

Также сохраняйте указатель 'head' и 'freelist';

Заполните его в 2 прохода:
1. заполните arr всеми песнями в каталоге в порядке 0..N.
2. случайно перебрать все индексы, заполнив указатель next;

Удаление проигранных песен: O (1):

head=cur->next;
cur->song=NULL;
freelist->next = freelist;
cur->next=freelist;
freelist=cur;

Вставка новых песен также является O (1): произвольно выбирайте индекс массива и исправляйте новый узел.

node = freelist;
freelist=freelist->next;
do {
i=rand(N);   
} while (!arr[i].song);  //make sure you didn't hit a played node
node->next = arr[i].next;
arr[i].next=node;

Answer 4

Вы можете просто сгенерировать последовательность чисел от 1 до n, а затем перетасовать ее, используя перемешивание Фишера-Йейтса. Таким образом, вы можете гарантировать, что последовательность не повторится, независимо от n.

Answer 5

Хотя решение Эриха, вероятно, лучше для вашего конкретного случая использования, проверка, если песня уже была воспроизведена, выполняется очень быстро (амортизируется O (1)) со структурой на основе хеша, такой как set в Python или hashset<int> в C ++.