随机播放列表算法

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的数组。我正在寻找不需要内存分配的东西。

谢谢。

- Alon Gubkin

---

参见：https://dev59.com/l3M_5IYBdhLWcg3wp06l - Ryan Emerle

不能修改原始列表或分配额外的内存，就无法跟踪重复项。这会导致用户体验不佳。 - Mark Ransom

完全同意Mark Ransom的观点。 - Peter Perháč

Answer 1

如果您不小心使用一个天真的洗牌算法，这实际上可能会很棘手。请查看Fisher-Yates/Knuth shuffle algorithm以正确分配值。

一旦您有了洗牌算法，其余部分应该很容易。

这里是Jeff Atwood提供的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 个项目添加到播放列表中，我不会对增加的内存利用率感到惊讶。

还记得这是一种托管语言。虚拟机将始终保留比您使用的更多的内存，以限制它需要请求更多 RAM 的次数并减少碎片。 编辑 好吧，最后一次尝试：我们可以寻找性能/内存权衡的调整方法：您可以创建整数列表，然后将其写入磁盘。然后只需保留指向文件中偏移量的指针。每次需要新数字时，您只需处理磁盘 I/O。也许您可以在此处找到一些平衡点，并仅将大小为 N 的数据块读入内存，其中 N 是您满意的某个数字。

对于洗牌算法来说，似乎是很多工作，但如果您决心节省内存，那么至少这是一个选项。

- Ryan Emerle

---

你也有iPod Shuffle吗？ ;) - Frankie

@Ryan Emerle，我删除了我的答案，因为没有必要弄乱。Jon Skeet的实现链接真的非常有启发性。+1！ - Frankie

谢谢，这很好，但它会改变列表中的元素，而我不想改变列表中的元素。我只想要随机索引...无论如何还是谢谢。 - Alon Gubkin

@Alon，我同意这不是最优雅的解决方案，但内存利用率将是可忽略的。对于一个包含 100,000 个索引的 int[]，你需要大约 400K 的内存。或者，你可以选择一个随机索引，然后保持一个单独的已使用索引列表，但这样会有同样的问题，即实现不够严谨。如果可以的话，请发布您选择的答案；我很想看看您想出了什么。 - Ryan Emerle

如果@Alon不那么吝啬内存（400k，真的吗？），他可以将订单与歌曲一起存储在歌曲所保存的任何结构中，然后您可以随意调整它们的顺序。最坏的情况下，每首歌曲只需添加1个Int32…这是您能做到的最好的事情。在这个问题上花费任何额外的时间都是浪费。 - user7116

Answer 2

如果您使用最大线性反馈移位寄存器，您将使用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只能生成二次幂以下的序列，因此在高范围内，它将生成最坏情况下多2x-1个值。这些值将被跳过 - 这仍然比FYK更快。

- plinth

---

需要仔细的数学分析才能确保LFSR生成的数字足够“随机”。除此之外，我很想看看这在实践中是如何工作的。 - Ryan Emerle

@RyanEmerle 并不一定需要进行仔细的数学分析。检查“可接受”的随机性的有效方法是使用LFSR生成2D整数坐标并将其呈现到窗口中。然后只需寻找明显的模式即可。 - Ash

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首歌曲的几率。

- FryGuy

Answer 4

除非你打算重新洗牌原歌曲列表（你说你不想这样做），否则你需要分配一些额外的内存来实现你想要的目标。

如果你事先生成了歌曲索引的随机排列（就像你正在做的那样），你显然需要分配一些非平凡的内存来存储它，可以编码或作为列表。

如果用户不需要看到列表，你可以在播放时动态生成随机歌曲顺序：每首歌曲后，从未播放歌曲的池中选择另一首随机歌曲。你仍然需要跟踪哪些歌曲已经播放过，但你可以使用位域来完成。如果你有10000首歌曲，你只需要10000个位（1250字节），每个位表示歌曲是否已经播放过。

我不知道你的确切限制是什么，但我必须想知道存储播放列表所需的内存是否与播放音频所需的内存相比显著。

- Donnie DeBoer

Answer 5

有许多生成排列的方法，无需存储状态。请参见此问题。

- FryGuy

Answer 6

从逻辑上讲，这是可能的。给定一个由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）排列的第三首歌曲，例如歌曲1。

然而，这种方法依赖于您有一种有效的方法来确定第j个排列的第i首歌曲，直到我有机会思考（或者有比我更强的数学背景的人插话）等价于“然后奇迹发生了”。但原则在那里。

- FacticiusVir

---

有趣的是，这只适用于非常小的_n_值.. 50！= 3.04140932 × 10^64 - Ryan Emerle

生成排列并选择正确的索引非常容易和快速 - 您只需要进行一些整数除法和模运算即可。但是，这也需要修改现有列表或创建新列表，因为您需要跟踪已经选择的元素。还有Ryan提到的这些数字的大小问题，但如果您能够准确地生成和操作它们，算法仍将有效，因为您可以直接生成排列 - 但您可能会遇到非本机类型的额外开销，使其变慢。 - Michael Madsen

Answer 7

如果在一定数量的记录之后真的存在内存问题，并且可以安全地说，如果达到了该内存限制，则列表中有足够的项目，使得重复项并不重要，只要不重复播放同一首歌曲，我会使用组合方法。

情况1：如果数量<最大内存限制，请提前生成播放列表并使用Knuth shuffle（请参阅Jon Skeet的实现，在其他答案中提到）。

情况2：如果数量> =最大内存约束，则在运行时确定要播放的歌曲（我会尽快这样做，以便下一首歌曲在当前歌曲结束时已经生成）。 保存播放过的最后[max memory constraint或某个令牌值]首歌曲，生成介于1和歌曲计数之间的随机数（R），如果R =最后X首播放的歌曲之一，请生成一个新的R，直到它不在列表中。 播放那首歌曲。

您的最大内存限制将始终得到保持，但是如果您播放了很多歌曲/偶然频繁重复获得随机数字，则情况2的性能可能会受到影响。

- BarrettJ

Answer 8

我认为你应该坚持你目前的解决方案（即你编辑过的那个）。

如果要进行无重复的重新排序，并且不使你的代码变得不可靠，你必须通过保留未使用的索引或间接地从原始列表中交换来跟踪你已经使用或喜欢的内容。

我建议在工作应用程序的上下文中检查它，即它是否与系统的其他部分使用的内存有任何关系。

- eglasius

Answer 9

正如其他人所说，你应该先实现再优化，只优化需要的部分（通过性能分析器检查）。我提供了一种（希望）优雅的方法来获取你需要的列表，它并不太关心性能：

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

- RCIX

Answer 10

如果不分配额外的内存，几乎不可能完成它。如果您担心分配的额外内存量，您可以随机选择一个子集并在其中进行洗牌。在每首歌曲播放之前，您将获得重复，但是使用足够大的子集，我保证很少有人会注意到。

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

- ICR