随机播放列表算法

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

如果你不小心(即使用天真的洗牌算法),这实际上可能很棘手.看看Fisher-Yates/Knuth shuffle算法,以便正确分配值.

一旦你有了洗牌算法,其余的应该很容易.

以下是Jeff Atwood 的更多细节.

最后,这里是Jon Skeet的实现和描述.

编辑

我不相信有一个解决方案可以满足你的两个相互矛盾的要求(首先,随机没有重复,第二个不分配任何额外的内存).我相信你可能过早地优化你的解决方案,因为内存含义应该可以忽略不计,除非你被嵌入.或者,也许我只是不够聪明才能得出答案.

有了这个,这里的代码将使用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.如果我个人在播放列表中添加了超过65K的项目,我不会因内存利用率增加而感到震惊.

还要记住,这是一种托管语言.VM将始终保留比您使用的内存更多的内存,以限制它要求操作系统获得更多RAM并限制碎片的次数.

编辑

好的,最后一次尝试:我们可以调整性能/内存权衡:您可以创建整数列表,然后将其写入磁盘.然后只保留指向文件中偏移量的指针.然后,每当您需要一个新号码时,您只需要处理磁盘I/O. 也许你可以在这里找到一些平衡点,只需将N个大小的数据块读入内存,其中N是你熟悉的数字.

对于一个shuffle算法来说似乎有很多工作,但是如果你在保存内存方面已经死了,那么至少它是一个选项.

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只生成最大2的幂序列,所以在高范围内,它会产生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 /(总歌曲)概率,而该算法具有较低的(和可配置的)再次听到最后一首x歌之一的机会.