2017.05.08)↑スキップリストいろいろ考えて、Essenの内部ではスキップリストを使いまくることにした。crit-bit-treeはいったん使わない方向で。ちなみにこれは内部構造的な話でしかないので、言語仕様には全く影響ないです(笑)。skiplist」を使う。https://ja.wikipedia.org/wiki/%E3%82%B9%E3%82%AD%E3%83%83%E3%83%97%E3%83%AA%E3%82%B9%E3%83%88それで、ノードの高さは乱数では決め「ない」。リンクの幅が簡単に得られるのを利用して、不自然な長さになったら近くのノードのレベルを上げ下げして調節する。スキップリストでは、リバランスがいらないことがアルゴリズムのシンプルさにつながっていて長所の一つだったが、Essen内のスキップリストではその長所は捨てて安定動作を目指したことになる。1/2か1/4か1/8か1/16か。仮にN=65536のスキップリストがあったとする。リバランスによって、幅は理想値の1/2~2倍に調整されているとする。ポインタの幅はひとまず4バイトを仮定する。4.8バイトこうしてみると、1/4がいいかなと思う。・・・1/16だとさすがに性能が落ちすぎな気がするし、その割に容量がものすごく節約されるというわけではない。いって1/2はやはり容量を食いすぎる。1/4か1/8かで迷って、7.7バイトと5.7バイトの差をどう思うか。実際には最低でも4バイトのデータがあるだろうから、容量比としては最大でも20%くらい。2割小さくなることと引き換えに、1.5倍の遅さになるのはどうなのか。・・・ということで1/4がいいかなと思った。yesKISLでは、双方向リストを自由につなぎかえるように要素を並べ替えることができる。この使い方をする場合はデータの中に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です。return;}適当なマシンでの実測値です。バックグラウンドでいくつかプログラムが動いているので、まあそれほど厳密な値ではありませんが。4.772[sec]n=256からはKISLのほうが高速になっています。ちなみにポインタ配列版も要素を追加していくとそれに応じて配列をreallocして拡張していく感じなので、その分のオーバーヘッドを含んでいます。KISL版では処理時間の伸びはかなり穏やかで、O(logN)を感じさせます。ポインタ配列版は、O(N)な感じです。これを踏まえて、n=0のときはポインタ配列型で、n=96になったらKISLに切り替えることにします。→混合・自動切り替えちなみにn=48になったらポインタ配列に戻します。大きな値で切り替えたほうがよさそうに思うかもしれませんが、実際のケースではO(N)操作が多くなるケースもあるかもしれないので、早めにKISLに切り替えるようにしました。