イリフベクター

コンピュータプログラミングにおいて、Iliffe ベクトル(ディスプレイとも呼ばれる) は、多次元配列を実装するために使用されるデータ構造です。

n次元配列 ( n ≥ 2)の Iliffe ベクトルは、( n − 1) 次元配列へのポインタ のベクトル (または 1 次元配列) で構成されます 。配列要素のアドレス計算を実行するときに、高価な乗算操作を回避するためによく使用されます。また、三角配列、三角行列、その他の不規則な形状の配列などのギザギザの配列を実装するためにも使用できます。このデータ構造は、 John K. Iliffeにちなんで名付けられました。

欠点としては、要素にアクセスするために複数の連鎖ポインタ間接参照が必要であること、最適化コンパイラがプリフェッチできるようにn次元配列の次の行を決定するために余分な作業が必要であることが挙げられます。これらは両方とも、CPU がメイン メモリよりも大幅に高速なシステムでは遅延の原因となります。

2 次元配列の Iliffe ベクトルは、単にデータのベクトルへのポインタのベクトルです。つまり、Iliffe ベクトルは配列の列を表し、各列要素は行ベクトルへのポインタです。

Java、Python (多次元リスト)、Ruby、Visual Basic .NET、Perl、PHP、JavaScript、Objective-C (行優先のC スタイル配列ではなく、 NSArray を使用する場合)、Swift、Atlas Autocodeなどの言語の多次元配列は、 Iliffe ベクトルとして実装されています。 Iliffe ベクトルは、 OLAP 製品Holosでスパース多次元配列を実装するために使用されました。

Iliffe ベクトルは、各次元の添え字のストライド係数とオフセット値を含む Fortranなどの言語のdope ベクトルとは対照的です。

• John K. Iliffe (1961)。 「数値計算における Genie システムの使用」。自動プログラミング年次レビュー。2 :25。doi : 10.1016/S0066-4138(61)80002-5。

• 「第 3 章: データ構造マッピング」。コンパイル テクニック。Associates Technology Literature Applications Society。2015年5 月 5 日閲覧。