代码之家 › 专栏 › 技术社区 › Fredou

一对二对三维阵列,为什么速度差?

.net

Fredou · 技术社区 · 15 年前

当我运行此代码时

Enum l
    NormalFor
    NormalForEach
End Enum

Sub Main()
    run(l.NormalFor)
    run(l.NormalForEach)
    Console.Read()
End Sub

Sub run(ByVal l As l)
    Dim one(999999) As Integer
    Dim two(999, 999) As Integer
    Dim three(99, 99, 99) As Integer
    Dim r As Random
    Dim sw As Stopwatch

    r = New Random(42)
    Select Case l
        Case Module1.l.NormalFor
            sw = Stopwatch.StartNew
            For i = 0 To 999999
                one(i) = r.Next
            Next
            sw.Stop()
        Case Module1.l.NormalForEach
            sw = Stopwatch.StartNew
            For Each i In one
                i = r.Next
            Next
            sw.Stop()
    End Select
    Console.WriteLine("One dimension, Array of " & one.Length.ToString & " items " & sw.ElapsedMilliseconds & "ms (" & l.ToString & ")")

    r = New Random(42)
    Select Case l
        Case Module1.l.NormalFor
            sw = Stopwatch.StartNew
            For i = 0 To 999
                For j = 0 To 999
                    two(i, j) = r.Next
                Next
            Next
            sw.Stop()
        Case Module1.l.NormalForEach
            sw = Stopwatch.StartNew
            For Each i In two
                i = r.Next
            Next
            sw.Stop()
    End Select
    Console.WriteLine("Two dimension, Array of " & two.Length.ToString & " items " & sw.ElapsedMilliseconds & "ms (" & l.ToString & ")")

    r = New Random(42)
    Select Case l
        Case Module1.l.NormalFor
            sw = Stopwatch.StartNew
            For i = 0 To 99
                For j = 0 To 99
                    For k = 0 To 99
                        three(i, j, k) = r.Next
                    Next
                Next
            Next
            sw.Stop()
        Case Module1.l.NormalForEach
            sw = Stopwatch.StartNew
            For Each i In three
                i = r.Next
            Next
            sw.Stop()
    End Select
    Console.WriteLine("Three dimension, Array of " & three.Length.ToString & " items " & sw.ElapsedMilliseconds & "ms (" & l.ToString & ")")
End Sub

我得到这个结果

一维,1000000个项目的数组8ms(normalfor)
二维,1000000个项目的数组14ms(normalfor)
三维,1000000个项目的数组13ms(Normalfor)
一维,1000000个项目的数组9ms(NormalForEach)
二维,1000000个项目数组230ms(NormalForEach)
三维,1000000个项目的数组241ms(NormalForEach)

有人知道为什么二维数组会慢很多吗?

2 回复 | 直到 15 年前

Jon Skeet 15 年前

clr支持两种不同的数组类型: 向量和数组 . 矢量是一维的,是基于零的-因此访问一个元素只是一个例子:

ptr = arrayStart + elementSize * elementIndex

并执行非常简单的边界检查: 0 <= elementIndex < arraySize

数组(用clr术语)可以是多维的,并且有不同的下限——因此访问它们需要付出更多的努力。例如,对于二维数组:

ptr = arrayStart + ((elementIndex1 - lowerBound1) * arraySize2
                    + (elementIndex2 - loundBound2)) * elementSize

以及边界检查 rank == 2 && lowerBound1 <= elementIndex1 < upperBound1 && lowerBound2 <= elementIndex2 < upperBound2 .显然,这比简单的情况要慢得多。

基本上,它是为常见的一维零基情况而优化的,但是对于真正使事情变得更好的情况,它支持多维数组。

Simon P Stevens 15 年前

我的最佳猜测是,它是与内存访问。

内存不是三维数组,而是一维数组。因此,您的3D阵列必须转换为1d阵列的数据点,放置在内存中。这意味着,当您访问一维数组中的数据时,它只需获取数组中第一个数据点的内存位置,并添加偏移量即可获得您请求的数据点的位置。

但是对于3D阵列,它必须获取第一个点的位置,将您提供的3个偏移量相乘,以获得一维内存偏移量,然后访问内存中的该点。这会增加额外的开销。它不多8毫秒(甚至200毫秒),超过100万件物品是非常小的。我假设for each使差异更加明显,因为它现在必须计算出数组每个维度的偏移量,并将偏移量向下转换为一维内存位置。如果.NET多维数组是作为数组数组实现的,这意味着for each在处理数组的每个维度的枚举器时必须做很多工作。

[免责声明:这不是事实,只是一个基于记忆知识和如何访问的理论猜测。]

(不要太担心这个问题,只要对数据有意义就使用3D阵列。访问时间的差别是如此之小,你最好让代码易于维护和可读,而不是仅仅为了几毫秒的性能就把三维数据压缩到一维数组中。)