Случайный алгоритм списка воспроизведения

Question

Мне нужно создать список чисел из диапазона (например, от x до y) в случайном порядке, чтобы каждый порядок имел равный шанс.

Мне нужно это для музыкального плеера, который я пишу на C#, для создания списков воспроизведения в случайном порядке.

Любые идеи?

Спасибо.

EDIT: Меня не интересует изменение исходного списка, просто выберите случайные индексы из диапазона в случайном порядке, чтобы каждый заказ имел равные шансы.

Вот что я wrriten до сих пор:

public static IEnumerable<int> RandomIndexes(int count) 
    { 
     if (count > 0) 
     { 
      int[] indexes = new int[count]; 
      int indexesCountMinus1 = count - 1; 

      for (int i = 0; i < count; i++) 
      { 
       indexes[i] = i; 
      } 

      Random random = new Random(); 

      while (indexesCountMinus1 > 0) 
      { 
       int currIndex = random.Next(0, indexesCountMinus1 + 1); 
       yield return indexes[currIndex]; 

       indexes[currIndex] = indexes[indexesCountMinus1]; 
       indexesCountMinus1--; 
      } 

      yield return indexes[0]; 
     } 
    } 

Это работает, но единственная проблема в том, что мне нужно выделить массив в памяти размером count. Я ищу что-то, что доза не требует выделения памяти.

Спасибо.

Answer 1

Это может быть сложно, если вы не будете осторожны (т. Е. Используя алгоритм перетасовки naïve). Взгляните на Fisher-Yates/Knuth shuffle algorithm для правильного распределения значений.

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

Адрес more detail от Jeff Atwood.

Наконец, вот 1 implementation and description пользователя Jon Skeet.

EDIT

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

Приведем здесь код, который создаст массив равномерно распределенных случайных индексов с использованием алгоритма Knuth-Fisher-Yates (с небольшой модификацией). Вы можете кэшировать полученный массив или выполнить любое количество оптимизаций в зависимости от остальной части вашей реализации.

private static int[] BuildShuffledIndexArray(int size) { 

    int[] array = new int[size]; 
    Random rand = new Random(); 
    for (int currentIndex = array.Length - 1; currentIndex > 0; currentIndex--) { 
     int nextIndex = rand.Next(currentIndex + 1); 
     Swap(array, currentIndex, nextIndex); 
    } 
    return array; 
    } 

    private static void Swap(IList<int> array, int firstIndex, int secondIndex) { 

    if (array[firstIndex] == 0) { 
     array[firstIndex] = firstIndex; 
    } 
    if (array[secondIndex] == 0) { 
     array[secondIndex] = secondIndex; 
    } 
    int temp = array[secondIndex]; 
    array[secondIndex] = array[firstIndex]; 
    array[firstIndex] = temp; 
    } 

ПРИМЕЧАНИЕ: Вы можете использовать ushort вместо int до половины размера в памяти до тех пор, пока вы не более чем 65535 пунктов в списке воспроизведения. Вы всегда можете программно переключиться на int, если размер превышает ushort.MaxValue. Если бы я лично добавил в плейлист более 65 тыс. Элементов, я бы не был шокирован увеличением использования памяти.

Помните, что это управляемый язык. VM всегда резервирует больше памяти, чем вы используете, чтобы ограничить количество раз, когда нужно запросить ОС для большей ОЗУ и ограничить фрагментацию.

EDIT

Ладно, последняя попытка: мы можем смотреть настроить торговлю/производительность памяти от: Вы могли создать список целых чисел, а затем записать его на диск. Затем просто держите указатель на смещение в файле. Затем каждый раз, когда вам нужен новый номер, у вас просто есть дисковый ввод-вывод. Возможно, вы можете найти какой-то баланс здесь и просто прочитать N -размерные блоки данных в память, где N - это номер, с которым вам удобно.

Кажется, что много работы для алгоритма перетасовки, но если вы мертвы для сохранения памяти, то, по крайней мере, это вариант.

Answer 2

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

IEnumerable<Song> GetSongOrder(List<Song> allSongs) 
{ 
    var playOrder = new List<Song>(); 
    while (true) 
    { 
     // this step assigns an integer weight to each song, 
     // corresponding to how likely it is to be played next. 
     // in a better implementation, this would look at the total number of 
     // songs as well, and provide a smoother ramp up/down. 
     var weights = allSongs.Select(x => playOrder.LastIndexOf(x) > playOrder.Length - 10 ? 50 : 1); 

     int position = random.Next(weights.Sum()); 
     foreach (int i in Enumerable.Range(allSongs.Length)) 
     { 
      position -= weights[i]; 
      if (position < 0) 
      { 
       var song = allSongs[i]; 
       playOrder.Add(song); 
       yield return song; 
       break; 
      } 
     } 

     // trim playOrder to prevent infinite memory here as well. 
     if (playOrder.Length > allSongs.Length * 10) 
      playOrder = playOrder.Skip(allSongs.Length * 8).ToList(); 
    }  
} 

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

