読者です 読者をやめる 読者になる 読者になる

DoubleArrayのBASEとCHECK表現方法

雑記 speed

BASEとCHECKの表現として、(すぐ思いつくものとしては)以下の二つがあると思う。

// 方法1: BASEとCHECK用にそれぞれ配列を用意する
int base[ノード数];
int chck[ノード数];
// 方法2: ノード用に一つの配列を用意し、その各要素がBASEとCHECKフィールドを持つようにする
struct Node {
  int base;
  int chck;
};

Node nodes[ノード数];

これまでは、主にCHECKのサイズを節約するため*1の制限上*2、方法1の表現を使っていた。
ただ方法1では、検索時に二つの配列にアクセスする必要があるので、メモリキャッシュ的な面で、方法2に比べて不利そうな気がする。
前回のDoubleArrayの実装を後者に変更して軽く比べてみたところ、方法2の方が(かなり大雑把な感覚では)5%〜10%*3くらい検索時間が短い感じとなった。
実際の使用ケースで常にそのような結果となるかは分からないし、CHECKに4byteを割り当てるのはもったいない気もするので、即有効という訳ではないが、一応覚えておこうと思う。

*1:CHECKに遷移元ノードではなく、遷移に用いた文字を格納するようにすることで、4byteから1byteに各要素の使用領域を抑えることが可能

*2:CHECKの各要素を1byte(char型)にした場合、Node構造体のサイズは5byteという中途半端な値になってしまう(コンパイラがパディングを入れないと仮定して)。これを配列として保持した場合、アクセス速度が遅くなりそう(各要素のアラインメントが2の乗数に揃っていないので)だし、ファイルに読み書きするにしても扱いにくい(C++以外の言語で読み込もうとした場合は特に)

*3:追記(2010/06/30): 別の環境で試したら三割程度検索時間が短縮された。これくらい効果があるとかなり魅力的に思えてくる。。あと、いまさらだけど、キーセットには前回も使っているWikipediaのタイトルを使用。データサイズは400MB近く。サイズが(結構)大きいということも方法2にした場合の速度改善(率?)に影響しているのかもしれない。