配列の配列（2D）または1D配列を使用して、より効率的な行列を実装しますか？

Question

配列を使用してMatrixコンストラクトを実装すると、より効率的になりますか？ 1D配列、または配列の配列（2D）を使用していますか？

私はあなたがすでに1次元実装では、あなたが指数を計算しなければならない要素のXとY座標を持っているように、2Dが、より効率的であると思うだろう。

編集：それはJavaの

Answer 1

を使用して実装されている「効率的に」キャッチオール用語ではありません。

アレイのサブアレイ溶液は、アレイ（すなわち、すべてのゼロの行列の行を表すためにNULLポインタを使用することができる）疎であってもよい記憶の点でより効率的です。これは（C言語で）：

int *x[9]; 

ここで、それぞれ"int *"は別々に割り当てられます。それはメモリロケーションを参照を解除することなく、数学とメモリ位置をうまくいくので、（必ずしも配列の配列ではない）

A 2次元アレイは、一般的に速い（効率的な速度の点で）であろう。私は、コンストラクトの話：フォームの

int x[9][9]; 

A 1D配列：あなたはまだいくつかの計算を行う必要があるので、

int x[81]; 

は、任意の速い同等の2Dバージョンよりも可能性は低いです正しいセルを見つける（コンパイラに指示するのではなく、コード内で手動で）。 Javaは要件として加えた編集後

：

Iは、Java 2Dアレイは（1Dアレイに必要な1とは対照的に、二つのメモリアクセスを必要とする）の配列の多様性の配列であると信じ手作業でインデックスを計算する1D配列のほうが速いかもしれません。だから、代わりに宣言および使用する：

int x[width][height]; 
x[a][b] = 2; 

あなたともっとスピードを得ることができます：

int x[width*height]; 
x[a*height+b] = 2; 

あなたはただ、ドンあなたはどこにでも（すなわちアップ混合式を取得しないように注意する必要があります不注意にスワップ4と7）。

この速度差は、私が間違っていることができるようにJavaがカバーの下にコード化されていると思います（私は:-)それを疑う方法に基づいています。私のアドバイスは、いつものように最適化の質問のために、の尺度ですが、推測しないでください！

Answer 2

言語によっては、何ら違いはありません。実際の問題は、2D行列がどのように割り当てられるかです。それはX * Yバイトの連続した1つのスペースか、またはXサイズのY個の独立した配列として割り当てられていますか？後者は通常、疎行列を作成するときに実行されます。

Answer 3

私は、これまでの回答でランクを壊し、1次元配列は、恐らく高速であることを、次の理由を提案するつもりです。

2次元配列には2つのメモリアクセスが含まれます。 A [x] [y]はまずA [x]を検索し、次にその配列[y]の別の検索を行う必要があります。

1D実装は伝統的にA [x +（幅* y）]になります。幅がレジスタ（またはリテラル）の場合、これは2回の検索ではなく2回の演算と1回の検索を意​​味します。ルックアップは数学演算よりも遅いオーダーであるため、幅が時間のわずかな割合でも登録されている場合、またはリテラルである場合は速くなります。

もちろん、標準の警告が適用されます。常にプロファイリングし、早すぎる最適化を避けます。

Answer 4

実際にサンプルコードを書いて結果をテストすることなく、この質問にはと答えることはできません。例えば、this questionは以下の結果を見出した。

sum(double[], int): 2738 ms (100%) 
sum(double[,]):  5019 ms (183%) 
sum(double[][]): 2540 ms (93%) 

ジグザグ配列が最も速く、1次元配列が続き、多次元配列が続きます。ギザギザの配列が最も速いのはおそらく人々が予測したものではないでしょう。これらの結果は、Javaではさまざまな最適化（Javaでは多次元配列なし）があるため、おそらく役に立たないでしょう。

私は前提を非常に慎重に考えています。たとえば、2D配列の行をループしている場合、インラインインデックス計算を伴う1D配列を使用している場合、Javaはインデックスルックアップを最適化したり、範囲外のチェックを行うことができない場合があります。

希望のプラットフォームで速度をテストする簡単なプログラムを書くことをお勧めします。

Answer 5

1Dアレイを線形代数計算の基礎として使用して機械的エンジニアとして私のキャリアで使用した市販の有限要素パッケージです。有限要素法の結果、大規模で疎でバンデッドな行列が得られます。これらのゼロ要素をバンドの外に保存することは意味をなさない。

使用される2D配列は、学術的な問題やスパースでない問題（境界要素のメソッドなど）にのみ使用されます。

Answer 6

一般的なケースでは、アルゴリズムの最も効率的な実装は、コード量が最も少ないアルゴリズムです。これは多くの理由のためである：

• 少ないコード - >それをコードの
• 少ないラインを書くためのより少ない時間は（見つけるのは容易です（KLOCあたりのバグが与えられたプログラマのためのかなり一定であるため）以下のバグを意味し、
• あなたのアルゴリズムがタスクに合っていない場合は、10行ではなく10行で置き換えが簡単です
• コンパクトな実装は、通常、クリーンなインターフェイスにつながりますのコードはライブラリをきれいにしています（効果が増えます）。これにより、クライアントコードをより効率的にする（つまり、作業を単一の場所に集中させて、他のすべてをよりシンプルにする）なら、より複雑なライブラリの実装につなげることもできます。

アクセスパターンにも大きく依存します。あなたはいつも行列全体を歩いていますか？それはまばらですか？行や列を処理する方が好きですか？

極端な例（10行しか使用されていない10億のセルが使用されているマトリックス）では、HashMapはどのアレイ実装よりも効率的です。他の問題では、問題に応じてアプローチを混在させる方が効率的です（たとえば、巨大な空き領域にセルが詰まったときのミニ行列の配列のHashMap）。

問題が行/列を見つけてその値を処理するよう求められた場合は、2Dアプローチを使用する方が効率的かもしれません。最初のアクセスでは配列を返します。オフエラーなど