Saturday, 19 September 2009

配列

ついでに、もう一つ。学生は配列大好きで、なんでも配列で書く。これは、いくつかの点でまずい。

 配列には、配列の大きさがあるが、配列自体に大きさがない処理系がある

つまり、Cのことなんだけど。毎回、添字の範囲のチェックをしろ、とは言わないが、

 「インデックスが配列をはみ出さないように保証する必要がある」

次に、

 配列には局所性がない。あるいは、局所性を表現できない

もちろん、本質的に局所性のないアクセスを要求される場合もある。アクセスパターンを予測できない場合とか。でも、実際には、なんらかの局所性があるのが普通。

計算機のメモリは一見、均一なアクセスタイムを保証した配列に見える。最初は、そういう理解でも構わない。でも、現実には、レジスタ/キャッシュ/二次キャッシュ/メインメモリ上のバルク転送/仮想記憶と言った何段階もの構造を持っている。

更に、GCが絡むと、アクセスの局所性だけでなく時間的な局所性を考慮する必要がある。

これらは、アルゴリズムの実装に合わせて変更される。と言うことは、

 裸の配列をランダムにアクセスする

と言う事自体よろしくない。もちろん、信号処理とか、それが必須なものも多いが、それは巨大な配列と言うよりは「局所的に使われる小さな配列 = ベクタ」が多いと思う。大きな均一な配列ってのは、実際には使われない。

まぁ、C++ とかだと配列の演算子を変更して「配列に見せるだけ」ってのも可能なんだけど、配列に見せることが重要だとは思わない。

また、固定長配列ってのはメモリ管理が難しい。malloc/free を繰り返すと穴が開くし。今は、意図的に穴を空けた malloc とかあるみたいだけど、賛成できないです。

配列へのポインタとサイズみたいな組みと、その上でのIteratorという形に書くべきだと思う。

Post a Comment