随机播放列表算法

一尘不染

随机播放列表算法

algorithm

我需要以随机顺序创建一个范围（例如，从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。我正在寻找不需要内存分配的东西。

谢谢。

阅读 312

2020-07-28

共1个答案

一尘不染

如果您不小心（例如，使用 幼稚的 改组算法），这实际上可能很棘手。看一下Fisher-Yates /
Knuth随机播放算法以正确分配值。

一旦有了改组算法，其余的就应该很容易了。

这是来自Jeff Atwood的更多细节。

编辑

我不认为有一种解决方案可以满足您两个相互矛盾的要求（首先是随机的，没有重复，第二是不分配任何额外的内存）。我相信您可能会过早优化解决方案，因为除非您是嵌入式的，否则对内存的影响应该可以忽略不计。或者，也许我不够聪明，无法给出答案。

这样，下面的代码将使用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就可以使用而不是内存大小的一半。int如果大小超过，您总是可以通过编程方式切换到ushort.MaxValue。如果我个人将超过65K的项目添加到播放列表中，那么内存使用率的提高不会令我感到震惊。

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

编辑

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

随机播放算法似乎需要做很多工作，但是如果您对保留内存一无所知，那么至少可以选择。

2020-07-28