行優先と列優先の順序

コンピューティングにおいて、行優先順序と列優先順序は、ランダム アクセス メモリなどの線形ストレージに多次元配列を格納する方法です。

これらの順序の違いは、配列のどの要素がメモリ内で連続しているかにあります。行優先順序では、行の連続する要素が互いに隣接して存在しますが、列優先順序では、列の連続する要素に同じことが当てはまります。これらの用語は 2 次元配列、つまり 行列 の行と列を指しますが、行優先と列優先という用語がそれぞれ辞書式順序と列辞書式順序と同等であることに注意することで、これらの順序を任意の次元の配列に一般化できます。また、行列は一般に行ベクトルまたは列ベクトルのコレクションとして表されるため、このアプローチを使用すると、連続するベクトルまたは連続するベクトル要素として効果的に格納されることにも注意してください。このようなデータ格納方法は、それぞれAoS と SoAと呼ばれます。

データレイアウトは、異なるプログラミング言語で書かれたプログラム間で配列を正しく渡すために重要です。また、配列をトラバースする際のパフォーマンスにも重要です。これは、現代のCPUが非連続データよりも連続データをより効率的に処理するためです。これは主に、参照の空間的局所性を利用するCPUキャッシュによるものです。^{[1]さらに、連続アクセスにより、データのベクトルを操作する}SIMD命令を使用できます。磁気テープデータストレージなどの一部のメディアでは、連続アクセスは非連続アクセスよりも桁違いに高速です。^[要出典]

行優先と列優先という用語は、オブジェクトの順序付けに関連する用語に由来しています。多くの属性を持つオブジェクトを順序付ける一般的な方法は、まず 1 つの属性でグループ化して順序付けし、次に各グループ内で別の属性でグループ化して順序付けするという方法です。順序付けに複数の属性が関係する場合、最初の属性はメジャー、最後の属性はマイナーと呼ばれます。順序付けに 2 つの属性が関係する場合は、メジャー属性のみに名前を付ければ十分です。

配列の場合、属性は各次元に沿ったインデックスです。数学表記の行列の場合、最初のインデックスは行を示し、 2番目は列を示します。たとえば、行列 の場合、エントリはその最初の行と2番目の列にあります。この規則はプログラミング言語の構文にも引き継がれていますが、^[2]インデックスは1ではなく0から始まることがよくあります。^[3]${\displaystyle A}$${\displaystyle a_{1,2}}$

行は最初のインデックスで示され、列は2 番目のインデックスで示されますが、これによって次元間のグループ化順序が暗示されることはありません。したがって、行優先または列優先のどちらの方法でインデックスをグループ化および順序付けるかの選択は、慣例の問題です。同じ用語は、さらに高次元の配列にも適用できます。行優先のグループ化は左端のインデックスから始まり、列優先のグループ化は右端のインデックスから始まり、それぞれ辞書式順序とコレクシコグラフィック (またはコレックス) 順序になります。

例えば、配列

${\displaystyle A=a_{y,x}={\begin{bmatrix}\color {Blue}a_{11}&\color {Blue}a_{12}&\color {Blue}a_{13}\\\color {Orange}a_{21}&\color {Orange}a_{22}&\color {Orange}a_{23}\end{bmatrix}}}$

保存方法は 2 つ考えられます。

プログラミング言語はこれをさまざまな方法で処理します。Cでは、多次元配列は行優先順で格納され、配列インデックスは行優先順 (辞書式アクセス順) で記述されます。

一方、Fortranでは、配列は列優先順で格納されますが、配列インデックスは行優先順 (コレクシコグラフィカル アクセス順) で記述されます。

C のように複数ステップのインデックス付けを伴うの使用は、 Fortran のようA[i][j]な中立表記とは対照的に、と書き直すことができ、行部分を中間変数に代入して別の式でインデックス付けすることもできるため、いわば構文上の理由から行優先順序をほぼ必然的に意味することに注意してください。(他の意味合いは想定すべきではありません。たとえば、Fortran は表記法上は列優先ではありませんし、上記の意味合いさえも新しい言語では意図的に回避される可能性があります。) A(i,j)(A[i])[j]A[i]

何らかの理由で行優先の環境で列優先の順序を使用する、またはその逆を行う場合、回避策の 1 つは、インデックスに非標準的な役割を割り当てること (列に最初のインデックス、行に 2 番目のインデックスを使用する) であり、もう 1 つは、1 次元配列内の位置を明示的に計算して言語構文を回避することです。もちろん、慣例から逸脱すると、従来の言語機能やその他のコードとの必要なやり取りの度合いに応じてコストが増大する可能性があります。これは、間違いが発生しやすくなる (行列の乗算順序を逆にすることも忘れる、コード保守中に慣例に戻すなど) だけでなく、要素を積極的に再配置する必要があるという形でも発生します。これらすべてを、パフォーマンスの向上などの本来の目的と比較して検討する必要があります。C などの行優先の言語では、行単位でループを実行することが推奨され、列優先の言語ではその逆が推奨されます。

多次元配列をサポートするプログラミング言語またはその標準ライブラリでは、通常、これらの配列に対して行優先または列優先のネイティブな格納順序が採用されています。

行優先順序は、C / C++ / Objective-C（Cスタイルの配列用）、PL/I、^[4] Pascal、^[5] Speakeasy、^[要出典]、SAS ^[6]で使用されます。

列優先順序はFortran、^{[7] [8]} IDL、^[7] MATLAB、^[8] GNU Octave、Julia、^[9] S、S-PLUS、^[10] R、^[11] Scilab、^[12] Yorick、Rasdamanで使用されています。^[13]

