在Go语言中,应该按行优先顺序还是列优先顺序访问2D切片呢?

huangapple go评论79阅读模式
英文:

Should I access 2D slices in row major order or column major order in Go?

问题

假设我有以下代码:

arr := make([][]byte, 10000)
for i := range arr {
    arr[i] = make([]byte, 10000)
}

按照这种方式迭代数组会更快吗?

for row := len(arr) {
    for col := len(arr[0]) {
        // 访问 arr[col][row]
    }
 }

还是按照这种方式?

for col:= len(arr[0]) {
    for row := len(arr) {
        // 访问 arr[col][row]
    }
 }

根据你的代码,第一种方式是更快的。在第一种方式中,外层循环是按照行数进行迭代,内层循环是按照列数进行迭代。这样的迭代方式更符合内存的连续访问模式,可以提高访问效率。而在第二种方式中,外层循环是按照列数进行迭代,内层循环是按照行数进行迭代,这样的迭代方式可能导致内存访问的不连续,效率较低。因此,建议使用第一种方式进行迭代。

英文:

Suppose I have the following code:

arr := make([][]byte, 10000)
for i := range arr {
    arr[i] = make([]byte, 10000)
}

Is it faster to iterate over the array like this?

for row := len(arr) {
    for col := len(arr[0]) {
        // access arr[col][row]
    }
 }

Or like this?

for col:= len(arr[0]) {
    for row := len(arr) {
        // access arr[col][row]
    }
 }

答案1

得分: 2

第二个版本允许执行更少的索引操作:你只需索引一次,就可以得到一行数据。通过索引“内部”切片,可以对一行数据进行迭代。

因此,在迭代切片的切片时,始终首先通过外部切片进行循环,索引一次并获取内部切片。然后,只需通过索引内部切片进行迭代(无需始终索引外部切片)。

这还会导致顺序内存访问,这可能会进一步优化编译器和运行时。

所以,可以这样做:

for _, row := range arr {
    for _, value := range row {
        // 使用 value
    }
}

如果采用另一种方式(先增加内部切片的索引),则始终需要使用双重索引。

英文:

The second version allows to perform less indexing: you index once and you get a row. Iterating over a row can be done by indexing the "inner" slice only.

So when iterating over a slice of slices, always loop first by the outer slice, you index it once and you get an inner slice. You can iterate over it by indexing only the inner slice (no need to index the outer always).

This also results in sequential memory access which may result in further optimization by the compiler and runtime.

So do it like this:

for _, row := range arr {
    for _, value := range row {
        // Use value
    }
}

Doing the other way (when you increase the index of the inner slice first), you always have to use double indexing.

huangapple
  • 本文由 发表于 2022年1月5日 17:24:47
  • 转载请务必保留本文链接:https://go.coder-hub.com/70590466.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定