行優先と列優先

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

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

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

説明と例

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

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

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

例えば、配列

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 つの方法で保存できます。

住所	行優先順	列優先順
0	$\color {Blue}a_{11}$	$\color {Blue}a_{11}$
1	$\color {Blue}a_{12}$	$\color {Orange}a_{21}$
2	$\color {Blue}a_{13}$	$\color {Blue}a_{12}$
3	$\color {Orange}a_{21}$	$\color {Orange}a_{22}$
4	$\color {Orange}a_{22}$	$\color {Blue}a_{13}$
5	$\color {Orange}a_{23}$	$\color {Orange}a_{23}$

プログラミング言語によって処理方法は異なります。C言語では、多次元配列は行優先順で格納され、配列のインデックスは行優先順（辞書式アクセス順）で記述されます。

C: 行優先順（辞書式アクセス順）、ゼロベースのインデックス
住所 `x + N_x*y`	アクセス `A[y][x]`	価値 $a_{y,x}$
0	`A[0][0]`	$a_{11}$
1	`A[0][1]`	$a_{12}$
2	`A[0][2]`	$a_{13}$
3	`A[1][0]`	$a_{21}$
4	`A[1][1]`	$a_{22}$
5	`A[1][2]`	$a_{23}$

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

Fortran: 列優先順序（コレクシコグラフィー的アクセス順序）、1から始まるインデックス
住所 `y + N_y*(x-1)`	アクセス `A(y,x)`	価値 $a_{y,x}$
1	`A(1,1)`	$a_{11}$
2	`A(2,1)`	$a_{21}$
3	`A(1,2)`	$a_{12}$
4	`A(2,2)`	$a_{22}$
5	`A(1,3)`	$a_{13}$
6	`A(2,3)`	$a_{23}$

Fortran のA[i][j]中立表記ではなく、C のように複数ステップのインデックスを付けるを使用すると、と書き換えることができ、行部分を中間変数に代入して別の式でインデックスを付けることもできるため、構文上の理由から、行優先順序になることがほぼ必然的であることに注意してください。(その他の意味合いは想定すべきではありません。たとえば、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）が挙げられます。「近年の線形代数や関連分野の数学的処理では、ベクトルは常に列として扱われる」ため、設計者のマーク・シーガルは、前身である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 個(ゼロベース) のインデックスのタプルによって指定されます。 $N_{1}\times N_{2}\times \cdots \times N_{d}$ $(n_{1},n_{2},\ldots ,n_{d})$ $n_{k}\in [0,N_{k}-1]$

行優先順では最後の次元は連続しているので、この要素のメモリオフセットは次のように表されます。 $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}$

列優先順序では、最初の次元は連続しているので、この要素のメモリオフセットは次のように与えられます。ここで、空の積は乗法単位元、つまりです。 $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形式、メモリに疎行列を格納する技術
ベクトル化（数学）は、行列を対応する列主ベクトルに変換することと同等である。

参考文献

^ 「キャッシュメモリ」。Peter Lars Dordal . 2021年4月10日閲覧。
^ 「配列と書式付きI/O」FORTRANチュートリアル. 2016年11月19日閲覧。
^ 「なぜ番号付けはゼロから始めるべきなのか」EWダイクストラアーカイブ。 2017年2月2日閲覧。
^ 「言語リファレンスバージョン4 リリース3」（PDF） . IBM . 2017年11月13日閲覧。配列に指定された初期値は、行優先順（最終添え字が最も急速に変化）で配列の連続する要素に割り当てられます。
^ "ISO/IEC 7185:1990(E)" (PDF)。2つ以上のインデックス型のシーケンスを指定する配列型は、シーケンスの最初のインデックス型をインデックス型として持ち、シーケンスの最初のインデックス型を除いたインデックス型のシーケンスを指定する配列型をコンポーネント型とし、元の仕様と同じコンポーネント型を指定する配列型の省略表記とする。
^ 「SAS® 9.4 言語リファレンス：概念、第6版」（PDF）。SAS Institute Inc. 2017年9月6日。p. 573。2017年11月18日閲覧。右から左へ、右端の次元は列を表し、次の次元は行を表します。[...] SASは、配列の左上隅から順にすべての行を埋めていくことで、変数を多次元配列に配置します（行優先順と呼ばれます）。
^ ab 「列、行、配列の多数決」www.nv5geospatialsoftware.com . 2024年7月31日閲覧。
^ ab MATLAB ドキュメント、MATLAB データストレージ (Mathworks.co.uk から 2014 年 1 月取得)。
^ 「多次元配列」. Julia . 2020年11月9日閲覧。
^ Spiegelhalter et al. (2003, p. 17): Spiegelhalter, David ; Thomas, Andrew; Best, Nicky ; Lunn, Dave (2003年1月)、「データのフォーマット：S-Plus形式」、WinBUGSユーザーマニュアル（PDF）（バージョン1.4版）、ケンブリッジ、英国：MRC Biostatistics Unit、公衆衛生研究所、 2003年5月18日時点のオリジナル（PDF）からアーカイブ
^ R入門、セクション5.1：配列（2010年3月取得）。
^ 「多次元データを使ったFFT」Scilab Wiki . 2017年11月25日閲覧。Scilabは配列を列優先形式で保存するため、列の要素は線形形式で隣接しています（つまり、1間隔で離れています）。
^ 「rasdamanにおける配列の内部表現」rasdaman.org . 2025年3月30日閲覧。
^ 「Java言語仕様」Oracle . 2016年2月13日閲覧。
^ "object Array". Scala標準ライブラリ. 2016年5月1日閲覧。
^ 「Python標準ライブラリ: 8. データ型」。 2017年11月18日閲覧。
^ 「ベクトルと行列」Wolfram . 2017年11月12日閲覧。
^ 「11.2 – 行列と多次元配列」。 2016年2月6日閲覧。
^ “N次元配列（ndarray）”. SciPy.org . 2016年4月3日閲覧。
^ "Eigen: ストレージ順序". eigen.tuxfamily.org . 2017年11月23日閲覧。ストレージ順序が指定されていない場合、Eigenはデフォルトでエントリを列優先で保存します。
^ 「列ベクトルと行ベクトル」。 2017年11月12日閲覧。
^ "Tensor" . 2016年2月6日閲覧。
^ "Tensor". Torchパッケージリファレンスマニュアル. 2016年5月8日閲覧。
^ 「BLAS（基本線形代数サブプログラム）」。 2015年5月16日閲覧。