Answer 3

Я думаю, вы должны придерживаться своего текущего решения (того, которое вы редактируете).

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

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

Answer 4

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

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

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

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

Answer 5

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

private IEnumerable<int> RandomIndexes(int startIndexInclusive, int endIndexInclusive) 
{ 
    if (endIndexInclusive < startIndexInclusive) 
     throw new Exception("endIndex must be equal or higher than startIndex"); 

    List<int> originalList = new List<int>(endIndexInclusive - startIndexInclusive); 
    for (int i = startIndexInclusive; i <= endIndexInclusive; i++) 
     originalList.Add(i); 

    return from i in originalList 
      orderby Guid.NewGuid() 
      select i; 
} 

Answer 6

С логической точки зрения, это возможно. Учитывая список n песен, есть n! перестановки; если вы назначили каждой перестановке число от 1 до n! (или от 0 до n! -1 :-D) и выберите одно из этих чисел в произвольном порядке, затем вы можете сохранить номер перестановки, который вы используете в настоящее время, вместе с исходным списком и индексом текущего песня в перестановке.

Например, если у вас есть список песен {1, 2, 3}, ваши перестановки:

0: {1, 2, 3} 
1: {1, 3, 2} 
2: {2, 1, 3} 
3: {2, 3, 1} 
4: {3, 1, 2} 
5: {3, 2, 1} 

Так только данные мне нужно отслеживать оригинальный список ({1, 2 , 3}), текущий индекс песни (например, 1) и индекс перестановки (например, 3). Затем, если я хочу найти следующую песню для игры, я знаю, что это третья (2, но нулевая) песня перестановки 3, например. Песня 1.

Однако этот метод основана на вас имея эффективные средства определения I-й песни J й перестановки, которые, пока я не имел возможность думать (или кто-то с более сильным математическим фон, чем я могу вставлять) эквивалентен «тогда происходит чудо». Но принцип есть.

Answer 7

Существует несколько способов генерации перестановок без необходимости сохранения состояния. См. this question.

Answer 8

Если вы используете максимальный регистр сдвига с линейной обратной связью, вы будете использовать O (1) памяти и примерно O (1) раз. See here для удобной реализации C (две строки! Woo-hoo!) И таблицы условий обратной связи для использования.

А вот решение:

public class MaximalLFSR 
{ 
    private int GetFeedbackSize(uint v) 
    { 
     uint r = 0; 

     while ((v >>= 1) != 0) 
     { 
      r++; 
     } 
     if (r < 4) 
      r = 4; 
     return (int)r; 
    } 

    static uint[] _feedback = new uint[] { 
     0x9, 0x17, 0x30, 0x44, 0x8e, 
     0x108, 0x20d, 0x402, 0x829, 0x1013, 0x203d, 0x4001, 0x801f, 
     0x1002a, 0x2018b, 0x400e3, 0x801e1, 0x10011e, 0x2002cc, 0x400079, 0x80035e, 
     0x1000160, 0x20001e4, 0x4000203, 0x8000100, 0x10000235, 0x2000027d, 0x4000016f, 0x80000478 
    }; 

    private uint GetFeedbackTerm(int bits) 
    { 
     if (bits < 4 || bits >= 28) 
      throw new ArgumentOutOfRangeException("bits"); 
     return _feedback[bits]; 
    } 

    public IEnumerable<int> RandomIndexes(int count) 
    { 
     if (count < 0) 
      throw new ArgumentOutOfRangeException("count"); 

     int bitsForFeedback = GetFeedbackSize((uint)count); 

     Random r = new Random(); 
     uint i = (uint)(r.Next(1, count - 1)); 

     uint feedback = GetFeedbackTerm(bitsForFeedback); 
     int valuesReturned = 0; 
     while (valuesReturned < count) 
     { 
      if ((i & 1) != 0) 
      { 
       i = (i >> 1)^feedback; 
      } 
      else { 
       i = (i >> 1); 
      } 
      if (i <= count) 
      { 
       valuesReturned++; 
       yield return (int)(i-1); 
      } 
     } 
    } 
} 

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

Вот тестовый код:

static void Main(string[] args) 
    { 
     while (true) 
     { 
      Console.Write("Enter a count: "); 
      string s = Console.ReadLine(); 
      int count; 
      if (Int32.TryParse(s, out count)) 
      { 
       MaximalLFSR lfsr = new MaximalLFSR(); 
       foreach (int i in lfsr.RandomIndexes(count)) 
       { 
        Console.Write(i + ", "); 
       } 
      } 
      Console.WriteLine("Done."); 
     } 
    } 

Имейте в виду, что максимальная ЛРСОС еще никогда не генерировать 0. Я взломал вокруг этого, возвращая термин я - 1. Это работает достаточно хорошо. Кроме того, поскольку вы хотите гарантировать уникальность, я игнорирую что-либо вне диапазона - LFSR генерирует последовательности до двух значений, поэтому в высоких диапазонах он генерирует слишком много значений 2x-1. Они будут пропущены - это все равно будет быстрее, чем FYK.

Answer 9

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

Корпус 1: Если счет < максимальный объем памяти, сгенерируйте плейлист раньше времени и используйте Knuth shuffle (см. Реализацию Jon Skeet, упомянутую в других ответах).

Случай 2: Если ограничение count> = max ограничено, песня, которую нужно воспроизвести, будет определена во время выполнения (я сделаю это, как только начнется воспроизведение песни, чтобы следующая песня была сгенерирована к тому времени, когда текущая песня заканчивается). Сохраните последнее [максимальное ограничение памяти или некоторое количество токенов] количество воспроизводимых песен, сгенерируйте случайное число (R) между 1 и количеством песен, а если R = одна из X последних воспроизводимых песен, сгенерируйте новый R до тех пор, пока он не будет в списке. Воспроизвести эту песню.

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

Answer 10

Вам нужно будет выделить некоторую память, но это не должно быть много. Вы можете уменьшить объем памяти (степень, в которой я не уверен, поскольку я не знаю, что много о кишках C#), используя массив bool вместо int. В лучшем случае это будет использовать (count/8) байт памяти, что не так уж плохо (но я сомневаюсь, что C# фактически представляет bools как отдельные биты).

public static IEnumerable<int> RandomIndexes(int count) { 
     Random rand = new Random(); 
     bool[] used = new bool[count]; 

     int i; 
     for (int counter = 0; counter < count; counter++) { 
      while (used[i = rand.Next(count)]); //i = some random unused value 
      used[i] = true; 
      yield return i; 
     } 
    } 

Надеюсь, что это поможет!

Answer 11

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

using System; 
using System.Collections.Generic; 
using System.Linq; 

namespace Test 
{ 
    class Program 
    { 
     static void Main(string[] a) 
     { 
      Random random = new Random(); 
      List<int> list1 = new List<int>(); //source list 
      List<int> list2 = new List<int>(); 
      list2 = random.SequenceWhile((i) => 
       { 
        if (list2.Contains(i)) 
        { 
         return false; 
        } 
        list2.Add(i); 
        return true; 
       }, 
       () => list2.Count == list1.Count, 
       list1.Count).ToList(); 

     } 
    } 
    public static class RandomExtensions 
    { 
     public static IEnumerable<int> SequenceWhile(
      this Random random, 
      Func<int, bool> shouldSkip, 
      Func<bool> continuationCondition, 
      int maxValue) 
     { 
      int current = random.Next(maxValue); 
      while (continuationCondition()) 
      { 
       if (!shouldSkip(current)) 
       { 
        yield return current; 
       } 
       current = random.Next(maxValue); 
      } 
     } 
    } 
} 

Answer 12

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

const int MaxItemsToShuffle = 20; 
public static IEnumerable<int> RandomIndexes(int count) 
{ 
    Random random = new Random(); 

    int indexCount = Math.Min(count, MaxItemsToShuffle); 
    int[] indexes = new int[indexCount]; 

    if (count > MaxItemsToShuffle) 
    { 
     int cur = 0, subsetCount = MaxItemsToShuffle; 
     for (int i = 0; i < count; i += 1) 
     { 
      if (random.NextDouble() <= ((float)subsetCount/(float)(count - i + 1))) 
      { 
       indexes[cur] = i; 
       cur += 1; 
       subsetCount -= 1; 
      } 
     } 
    } 
    else 
    { 
     for (int i = 0; i < count; i += 1) 
     { 
      indexes[i] = i; 
     } 
    } 

    for (int i = indexCount; i > 0; i -= 1) 
    { 
     int curIndex = random.Next(0, i); 
     yield return indexes[curIndex]; 

     indexes[curIndex] = indexes[i - 1]; 
    } 
}