arrays - C 次元オブジェクトを含む N 次元配列は、C オブジェクトを含む N 次元配列とどのように異なるのですか?

Question

オライリーの本からの抜粋:

上記の抜粋から、著者はパフォーマンスの観点から、大きなああまたは他の用語でパフォーマンスの違いが必要な理由と、n x c 次元配列の任意の要素を見つけるための式の根拠を説明します。

追加: 3 次元の例で異なるデータ型が使用されているのはなぜですか? なぜわざわざこれを別の方法で表現するのですか?

Answer 1

この記事では、行列データ構造を表現するさまざまな方法と、単一の配列表現によるパフォーマンスの向上を指摘しているようですが、パフォーマンスが向上する理由については実際には説明していません。

たとえば、NxNxN 行列を表すには、次のようにします。

オブジェクト形式:

Cell {
   int x,y,z;
}
Matrix {
   int size = 10;
   Cell[] cells = new Cell[size];
}

3 配列形式の場合:

Matrix {
    int size = 10;
    int[][][] data = new int[size][size][size];
}

単一の配列で:

Matrx {
    int size = 10;
    int[] data = new int[size*size*size];
}

あなたの質問には、NxN 行列を N*N の長さの単一の配列として表すことでパフォーマンスが向上します。キャッシュによりパフォーマンスが向上します (行列全体を 1 つのチャンクに収めることができないと仮定します)。単一の配列表現は、行列全体がメモリの連続したチャンクにあることを保証します。データがメモリからキャッシュ (またはディスクからメモリ) に移動される場合、チャンクで移動されるため、必要以上のデータを取得することがあります。取得する余分なデータには、必要なデータを囲む領域が含まれます。

たとえば、行列を行ごとに処理しているとします。新しいデータを取得するとき、OS はチャンクごとに N+10 個のアイテムを取得できます。NxN の場合、余分なデータ (+10)は無関係なデータである可能性があります。N*N の長さの配列の場合、余分なデータ (+10) は行列からのものである可能性が最も高くなります。

SGI のこの記事では、もう少し詳細、具体的には適切なキャッシュ使用の原則について説明しているようです 。