c# - 随机排序的长序列

Question

从开始到结束，两种数据类型都是 long的，我想用它们生成一个随机排序的列表。

目前，我正在使用 for 循环来填充列表:

for (var i = idStart; i < idEnd; i++){ list.Add(i); }

然后我使用扩展方法对列表进行洗牌。但是当start和end相差很大(百万级)时，for循环会导致out of memory异常。

是否有更有效、更流畅的方法来生成随机排序的列表 long的，每个数字只出现一次？

Answer 1

Is there a more efficient, sleeker method for producing an randomly sequenced list of long's, where each number only appears once?

是的，如果您消除序列真正随机的要求。使用以下技术。

在不失一般性的情况下，让我们假设您希望为某个 n 生成从 0 到 n-1 的数字。很明显，您可以看到如何生成 x 和 y 之间的数字；只需生成从 0 到 x-y 的数字，然后将 x 添加到每个数字。

找到与 n 互质的随机生成的数字 z。这样做留给读者作为练习。如果这个数字非常大模 n 会有所帮助；如果 z 以 n 为模，则该模式很容易被注意到。

找到一个随机生成的介于 0 和 n-1 之间的数字 m。

现在生成序列 (m) * z % n、(m + 1) * z % n、(m + 2) * z % n，等等。该序列在 (m + n) * z % n 处重复；在此之前它不会重复。同样，确定它不重复的原因留作练习。

很容易看出这不是真正的洗牌，因为生成的可能序列少于 n 平方，而不是真正洗牌可能产生的 n 个阶乘序列。但这可能足以满足您的目的；如果您正在使用类似 System.Random 的东西来进行随机化，那么您已经放弃了真正的洗牌。

我还注意到，许多评论表明大分配应该没有问题。这些评论忘记了 (1) 相关的衡量标准不是盒子中的 RAM 数量，而是最大的连续用户模式地址空间 block 的大小，并且它很容易小于一亿字节一个 32 位进程，(2) 列表数据结构有意过度分配，即 (3) 当列表变满时，必须分配底层数组的副本以将旧列表复制到新列表中，这会增加一倍以上列表的实际内存负载，暂时，以及 (4) 天真地尝试分配一亿字节结构的用户可能会在整个程序中尝试分配一打。您应该始终避免如此大的分配；如果您有需要大量存储的数据结构，请将它们放在磁盘上。