更快地争夺百万数字

Question

我需要打乱巨大的整数数组（从 1,000,000 到 80,000,000 个元素）。

这些数组是按顺序创建的（第 1 步 1 到 n），我需要确保没有一个序号丢失 - 因此我无法创建 "random numbers" 个数组。

因此，我使用单个 FOR-NEXT 创建它们（花费的时间非常短，大约 2 毫秒），并且我使用 Fisher-Yates-Durnstenfeld 随机播放算法，如下所示。

首先我创建数组：

 dim Huge(0 to 80,000,000) as Integer
 For x as integer = 1 to 79,999,999
     Huge(x) = x
 Next

创建真的只需要几毫秒...

之后，我打乱数字：

    Shuffle(Huge)

其中 Shuffle 是 在 Parallel/Multitasking 环境 中调用的例程。因此，我需要锁定 Fisher-Yates-Durstenfeld 例程中使用的 RANDOM 函数（以在交换值和位置时提供良好的熵）：

Fisher-Yates 洗牌

Friend Sub Shuffle(ByRef Buffer As Integer())
  For max As Integer = Buffer.Length - 1 To 1 Step -1
      ExtractRandomItem(Buffer, max)
  Next
End Sub

Friend Sub ExtractRandomItem(ByRef buffer As Integer(), max As Integer)
  Dim random As Integer = GetRandomNumber(max + 1)
  If random = max Then
     random -= 1
  End If

  Dim temp As Integer = buffer(max)
  buffer(max) = buffer(random)
  buffer(random) = temp
End Sub

Friend Function GetRandomNumber(max As Integer) As Integer
  Dim _random As New System.Random
  SyncLock _random
      Return _random.Next(1,max)
  End SyncLock
End Function

我的问题

这个洗牌例程非常适合随机打乱数组，但是，如果打乱 8192 个元素只需要 2 毫秒，那么 24,000,000 个元素需要 32 秒 - 太多时间了为了我的需要。

你知道有什么方法可以增强这个过程并让它更快吗？

或者你知道另一种非确定性洗牌算法比我的算法运行得更快吗？

注意：我已经尝试过PARALLEL.FOR，但无论如何我都没有表达能力（实际上只有几毫秒）。

而且我真的不需要 "random-like" 洗牌，只需要一个不确定的排序。

感谢您的帮助

更新

由于Jdweng和Hans的相关评论，感觉预约很有意思：

例程同时处理 2 个数组（一个输入和一个输出），每个数组可能有 32 个巨型元素（每个元素 > 3300 万），这导致 .NET分配近 1Gb 的 RAM。这不是我的选择，有时是系统要求。
所以，我需要避免创建一个新数组来将 SWAP 操作替换为 in -> out 操作...

更新二

有些人推荐了好的做法，但他们没有资格解决问题。让我逐一讨论：

使用不同的数组：此过程可以节省一些逐个操作的时钟，避免在数组 A 和 B 之间使用移动时交换（3 次操作）。但是它将需要加倍 RAM 请求（两个相同的矩阵）。这不是在 NET-Framework 内存分配模式（需要空闲的连续内存块）上使用巨大矩阵的选项。
使用 MergedShuffle 算法：这似乎是最理想的解决方案，但我担心将随机播放分开 "by pieces of the matrix"，因为这模式根据矩阵的中点对矩阵的各个部分进行处理。我需要深入研究它才能了解整个过程。
在主数组的片段上使用并行：这不是一个选项，因为洗牌将仅符合强加的范围 - 换句话说，我赢了' 让最后的元素与数组的初始元素混洗。它可以看作是一种确定性模式（不是一种选择）。

Answer 1

你表现不佳的主要原因是你为每个随机数创建了一个新的随机数生成器。我只创建一个就获得了 7 倍的速度提升。我还将所有代码合并到一个函数中，以最大限度地优化 .net。最终结果快了不到 10 倍（在我的 32 位 Win7 虚拟机上，对于 80,000,000 个项目，117 秒到 12 秒）。

Friend Sub Shuffle(ByRef Buffer As Integer())
    Dim _random As New System.Random
    For max As Integer = Buffer.Length - 1 To 1 Step -1
        Dim random As Integer = _random.Next(1, max)
        Dim temp As Integer = Buffer(max)
        Buffer(max) = Buffer(random)
        Buffer(random) = temp
    Next
End Sub

请注意，随机数生成器不需要锁，因为对 Shuffle 的每次调用都有自己的副本，并且不会跨线程共享。

70% 的时间花在了从 Buffer 中读取值（随机）上。这是因为它可能不在 CPU 缓存中并且必须访问主内存，而读取 Buffer(max) 仅为 .5%，因为它是按顺序降序读取的，并且 CPU 可以将其预读入缓存。 20% 用于计算随机数，因此使用更快的生成器，您可以节省更多时间但不会太多。

最大的胜利将是一种算法，它不会为每个元素随机访问数组。我听从了 Hans Passant 在问题评论中的建议并用谷歌搜索 MergeShuffle。它似乎就是这样一种算法（多次顺序访问而不是随机单次访问）。而且除了允许分区外，它不需要更多的内存。

我制作了它的原型，我看到 8000 万个项目在 250 万个项目切换到 Fisher-Yates 时速度提高了 20%。

更快地争夺百万数字

Faster Scramble Millions Numbers

vb.net

arrays

algorithm

performance

shuffle

Fisher-Yates 洗牌

我的问题