java - ネストされたループの順序は速度に関係しますか

Question

2 つの配列arrayOneとarrayTwowhere があるとします (異なるを持つarrayOne.length != arrayTwo.length2 つの同様のケースを想定します)。次のいずれかが他のものよりも速度の利点を提供しますか?Listsize()

オプション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

一般的な結果はありません。システムと実行時のさまざまな状況によって異なります。ベンチマークを行い、独自の結果を取得します。ただし、より多くのキャッシュの局所性を利用するものは、多くの場合より高速です

2D 配列の場合、通常、行優先の言語では行単位で反復してから列単位で反復する方が高速であり、その逆も同様です。ただし、それは配列のすべてまたは大部分をループする場合のみです。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