随机播放列表算法

如果你不小心的话(例如,使用 纳维 洗牌算法)。看看 Fisher-Yates/Knuth shuffle algorithm 以便正确分配值。

一旦你有了洗牌算法,剩下的应该很容易。

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

最后,这是乔恩·斯基特的 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;
  }

注释 你可以用 ushort 而不是 int 只要播放列表中的项目不超过65535个,内存大小就可以减半。您可以通过编程方式切换到 int 如果尺寸超过 ushort.MaxValue .如果我个人在播放列表中添加了超过65K个项目,我不会为内存利用率的提高而感到震惊。

记住,这也是一种管理语言。虚拟机将始终保留比您使用的内存更多的内存,以限制向操作系统请求更多RAM和限制碎片所需的次数。

编辑

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

对于随机播放算法来说似乎有很多工作要做,但是如果你已经做好了保存内存的准备,那么至少这是一个选项。

就个人而言,对于音乐播放器,我不会生成无序播放列表,然后播放该列表,然后在列表用完时生成另一个无序播放列表,但要执行以下操作:

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歌曲的可能性较低(且可配置)。

如果使用最大线性反馈移位寄存器,将使用内存的O(1)和大致的O(1)时间。 See here 对于一个方便的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只生成2次幂的序列,因此在高范围内,它将生成wost case 2x-1过多的值。这些将被跳过-这将仍然比FYK更快。

除非你洗牌原来的歌曲列表(你说过你不想这样做),否则你必须分配一些额外的内存来完成你想要的。

如果您事先(如您所做的那样)生成歌曲索引的随机排列,那么显然必须分配一些非常重要的内存来存储它,不管是编码的还是列表的。

如果用户不需要看到列表,您可以即时生成随机歌曲顺序:在每首歌曲之后,从未播放歌曲池中选择另一首随机歌曲。您仍然需要跟踪哪些歌曲已经播放过,但是您可以使用位字段进行播放。如果你有10000首歌,你只需要10000位(1250字节),每一位代表歌曲是否已经播放过。

我不知道您的确切限制,但我想知道存储播放列表所需的内存是否比播放音频所需的内存大。

我认为你应该坚持你当前的解决方案(编辑中的那个)。

要在不重复的情况下重新排序,而不使代码行为不可靠,必须通过保留未使用的索引或从原始列表中交换来间接跟踪已使用/喜欢的内容。

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

如果在一定数量的记录之后,记忆真的是一个问题,而且可以肯定地说,如果达到了记忆边界,列表中有足够的条目,不管是否有重复,只要同一首歌没有重复两次,我就会使用组合方法。

案例1:如果count<max memory约束,则提前生成播放列表并使用knuth shuffle(参见其他答案中提到的jon skeet的实现)。

案例2:如果count>=max memory constraints,将在运行时确定要播放的歌曲(我会在歌曲开始播放后立即执行此操作,以便下一首歌曲在当前歌曲结束时生成)。保存播放的最后[max memory constraint,or some token value]歌曲数,生成介于1和歌曲计数之间的随机数(r),如果r=播放的最后x首歌曲中的一首,则生成一个新的r,直到它不在列表中。播放那首歌。

您的最大内存限制将始终保持不变,尽管在案例2中,如果您经常播放大量歌曲/偶然获得重复随机数,性能可能会受到影响。

您可以使用我们在SQL Server中所做的一个技巧,使用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)。然后,如果我想找到下一首要播放的歌,我知道它是排列3的第三首(2首,但从零开始)歌,例如第1首。

然而,这种方法依赖于您有一种有效的方法来确定 我 第三首歌 J 这个排列,在我有机会思考(或者有比我更强大的数学背景的人)之前,它相当于“然后奇迹就发生了”。但原则就在这里。

有许多方法可以生成排列,而不需要存储状态。见 this question .

你将不得不分配一些内存,但不必太多。你可以通过使用bool数组而不是int来减少内存占用(我不确定的程度,因为我对c的胆量不太了解)。最佳情况下,这只使用(count/8)字节的内存,这并不太糟糕(但我怀疑c实际上表示bool为单个位)。

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