13

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

谢谢。

4

12 回答 12

31

如果您不小心，这实际上可能会很棘手（即，使用简单的洗牌算法）。查看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<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 将始终保留比您使用的内存更多的内存，以限制它需要向操作系统请求更多 RAM 并限制碎片的次数。

编辑

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

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

于 2009-11-29T19:51:39.257 回答
8

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

于 2009-12-02T21:22:11.787 回答
6

就个人而言，对于音乐播放器，我不会生成一个混洗列表，然后播放它，然后在用完时生成另一个混洗列表，而是做更多类似的事情：

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

这将使歌曲按顺序挑选，只要它们最近没有播放过。这提供了从一个 shuffle 结束到下一个 shuffle 的“更平滑”的过渡，因为下一个 shuffle 的第一首歌曲可能是与最后一个 shuffle 相同的歌曲，概率为 1/（总歌曲），而该算法具有较低的（和可配置）再次听到最后 x 首歌曲的机会。

于 2009-11-29T20:35:50.947 回答
3

除非你对原始歌曲列表进行洗牌（你说你不想这样做），否则你将不得不分配一些额外的内存来完成你所追求的。

如果您事先生成歌曲索引的随机排列（正如您所做的那样），您显然必须分配一些重要的内存量来存储它，无论是编码还是作为列表。

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

我不知道您的确切限制，但我想知道存储播放列表所需的内存与播放音频所需的内存量相比是否显着。

于 2009-12-01T23:08:44.473 回答
2

有许多无需存储状态即可生成排列的方法。看到这个问题。

于 2009-12-02T21:13:29.570 回答
1

如果在一定数量的记录之后内存确实是一个问题，并且可以肯定地说，如果达到了内存边界，那么列表中有足够的项目是否有重复无关紧要，只要同一首歌没有重复两次，我会使用组合方法。

案例 1：如果 count < max memory constraint，提前生成播放列表并使用 Knuth shuffle（参见 Jon Skeet 的实现，在其他答案中提到）。

情况 2：如果 count >= max memory constraint，要播放的歌曲将在运行时确定（我会在歌曲开始播放时立即执行，以便在当前歌曲结束时已经生成下一首歌曲） . 保存最后[max memory constraint, or some token value]播放的歌曲数，生成一个介于1和歌曲计数之间的随机数（R），如果R = X最后播放的歌曲中的一首，则生成一个新的R，直到它不是在列表中。播放那首歌。

您的最大内存限制将始终得到维护，尽管如果您播放了很多歌曲/偶然经常获得重复随机数，则在情况 2 中性能可能会受到影响。

于 2009-12-02T21:38:54.207 回答
1

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

要进行不重复的重新排序并且不使您的代码行为不可靠，您必须通过保留未使用的索引或通过从原始列表交换间接跟踪您已经使用/喜欢的内容。

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

于 2009-12-01T22:54:44.467 回答
1

从逻辑的角度来看，这是可能的。给定一个包含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个排列的第i首歌曲，直到我有机会思考（或具有比我更强大的数学背景的人）之前，它相当于“然后奇迹发生了”。但原理是有的。

于 2009-12-02T15:07:33.830 回答
0

正如许多其他人所说，您应该实施 THEN 优化，并且只优化需要它的部分（您使用分析器检查）。我提供了一种（希望）优雅的方法来获取您需要的列表，它并不真正关心性能：

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);
            }
        }
    }
}
于 2009-12-04T09:56:58.510 回答
0

您将不得不分配一些内存，但不必太多。您可以通过使用 bool 数组而不是 int 来减少内存占用（我不确定的程度，因为我不太了解 C# 的内容）。最好的情况下，这将只使用 (count / 8) 字节的内存，这还不错（但我怀疑 C# 实际上将布尔值表示为单个位）。

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

希望有帮助！

于 2009-12-02T21:54:02.147 回答
0

您可以使用我们在 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;
}
于 2009-12-02T15:02:04.637 回答
0

如果不分配额外的内存，几乎不可能做到这一点。如果您担心分配的额外内存量，您总是可以选择一个随机子集并在它们之间随机播放。在每首歌曲播放之前，您都会重复播放，但如果有足够大的子集，我保证很少有人会注意到。

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];
    }
}
于 2009-12-06T14:19:41.670 回答