12

配列を使用して Matrix コンストラクトを実装する場合、どちらがより効率的ですか? 1D 配列または配列の配列 (2D) を使用していますか?

1D実装ではインデックスを計算する必要がある要素のX座標とY座標が既にあるため、2Dの方が効率的だと思います。

編集：Javaを使用して実装されています

4

6 に答える 6

13

「効率的」は包括的な用語ではありません。

配列の配列ソリューションは、ストレージの点でより効率的であり、配列がまばらな場合があります (つまり、null ポインターを使用して、すべてゼロの行列行を表すことができます)。これは（Cで）次のようになります。

int *x[9];

それぞれ"int *"が別々に割り当てられる場所。

2D 配列 (必ずしも配列の配列である必要はありません) は、メモリ位置を逆参照する必要なく、数学でメモリ位置を計算するため、一般的に高速です (速度の点で効率的です)。私は構造について話している：

int x[9][9];

次の形式の 1D 配列:

int x[81];

正しいセルを見つけるために、ある時点で計算を行う必要があるため (コンパイラーに実行させるのではなく、コードで手動で実行する必要があるため)、同等の 2D バージョンよりも高速になる可能性はほとんどありません。

要件として Java が追加された場所を編集した後:

Java 2D 配列は配列の配列 (1D 配列に必要な 1 回とは対照的に 2 回のメモリ アクセスが必要) の配列であるため、手動インデックス計算を使用する 1D 配列の方が高速である可能性があります。したがって、宣言して使用する代わりに、次のようにします。

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

次の方法で速度を上げることができます。

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

数式をどこかで混同しないように注意する必要があります (つまり、4 と 7 を誤って交換しないでください)。

この速度の違いは、Java が内部でどのようにコーディングされているかを考えていることに基づいているため、間違っている可能性があります (しかし、私はそれを疑っています :-)。私のアドバイスは、常に最適化の質問と同様に、測定し、推測しないでください!

于 2009-04-09T03:39:01.997 に答える
4

これまでの回答とは一線を画し、1D 配列の方が高速である可能性が高い理由を次のように提案します。

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

1D 実装は伝統的に A[x + (width *y)] です。幅がレジスタ (またはリテラル) の場合、これは 2 回のルックアップではなく、2 つの演算操作と 1 回のルックアップを意味します。ルックアップは数学演算よりも桁違いに遅いため、幅がわずかな割合でもレジスタにある場合、またはリテラルである場合は、高速になります。

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

于 2009-04-09T04:02:02.767 に答える
2

この質問は、実際にサンプル コードを書いて結果をテストしないと答えられないと思います。たとえば、この質問では次の結果が見つかりました。

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

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

私は非常に慎重に仮定を立てます。 たとえば、2D 配列の行をループしている場合、インライン インデックス計算で 1D 配列を使用している場合、Java はインデックス ルックアップを最適化したり、範囲外チェックを実行したりする可能性があります。

目的のプラットフォームで速度をテストするための簡単なプログラムを作成することをお勧めします。

于 2009-04-09T04:19:50.027 に答える
1

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

于 2009-04-09T03:40:39.497 に答える
0

線形代数計算の基礎として1D配列を使用する、機械エンジニアとしてのキャリアの中で使用した商用の有限要素パッケージ。有限要素法は、大きく、まばらで、縞模様の行列になります。これらのゼロ要素をすべて帯域外に格納しても意味がありません。

使用される2D配列が表示されるのは、小さな学術的な問題またはスパースではない問題（境界要素法など）の場合のみです。

于 2009-04-09T09:57:35.673 に答える
0

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

  • コードが少ない -> 書く時間が少ない
  • コード行が少ないということは、バグが少ないことを意味し (特定のプログラマーにとって KLOC あたりのバグはほぼ一定であるため)、見つけやすくなります (数行のコードではうまく隠すことができないため)。
  • アルゴリズムがタスクに適合しない場合は、100 行ではなく 10 行の方が置き換えが容易です。
  • コンパクトな実装は、通常、ライブラリを使用するコードをクリーンにするクリーンなインターフェイスにつながります(そのため、効果が倍増します)。これにより、クライアント コードがより効率的になる場合、ライブラリの実装がより複雑になる可能性もあります (つまり、他のすべてをより単純にするために 1 つの場所に労力を集中させます)。

また、アクセスパターンにも大きく依存します。いつもマトリックス全体を歩いていますか？まばらですか？行と列のどちらを処理しますか?

極端な場合 (10 億個の行と 10 個のセルしか使用されていない列を持つ行列)、aHashMapはどの配列実装よりも効率的です。他の問題については、問題に応じてアプローチを混合する方が効率的です (たとえば、HashMapセルが巨大な空きスペースで「凝集」する場合のミニマトリックスの配列)。

問題が行/列を見つけてからそれらの値を処理することを要求する場合、2D アプローチを使用する方が効率的である可能性があります。そのため、最初のアクセスで配列が返され、境界や 1 回限りのエラーを気にせずに処理できます。等

于 2009-04-09T10:57:59.257 に答える