📂プログラミング

2次元配列の行優先と列優先

概要 ¹

行列や2次元配列の行優先^row-majorと列優先^column-majorについて説明する。簡単に言えば、配列を参照しながらどの方向で読むかを好むかについての話だ。

違い

ウィキペディアによると、いくつかのプログラミング言語やライブラリは、次のようにネイティブな行/列優先が決まっているという。

• 行優先: 行列で行を先に取り、左から右に読む方法だ。

  • C/C++/Objective-C
  • PL/I
  • Pascal
  • Speakeasy
  • SAS
  • Rasdaman

• 列優先: 行列で列を先に取り、上から下へ読む方法だ。

  • Fortran
  • MATLAB
  • GNU Octave
  • S-Plus
  • R
  • Julia
  • Scilab

なぜこの違いが生じるのか

まず、計算機科学的な説明²よりも直感的に理解しよう。コンピュータも人間も、好まない方式で行列を読むときにどのような問題があるか想像してみよう。例えば、列優先で行列を読む人だとしよう。

$$ \begin{bmatrix} 1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 9 \end{bmatrix} $$

上の行列を読むとき、列優先なら$1,2,3,4,5,\cdots$のように楽に読める。しかし、無理やり行優先で読むと、$1,4,7,2,5,\cdots$のように不自然な順番で読むことになる。

コンピュータの立場から見ると、論理的な配列が物理的なメモリに割り当てられており、我々の命令に従って行列を読むが、プログラミング言語の設計に従って単純に読むのと、行/列を混ぜながら読む方式とでは大きな違いがある。

なぜ行優先か

与えられた行列を画面に表示するプログラムを作ると想像してみよう。常識的に、上の行から右に向かって書いて改行し、次の行を書いていく方式になるはずだ。だから、ほとんどのプログラミング言語もコンソール窓で上から下に向かっていくため、行優先を選ぶのが自然だ。

なぜ列優先か

フォートラン、マットラボ、R、ジュリア…

ラインアップが素晴らしい。一目で科学、計算の言語が列優先を採用していることが分かる。そもそも行列というのが連立方程式の省略形から来ていることを考えれば、当然のことだ。世の中に行列を横方向に読む数学者はいない。当然、行に沿って上から下に、つまり列優先で読むのが常識だ。

パフォーマンス比較

julia> size = 10^4
10000

julia> M = rand(size, size);

ジュリア言語を基準にベンチマークを行った。下の2つのコードフェンスを見ると、行/列の順番だけを変えて実行時間を測定したが、行を先に読んだときは36秒、列優先のジュリアでは列を先に読んだときは20秒かかり、ほぼ2倍の顕著なパフォーマンス差があることが確認できた。

julia> X = zeros(size, size);

julia> @time for i in 1:size
           for j in 1:size
               X[i,j] = (M[i,j] + 1)
           end
       end
 36.088533 seconds (489.82 M allocations: 8.789 GiB, 4.64% gc Time)

julia> X = zeros(size, size);

julia> @time for j in 1:size
           for i in 1:size
               X[i,j] = (M[i,j] + 1)
           end
       end
 19.936053 seconds (489.82 M allocations: 8.789 GiB, 7.59% gc Time)