出典

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

[Peter_Lars_Dordal-1] 「キャッシュメモリ」。Peter Lars Dordal . 2021年4月10日閲覧。

[2] 「配列と書式付きI/O」FORTRANチュートリアル. 2016年11月19日閲覧。

[3] 「なぜ番号付けはゼロから始めるべきなのか」EWダイクストラアーカイブ。 2017年2月2日閲覧。

[4] 「言語リファレンスバージョン4 リリース3」（PDF） . IBM . 2017年11月13日閲覧。配列に指定された初期値は、行優先順（最終添え字が最も急速に変化）で配列の連続する要素に割り当てられます。

[5] "ISO/IEC 7185:1990(E)" (PDF)。2つ以上のインデックス型のシーケンスを指定する配列型は、シーケンスの最初のインデックス型をインデックス型として持ち、シーケンスの最初のインデックス型を除いたインデックス型のシーケンスを指定する配列型をコンポーネント型とし、元の仕様と同じコンポーネント型を指定する配列型の省略表記とする。

[6] 「SAS® 9.4 言語リファレンス：概念、第6版」（PDF）。SAS Institute Inc. 2017年9月6日。p. 573。2017年11月18日閲覧。右から左へ、右端の次元は列を表し、次の次元は行を表します。[...] SASは、配列の左上隅から順にすべての行を埋めていくことで、変数を多次元配列に配置します（行優先順と呼ばれます）。

[IDL-7] 「列、行、配列の多数決」www.nv5geospatialsoftware.com . 2024年7月31日閲覧。

[MATLAB-8] MATLAB ドキュメント、MATLAB データストレージ (Mathworks.co.uk から 2014 年 1 月取得)。

[9] 「多次元配列」. Julia . 2020年11月9日閲覧。

[WinBUGS-10] Spiegelhalter et al. (2003, p. 17): Spiegelhalter, David ; Thomas, Andrew; Best, Nicky ; Lunn, Dave (2003年1月)、「データのフォーマット：S-Plus形式」、WinBUGSユーザーマニュアル（PDF）（バージョン1.4版）、ケンブリッジ、英国：MRC Biostatistics Unit、公衆衛生研究所、 2003年5月18日時点のオリジナル（PDF）からアーカイブ

[11] R入門、セクション5.1：配列（2010年3月取得）。

[12] 「多次元データを使ったFFT」Scilab Wiki . 2017年11月25日閲覧。Scilabは配列を列優先形式で保存するため、列の要素は線形形式で隣接しています（つまり、1間隔で離れています）。

[13] 「rasdamanにおける配列の内部表現」rasdaman.org . 2025年3月30日閲覧。

[14] 「Java言語仕様」Oracle . 2016年2月13日閲覧。

[15] "object Array". Scala標準ライブラリ. 2016年5月1日閲覧。

[16] 「Python標準ライブラリ: 8. データ型」。 2017年11月18日閲覧。

[17] 「ベクトルと行列」Wolfram . 2017年11月12日閲覧。

[18] 「11.2 – 行列と多次元配列」。 2016年2月6日閲覧。

[19] “N次元配列（ndarray）”. SciPy.org . 2016年4月3日閲覧。

[20] "Eigen: ストレージ順序". eigen.tuxfamily.org . 2017年11月23日閲覧。ストレージ順序が指定されていない場合、Eigenはデフォルトでエントリを列優先で保存します。

[21] 「列ベクトルと行ベクトル」。 2017年11月12日閲覧。

[22] "Tensor" . 2016年2月6日閲覧。

[23] "Tensor". Torchパッケージリファレンスマニュアル. 2016年5月8日閲覧。

[24] 「BLAS（基本線形代数サブプログラム）」。 2015年5月16日閲覧。