密な配列ストレージの一般的な代替手段は、Iliffeベクトルを使用することです。これは通常、行自体ではなく、同じ行内の要素へのポインタを連続して格納します（行優先順など）。これらは、Java、^[14] C# / CLI / .Net、Scala、^[15]およびSwiftで使用されます（古い順） 。

さらに密度が低いのは、 Python ^[16]やWolfram MathematicaのWolfram言語[ ^17]などのリストのリストを使用することです。

別のアプローチとしては、例えばLuaのテーブルのテーブルを使う方法がある。^[18]

多次元配列のサポートは外部ライブラリによって提供される場合もあり、各次元にストライド値があり、行優先または列優先という 2 つの解釈が可能な任意の順序付けをサポートする場合もあります。

行優先順序はNumPy ^[19] (Pythonの場合)のデフォルトです。

列優先順序はEigen ^[20]とArmadillo（どちらもC++用） のデフォルトです。

特殊なケースとしては、グラフィックス処理用のOpenGL (およびOpenGL ES ) があります。「線形代数および関連分野の最近の数学的処理では、ベクトルが常に列として扱われる」ため、設計者の Mark Segal は、ベクトルを行として記述する前身のIRIS GLの慣例をこれに置き換えることにしました。互換性のために、変換行列は、座標優先 (= 列優先) の順序ではなく、ベクトル優先 (= 行優先) の順序で格納され、その後、彼は「OpenGL の行列は列優先の順序で格納される」というトリックを使用しました。^[21]これは実際にはプレゼンテーションにのみ関係がありました。行列の乗算はスタックベースであり、乗算後と解釈できるからです。しかし、さらに悪いことに、個々の要素がまたは、事実上としてアクセスされるため、C ベースのAPIを通じて現実が漏れてしまい、残念ながら設計者が採用しようとした規則が混乱し、これは後に追加されたOpenGL シェーディング言語でも保持されました(ただし、これにより、代わりに名前で座標にアクセスすることもできます。例: )。その結果、多くの開発者は、列を最初のインデックスとすることが列優先の定義であると単純に宣言するようになりましたが、これは明らかに Fortran のような実際の列優先言語では当てはまりません。 M[vector][coordinate]M[column][row]M[vector].y

Torch（Lua用）のデフォルトの順序が列優先^[22]から行優先^[23]に変更されました。

配列のインデックスを交換することが配列転置の本質であるため、行優先で格納されているが列優先で読み取られる配列 (またはその逆) は転置されているように見えます。メモリ内で実際にこの再配置を実行することは通常、コストのかかる操作であるため、一部のシステムでは、個々の行列が転置されて格納されるように指定するオプションが提供されています。プログラマーは、実際の使用状況 (計算で配列が再利用される回数を含む) に基づいて、メモリ内の要素を再配置するかどうかを決定する必要があります。

例えば、基本線形代数サブプログラム関数には、どの配列が転置されるかを示すフラグが渡されます。^[24]

この概念は、2 次元以上の配列にも一般化されます。

次元がN _k ( k =1... d ) であるd次元配列の場合、この配列の特定の要素はd 個(ゼロベース)のインデックスのタプルによって指定されます。 ${\displaystyle N_{1}\times N_{2}\times \cdots \times N_{d}}$ ${\displaystyle (n_{1},n_{2},\ldots ,n_{d})}$${\displaystyle n_{k}\in [0,N_{k}-1]}$

行優先順では、最後の次元は連続しているため、この要素のメモリ オフセットは次のように表されます。 $${\displaystyle n_{d}+N_{d}\cdot (n_{d-1}+N_{d-1}\cdot (n_{d-2}+N_{d-2}\cdot (\cdots +N_{2}n_{1})\cdots ))=\sum _{k=1}^{d}\left(\prod _{\ell =k+1}^{d}N_{\ell }\right)n_{k}}$$

列優先順序では、最初の次元は連続しているため、この要素のメモリ オフセットは次のように与えられます。 ここで、空の積は乗法単位元、つまり です。 $${\displaystyle n_{1}+N_{1}\cdot (n_{2}+N_{2}\cdot (n_{3}+N_{3}\cdot (\cdots +N_{d-1}n_{d})\cdots ))=\sum _{k=1}^{d}\left(\prod _{\ell =1}^{k-1}N_{\ell }\right)n_{k}}$$${\textstyle \prod _{\ell =1}^{0}N_{\ell }=\prod _{\ell =d+1}^{d}N_{\ell }=1}$

与えられた順序では、次元kのストライドは、上記の右側の合計の インデックスn _{k の}前の括弧内の乗算値によって与えられます。

より一般的には、与えられた配列に対してd!通りの順序が可能であり、次元の順列ごとに 1 つずつあります (行優先と列優先は 2 つの特別なケースにすぎません)。ただし、ストライド値のリストは必ずしも互いの順列であるとは限りません。たとえば、上記の 2 行 3 列の例では、ストライドは行優先の場合は (3,1)、列優先の場合は (1,2) です。

• 配列（データ構造）
• プログラミング言語の比較（配列）
• インデックスの起源、プログラミング言語間の配列型のもう 1 つの違い
• 行列表現
• モートン順序、多次元データを1次元インデックスにマッピングする別の方法。ツリーデータ構造で役立ちます。
• CSR 形式、メモリに疎行列を格納する技術
• ベクトル化（数学）は、行列を対応する列主ベクトルに変換することと同等である。

• Donald E. Knuth 著『The Art of Computer Programming Volume 1: Fundamental Algorithms』第 3 版、セクション 2.2.6 (Addison-Wesley: New York、1997 年)。