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

Question

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

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

Есть идеи?

Спасибо.

РЕДАКТИРОВАТЬ: Меня не интересует изменение исходного списка, просто подберите случайные индексы из диапазона в случайном порядке, чтобы у каждого заказа был равный шанс.

Вот что я написал до сих пор:

    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

На самом деле это может быть сложно, если вы не будете осторожны (то есть, используя наивный алгоритм перетасовки). Взгляните на алгоритм Фишера-Йейтса / Кнута shuffle для правильного распределения значений.

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

Вот подробнее от Джеффа Этвуда.

Наконец, вот реализация и описание Джона Скита .

EDIT

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

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

  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 до половины размера памяти, если в вашем плейлисте не более 65 535 элементов. Вы всегда можете программно переключиться на int, если размер превышает ushort.MaxValue. Если бы я лично добавил в список воспроизведения более 65 тыс. Элементов, я бы не был шокирован увеличением использования памяти.

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

EDIT

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

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

Answer 2

Если вы используете регистр сдвига максимальной линейной обратной связи, вы будете использовать O (1) памяти и примерно O (1) время. Смотрите здесь для удобной реализации 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.");
        }
    }

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

Answer 3

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

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 4

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

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

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

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

Answer 5

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

Случай 1: если count

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

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

Answer 6

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

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

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

Answer 7

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

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];
    }
}

Answer 8

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

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 9

Вы должны будете выделить немного памяти, но это не должно быть много. Вы можете уменьшить объем занимаемой памяти (в какой степени я не уверен, так как я мало что знаю о внутренностях 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 10

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