c# - 随机播放列表算法

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 algorithm以正确分配值(value)。

有了改组算法后，剩下的就很简单了。

这是 more detail来自杰夫·阿特伍德。

最后，这是 Jon Skeet 的 implementation and description .

编辑

我不相信有一个解决方案可以满足您的两个相互冲突的要求(首先，是随机的，没有重复，其次是不分配任何额外的内存)。我相信您可能会过早地优化您的解决方案，因为除非您是嵌入式的，否则内存影响应该可以忽略不计。或者，也许我只是不够聪明，无法得出答案。

有了这个，下面的代码将使用 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;
  }

注意:只要不超过 65,535，就可以使用 ushort 而不是 int 将内存大小减半播放列表中的项目。如果大小超过 ushort.MaxValue，您始终可以通过编程方式切换到 int。如果我个人将超过 65K 项添加到播放列表，我不会对内存利用率的增加感到震惊。

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

编辑

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

洗牌算法似乎需要做很多工作，但如果您执意要节省内存，那么至少这是一个选择。