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

Personally, for a music player, I wouldn't generate a shuffled list, and then play that, then generate another shuffled list when that runs out, but do something more like:

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();
    }    
}

This would make songs picked in order, as long as they haven't been recently played. This provides "smoother" transitions from the end of one shuffle to the next, because the first song of the next shuffle could be the same song as the last shuffle with 1/(total songs) probability, whereas this algorithm has a lower (and configurable) chance of hearing one of the last x songs again.

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

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

С логической точки зрения это возможно. Учитывая список 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 -й перестановки, которая, пока у меня не будет возможности подумать (или кто-то с более сильным математическим опытом чем я могу вставить) эквивалентно «тогда происходит чудо». Но принцип есть.

I think you should stick to your current solution (the one in your edit).

To do a re-order with no repetitions & not making your code behave unreliable, you have to track what you have already used / like by keeping unused indexes or indirectly by swapping from the original list.

I suggest to check it in the context of the working application i.e. if its of any significance vs. the memory used by other pieces of the system.

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

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

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 генерирует только последовательности до степени двойки, поэтому в высоких диапазонах он будет генерировать слишком много значений wost case 2x-1. Они будут пропущены - это все равно будет быстрее, чем FYK.

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

Случай 1: Если count <максимальное ограничение памяти, заранее сгенерируйте список воспроизведения и используйте перемешивание Knuth (см. реализацию Джона Скита, упомянутую в других ответах).

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

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

Unless you shuffle the original song list (which you said you don't want to do), you are going to have to allocate some additional memory to accomplish what you're after.

If you generate the random permutation of song indices beforehand (as you are doing), you obviously have to allocate some non-trivial amount of memory to store it, either encoded or as a list.

If the user doesn't need to be able to see the list, you could generate the random song order on the fly: After each song, pick another random song from the pool of unplayed songs. You still have to keep track of which songs have already been played, but you can use a bitfield for that. If you have 10000 songs, you just need 10000 bits (1250 bytes), each one representing whether the song has been played yet.

I don't know your exact limitations, but I have to wonder if the memory required to store a playlist is significant compared to the amount required for playing audio.

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

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

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

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

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

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

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