更快的争夺数百万

Question

我需要爬出巨大的整数阵列(从1,000,000到80,000,000个元素(。

这些数组是连续创建的(1至n步骤1(，我需要确保没有一个顺序数字丢失 - 因此，我无法创建"随机数"数组。

所以，我使用一个邻近单一的单一(时间很低，约为2ms(创建它们，然后使用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

创建实际上需要很少的miliseconds ...

之后，我争夺数字：

    Shuffle(Huge)

shuffle是在并行/多任务环境中中称为的例程。因此，我需要锁定在Fisher-Yates-durstenfeld常规中使用的随机功能(在交换值和位置中提供良好的熵(：

Fisher-Yates Shuffle

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

我的问题

这种混乱的例程可以随机争夺数组非常好，但是，如果仅需2毫秒即可炒8192个元素，则对于 24,000,000个元素，需要32秒 - 满足我的需求。

您知道任何方法可以增强此过程并使其更快吗？

，或者您知道另一种非确定性随机算法的工作速度比我更快吗？

注意：我已经在并行了。

，我真的不需要"随机"的洗牌，而只是一个非确定的订购。

感谢您的任何帮助

update

由于JDWeng和Hans的相关评论，我觉得预约很有趣：

• 该例程同时使用2个阵列(输入和输出(，并且每个阵列都可以直到32个Mega elements(> 3300万(，这会导致.NET分配几乎1GB内存。这不是我的选择，而是系统需要的。

• 所以，我需要避免创建一个新数组，以将交换操作替换为in-> out操作...

更新II

有些人建议做好良好的做法，但他们没有资格解决问题。让我讨论每个人：

• 使用不同的数组：此过程可以节省一些逐句话，以避免交换(3个操作((3个操作(，以在数组A和B之间使用移动。但是它需要将RAM翻倍请求(两个相同的矩阵(。在Net-Framework内存分配模式(需要免费连续的内存块(上使用巨大的矩阵不是一个选项。

• 使用合并什由算法：它似乎是最需要的解决方案，但是我很想法将shuffle"按矩阵的部分分开"，因为此架构可在基于其中间点的矩阵。我需要更深入地研究整个过程。

• 在主数组的部分上使用并行使用并行带有数组的初始元素。它可以看作是一种确定性的模式(不是选项(。

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

注意，随机数生成器不需要锁，因为每个呼叫都有自己的副本，并且不会在线程中共享。

70％的时间用于阅读从缓冲区(随机(的值。这是因为它可能不在CPU缓存中，必须击中主内存，而阅读缓冲区(MAX(仅为0.5％，因为它被依次读取，并且CPU可以将其预先读取到缓存中。20％是在计算随机数中，因此使用更快的发电机，您可以节省更多的时间，但不多。

最大的胜利将是一种没有随机访问每个元素的数组的算法。我在问题评论中遵循了汉斯·帕斯特(Hans Passant(的建议，并用谷歌搜索了MergeShuffle。它似乎只是这样的算法(多个顺序访问而不是随机单个通行证(。除了允许分区之外，它不需要更多的RAM。

我对它进行了原型型，我看到20％的速度加快了80m的物品，以250万个项目切换到Fisher-Yates。