java - 嵌套循环的顺序对速度有影响吗

Question

假设我有两个数组arrayOne和arrayTwo位置arrayOne.length != arrayTwo.length（假设两个List具有不同的类似情况size()）。以下任何一项是否比另一项提供速度优势？

选项1

for(int i = 0 ; i < arrayOne.length ; ++i) {
   for(int j = 0 ; j < arrayTwo.length ; ++j) {
    //Do something
   }
}

选项 2

for(int i = 0 ; i < arrayTwo.length ; ++i) {
   for(int j = 0 ; j < arrayOne.length ; ++j) {
    //Do something
   }
}

score 7 · Accepted Answer

没有普遍的结果。这取决于您的系统和运行时的各种情况。进行基准测试并获得自己的结果。但是利用更多缓存局部性的通常更快

在二维数组的情况下，在以行为主的语言中，逐行然后逐列迭代通常更快，反之亦然。但这仅当您遍历数组的每个或大部分时。Java既不是行优先也不是列优先，因此没有一种方法在每种情况下都始终更快

如果像这样遍历2 个不同的数组，那么没有人真正知道它的行为方式

score 0 · Accepted Answer

假设

arrayOne.length = m
arrayTwo.length = n

计算时间复杂度

for(int i = 0 ; i < arrayOne.length ; ++i) {         // O(m)
  for(int j = 0 ; j < arrayTwo.length ; ++j) {  // O(n)
     //Do something
  }
}

时间复杂度 - O(m)*O(n) = O(mn)

for(int i = 0 ; i < arrayTwo.length ; ++i) {         // O(n)
  for(int j = 0 ; j < arrayOne.length ; ++j) {  // O(m)
     //Do something
  }
}

时间复杂度 - O(n)*O(m) = O(nm) = O(mn)

因此，假设您的“做某事”在这两种情况下花费的时间相似，那么这两种选择都应该花费相同的时间。

2 回答 2