随机播放列表算法
我需要以随机顺序从一个范围（例如从x到y）创建一个数字列表，这样每个订单都有相同的机会。
对于我用C＃编写的音乐播放器，我需要这个，以随机顺序创建播放列表。
有任何想法吗？
谢谢。
编辑：我对更改原始列表不感兴趣，只需从随机顺序中获取一个范围内的随机索引，以便每个订单都有相同的机会。
这是我到目前为止所写的内容：
public static IEnumerable RandomIndexes(int count) { if (count > 0) { int[] indexes = new int[count]; int indexesCountMinus1 = count - 1; for (int i = 0; i 0) { int currIndex = random.Next(0, indexesCountMinus1 + 1); yield return indexes[currIndex]; indexes[currIndex] = indexes[indexesCountMinus1]; indexesCountMinus1--; } yield return indexes[0]; } } 它正在工作，但唯一的问题是我需要在内存中以count的大小分配一个数组。 我正在寻找不需要内存分配的东西。
谢谢。
如果你不小心（即使用天真的改组算法），这实际上可能很棘手。 看看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 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个大小的数据块读入内存，其中N是你熟悉的数字。
对于一个shuffle算法来说似乎有很多工作，但是如果你在保存内存上已经死了，那么至少它是一个选项。
就个人而言，对于一个音乐播放器，我不会生成一个混洗列表，然后播放它，然后在用完时生成另一个混洗列表，但做更多的事情：
IEnumerable GetSongOrder(List allSongs) { var playOrder = new List (); 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）时间。 请看这里有一个方便的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 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快。
除非你随机播放原始歌曲列表（你说你不想这样做），否则你将不得不分配一些额外的内存来完成你所追求的目标。
如果您事先生成歌曲索引的随机排列（正如您所做的那样），您显然必须分配一些非平凡的内存来存储它，无论是编码还是列表。
如果用户不需要能够看到列表，您可以动态生成随机歌曲顺序：在每首歌曲之后，从未播放的歌曲池中选择另一首随机歌曲。 您仍然需要跟踪已播放的歌曲，但您可以使用位域。 如果你有10000首歌曲，你只需要10000位（1250字节），每一首都代表歌曲是否已播放。
我不知道你的确切限制，但我不得不怀疑，与播放音频所需的数量相比，存储播放列表所需的内存是否显着。
我认为你应该坚持你当前的解决方案（编辑中的那个）。
要重做顺序而不重复并且不使代码行为不可靠，您必须通过保留未使用的索引或通过交换原始列表间接跟踪已使用/喜欢的内容。
我建议在工作应用程序的上下文中检查它，即它是否与系统其他部分使用的内存有任何重要性。
如果在一定数量的记录之后存储器确实是一个问题，并且可以肯定地说，如果达到该存储器边界，则列表中的足够多的项目如果有一些重复则无关紧要，只要同一首歌没有被重复两次，我会用一种组合方法。
情况1：如果count 情况2：如果count> = max memory constraint，则播放的歌曲将在运行时确定（我会在歌曲开始播放时立即播放，因此当前歌曲结束时已生成下一首歌曲） 。 保存最后[最大内存约束或某些标记值]播放的歌曲数量，生成1和歌曲数之间的随机数（R），如果R =播放的最后一首歌曲中的一个，则生成一个新的R，直到它不是在列表中。 播放那首歌。 您的最大内存限制将始终得到维护，但如果您经常播放大量歌曲/频繁获取重复随机数，则情况2可能会受到影响。
你可以使用我们在sql server中做的技巧，使用guid来随机排序集合。 值始终是等随机分布的。
private IEnumerable RandomIndexes(int startIndexInclusive, int endIndexInclusive) { if (endIndexInclusive < startIndexInclusive) throw new Exception("endIndex must be equal or higher than startIndex"); List originalList = new List (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）。 然后，如果我想找到下一首要播放的歌曲，我知道这是第三首（2，但是从零开始）排列3的歌曲，例如歌曲1。
然而，这种方法依赖于你有一种有效的方法来确定第j个排列的第i首歌，直到我有机会思考（或者具有比我可以插入更强的数学背景的人）相当于“那么奇迹发生了“。 但原则是存在的。
有许多方法可以生成排列而无需存储状态。 看到这个问题 。
你将不得不分配一些内存，但它不必太多。 你可以通过使用bool数组而不是int来减少内存占用（我不确定的程度，因为我不太了解C＃的内容）。 最好的情况是这只会使用（计数/ 8）字节的内存，这不是太糟糕（但我怀疑C＃实际上代表bools作为单个位）。
public static IEnumerable 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; } }
希望有所帮助！
正如许多其他人所说，你应该实现THEN优化，并且只优化需要它的部件（你用探查器检查）。 我提供了一个（希望）优雅的方法来获取你需要的列表，这对于性能并不是很关心：
using System; using System.Collections.Generic; using System.Linq; namespace Test { class Program { static void Main(string[] a) { Random random = new Random(); List list1 = new List (); //source list List list2 = new List (); 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 SequenceWhile( this Random random, Func shouldSkip, Func 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 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]; } }