Essenの開発メモ#0004
スキップリスト
- いろいろ考えて、Essenの内部ではスキップリストを使いまくることにした。
- つまりcrit-bit-treeはいったん使わない方向で。
- ちなみにこれは内部構造的な話でしかないので、言語仕様には全く影響ないです（笑）。
- 基本構造としてはWikipediaの「Indexable skiplist」を使う。
- それで、ノードの高さは乱数では決め「ない」。リンクの幅が簡単に得られるのを利用して、不自然な長さになったら近くのノードのレベルを上げ下げして調節する。つまりリバランスする。
- もともとのスキップリストでは、リバランスがいらないことがアルゴリズムのシンプルさにつながっていて長所の一つだったが、Essen内のスキップリストではその長所は捨てて安定動作を目指したことになる。
- pをいくつにするか。1/2か1/4か1/8か1/16か。
- 仮にN=65536のスキップリストがあったとする。リバランスによって、幅は理想値の1/2～2倍に調整されているとする。ポインタの幅はひとまず4バイトを仮定する。
| p | 検索時に幅をたどる回数(平均) | 1ノードあたりの追加容量(平均) | | 1/2 | 1x16=16 | 14バイト | | 1/4 | 3x8=24 | 7.7バイト | | 1/8 | 1+7x5=36 | 5.7バイト | | 1/16 | 15x4=60 | 4.8バイト |
- こうしてみると、1/4がいいかなと思う。・・・1/16だとさすがに性能が落ちすぎな気がするし、その割に容量がものすごく節約されるというわけではない。かといって1/2はやはり容量を食いすぎる。1/4か1/8かで迷って、7.7バイトと5.7バイトの差をどう思うか。実際には最低でも4バイトのデータがあるだろうから、容量比としては最大でも20%くらい。2割小さくなることと引き換えに、1.5倍の遅さになるのはどうなのか。・・・ということで1/4がいいかなと思った。
比較
| 1要素あたりの追加容量 | 挿入 | 削除 | 検索 | i番目の要素を得る | 一つ先の要素を得る | 一つ前の要素を得る | この要素は何番目か | キーなしでも並べられるか | | 川合版 Indexable skiplist (KISL) | 7.7バイト | O(logN) | O(logN) | O(logN) | O(logN) | O(1) | O(logN) | O(logN) | yes | | 平衡二分木 | 8.0バイト以上 | O(logN) | O(logN) | O(logN) | O(logN) | O(logN) | O(logN) | O(logN) | たぶんyes | | B-tree | 8.0バイト以上 | O(logN) | O(logN) | O(logN) | O(logN) | ほぼO(1) | ほぼO(1) | O(logN) | たぶんyes | | 双方向リスト | 8.0バイト | O(1) | O(1) | O(N) | O(N) | O(1) | O(1) | O(N) | yes | | 片方向リスト | 4.0バイト | O(N) | O(N) | O(N) | O(N) | O(1) | O(N) | O(N) | yes | | ポインタ配列 | 4.0バイト | O(N) | O(N) | O(logN) | O(1) | O(1) or O(N) | O(1) or O(N) | O(1) or O(N) | yes |
- KISLでは、双方向リストを自由につなぎかえるように要素を並べ替えることができる。この使い方をする場合はデータの中にkeyがなくてもよく、先頭から100番目の位置にこの要素を挿入したい、とか、これこれの要素の隣に入れてほしいとか、そういう希望もすべてO(logN)で実現できる。またいろいろと要素を並べ替えた後で、この要素は現在何番目にいるのか？みたいな問い合わせにもO(logN)で答えられる。
- またKISLは乱数を使わないアルゴリズムなので、運が悪いと遅くなるとかそういうこともなく、ワーストケースでO(N)になるとかそういうこともない。
- ポインタ配列では、末尾への要素追加や末尾への要素削除に限定すれば、O(N)ではなくO(1)でできる。
- 「キーなしでも並べられるか」について、かつては平衡二分木などでは難しいのではないかと考えていたが、考え直して多分可能だと思うようになった。ということで、ここには優劣はない。
- 私としてはO(1)にはあまりこだわらない。O(logN)であれば事実上問題になることはほとんどないと思っている。あとは同じNを与えたとして、どれが一番速いかということになる。
混合戦略
- Nが小さいうちは、超シンプルなポインタ配列が結局は高速だと思います。ということで、ポインタ配列バージョンも作って、Nが大きくなったら自動で切り替えるようにしたいと思います。また要素の削除が続いて、Nが小さくなった時も切り替えるようにしたいと思います。
- それでNがどのくらいの値のときに切り替えるかは、実験をして決めようと思っています。
ほぼ完成した KCL_FastIndex
- [Q]これはどういうもの？
- [A]挿入や削除が高速なただの配列です。配列なので適当な順序で整列させることができます。要素内にポインタ1つ分のフィールドを追加すれば使えます。
- [Q]キーの比較ルールとかはどうやって与えるの？
- [A]このライブラリではキーを認識しませんので、自分で比較プログラムを書いてください。
- [Q]どうやって整列させるの？
- [A]配列全体の中から二分探索によって挿入箇所を自力で見つけてください。i番目の要素はidxToObj()で高速に得られます。
- [Q]どうやって挿入するの？
- [A]addで挿入位置を指定して追加します。
- [Q]どうやって削除するの？
- [A]removeで削除位置を指定して削除します。
- [Q]挿入や削除をすると、位置が変わってしまうと思うのだけど、今そのオブジェクトが何番目にあるかは調べられますか？
- [A]はいできます。objToIdxです。
- [Q]各要素は同型で同サイズである必要はありますか？
- [A]ありません。追加されたポインタフィールドしか見ていないので、それ以外の部分がどのようなフォーマットであってもOKです。
性能検証 (2017.05.22追記)
- テスト内容：
void testFastIndex(KCL_FastIndex *fi, Data *dat, int n)
{
int i, m0 = 0x800000 / n, m = m0;
double dt0 = clock();
while (m > 0) {
KCL_FastIndex_reset(fi);
// 後ろに要素を追加しながら長さnの配列を構築
for (i = 0; i < n; i++)
KCL_FastIndex_add(fi, &dat[i].p, -1); // 構造体内のポインタ格納用のメンバのアドレスを渡す.
// 0番目を末尾に移動, 1番目を後ろから2番目に移動, ...
for (i = 0; i < n; i++) {
Data *p = KCL_FastIndex_remove(fi, i);
KCL_FastIndex_add(fi, p, (n - 1) - i);
}
KCL_FastIndex_reset(fi);
// 先頭に要素を追加しながら長さnの配列を構築
for (i = 0; i < n; i++)
KCL_FastIndex_add(fi, &dat[i].islp, 0);
// 一番後ろを先頭に移動, 後ろから2番目を前から2番目に移動, ...
for (i = n - 1; i >= 0; i--) {
Data *p = KCL_FastIndex_remove(fi, i);
KCL_FastIndex_add(fi, p, (n - 1) - i);
}
m--;
}
printf("n=%d(x%d): time=%.3f[sec]\n", n, m0, (clock() - dt0) / (double) CLOCKS_PER_SEC);
return;
}
- 適当なマシンでの実測値です。バックグラウンドでいくつかプログラムが動いているので、まあそれほど厳密な値ではありませんが。
| n=16(x524288) | n=32(x262144) | n=64(x131072) | n=128(x65536) | n=256(x32768) | n=512(x16384) | n=1024(x8192) | n=2048(x4096) | | KISL | 1.314[sec] | 1.773[sec] | 2.068[sec] | 3.055[sec] | 3.490[sec] | 4.437[sec] | 4.286[sec] | 4.747[sec] | | ポインタ配列 | 0.804[sec] | 0.876[sec] | 1.324[sec] | 2.387[sec] | 4.433[sec] | 7.854[sec] | 15.435[sec] | 30.572[sec] | | 混合・自動切替 | 0.820[sec] | 1.053[sec] | 1.333[sec] | 3.456[sec] | 3.701[sec] | 4.429[sec] | 4.080[sec] | 4.772[sec] |
- n=256からはKISLのほうが高速になっています。ちなみにポインタ配列版も要素を追加していくとそれに応じて配列をreallocして拡張していく感じなので、その分のオーバーヘッドを含んでいます。
- KISL版では処理時間の伸びはかなり穏やかで、O(logN)を感じさせます。ポインタ配列版は、O(N)な感じです。
- これを踏まえて、n=0のときはポインタ配列型で、n=96になったらKISLに切り替えることにします。→混合・自動切り替え
- ちなみにn=48になったらポインタ配列に戻します。
- もっと大きな値で切り替えたほうがよさそうに思うかもしれませんが、実際のケースではO(N)操作が多くなるケースもあるかもしれないので、早めにKISLに切り替えるようにしました。
こめんと欄
|
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
