EssenMemo0004
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
* Essenの開発メモ#0004
-(by [[K]], 2017.05.08)
** スキップリスト
-いろいろ考えて、Essenの内部ではスキップリストを使いまく...
--つまりcrit-bit-treeはいったん使わない方向で。
--ちなみにこれは内部構造的な話でしかないので、言語仕様に...
-基本構造としてはWikipediaの「Indexable skiplist」を使う。
--https://ja.wikipedia.org/wiki/%E3%82%B9%E3%82%AD%E3%83%...
-それで、ノードの高さは乱数では決め「ない」。リンクの幅が...
--もともとのスキップリストでは、リバランスがいらないこと...
-pをいくつにするか。1/2か1/4か1/8か1/16か。
--仮にN=65536のスキップリストがあったとする。リバランスに...
|p|検索時に幅をたどる回数(平均)|1ノードあたりの追加容量(...
|1/2|RIGHT:1x16=16|RIGHT:14バイト|
|1/4|RIGHT:3x8=24|RIGHT:7.7バイト|
|1/8|RIGHT:1+7x5=36|RIGHT:5.7バイト|
|1/16|RIGHT:15x4=60|RIGHT:4.8バイト|
--こうしてみると、1/4がいいかなと思う。・・・1/16だとさす...
** 比較
| |1要素あたりの追加容量|挿入 |削除 ...
|川合版 Indexable skiplist (KISL)|7.7バイト|O(logN)|O(log...
|平衡二分木 |8.0バイト以上|O(logN)|O(log...
|B-tree |8.0バイト以上|O(logN)|O(log...
|双方向リスト |8.0バイト |O(1) |O(1) ...
|片方向リスト |4.0バイト |O(N) |O(N) ...
|ポインタ配列 |4.0バイト |O(N) |O(N) ...
-KISLでは、双方向リストを自由につなぎかえるように要素を並...
-またKISLは乱数を使わないアルゴリズムなので、運が悪いと遅...
-ポインタ配列では、末尾への要素追加や末尾への要素削除に限...
-「キーなしでも並べられるか」について、かつては平衡二分木...
-私としてはO(1)にはあまりこだわらない。O(logN)であれば事...
** 混合戦略
-Nが小さいうちは、超シンプルなポインタ配列が結局は高速だ...
-それでNがどのくらいの値のときに切り替えるかは、実験をし...
** ほぼ完成した KCL_FastIndex
-[Q]これはどういうもの？
-[A]挿入や削除が高速なただの配列です。配列なので適当な順...
-[Q]キーの比較ルールとかはどうやって与えるの？
-[A]このライブラリではキーを認識しませんので、自分で比較...
-[Q]どうやって整列させるの？
-[A]配列全体の中から二分探索によって挿入箇所を自力で見つ...
-[Q]どうやって挿入するの？
-[A]addで挿入位置を指定して追加します。
-[Q]どうやって削除するの？
-[A]removeで削除位置を指定して削除します。
-[Q]挿入や削除をすると、位置が変わってしまうと思うのだけ...
-[A]はいできます。objToIdxです。
-[Q]各要素は同型で同サイズである必要はありますか？
-[A]ありません。追加されたポインタフィールドしか見ていな...
** 性能検証 (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(...
return;
}
-適当なマシンでの実測値です。バックグラウンドでいくつかプ...
| |n=16(x524288) |n=32(x262144) |n=64(x1...
|KISL |RIGHT:1.314[sec]|RIGHT:1.773[sec]|RIGHT:2...
|ポインタ配列 |RIGHT:0.804[sec]|RIGHT:0.876[sec]|RIGHT:1...
|混合・自動切替|RIGHT:0.820[sec]|RIGHT:1.053[sec]|RIGHT:1...
-n=256からはKISLのほうが高速になっています。ちなみにポイ...
-KISL版では処理時間の伸びはかなり穏やかで、O(logN)を感じ...
-これを踏まえて、n=0のときはポインタ配列型で、n=96になっ...
--ちなみにn=48になったらポインタ配列に戻します。
--もっと大きな値で切り替えたほうがよさそうに思うかもしれ...
* こめんと欄
#comment
終了行:
* Essenの開発メモ#0004
-(by [[K]], 2017.05.08)
** スキップリスト
-いろいろ考えて、Essenの内部ではスキップリストを使いまく...
--つまりcrit-bit-treeはいったん使わない方向で。
--ちなみにこれは内部構造的な話でしかないので、言語仕様に...
-基本構造としてはWikipediaの「Indexable skiplist」を使う。
--https://ja.wikipedia.org/wiki/%E3%82%B9%E3%82%AD%E3%83%...
-それで、ノードの高さは乱数では決め「ない」。リンクの幅が...
--もともとのスキップリストでは、リバランスがいらないこと...
-pをいくつにするか。1/2か1/4か1/8か1/16か。
--仮にN=65536のスキップリストがあったとする。リバランスに...
|p|検索時に幅をたどる回数(平均)|1ノードあたりの追加容量(...
|1/2|RIGHT:1x16=16|RIGHT:14バイト|
|1/4|RIGHT:3x8=24|RIGHT:7.7バイト|
|1/8|RIGHT:1+7x5=36|RIGHT:5.7バイト|
|1/16|RIGHT:15x4=60|RIGHT:4.8バイト|
--こうしてみると、1/4がいいかなと思う。・・・1/16だとさす...
** 比較
| |1要素あたりの追加容量|挿入 |削除 ...
|川合版 Indexable skiplist (KISL)|7.7バイト|O(logN)|O(log...
|平衡二分木 |8.0バイト以上|O(logN)|O(log...
|B-tree |8.0バイト以上|O(logN)|O(log...
|双方向リスト |8.0バイト |O(1) |O(1) ...
|片方向リスト |4.0バイト |O(N) |O(N) ...
|ポインタ配列 |4.0バイト |O(N) |O(N) ...
-KISLでは、双方向リストを自由につなぎかえるように要素を並...
-またKISLは乱数を使わないアルゴリズムなので、運が悪いと遅...
-ポインタ配列では、末尾への要素追加や末尾への要素削除に限...
-「キーなしでも並べられるか」について、かつては平衡二分木...
-私としてはO(1)にはあまりこだわらない。O(logN)であれば事...
** 混合戦略
-Nが小さいうちは、超シンプルなポインタ配列が結局は高速だ...
-それでNがどのくらいの値のときに切り替えるかは、実験をし...
** ほぼ完成した KCL_FastIndex
-[Q]これはどういうもの？
-[A]挿入や削除が高速なただの配列です。配列なので適当な順...
-[Q]キーの比較ルールとかはどうやって与えるの？
-[A]このライブラリではキーを認識しませんので、自分で比較...
-[Q]どうやって整列させるの？
-[A]配列全体の中から二分探索によって挿入箇所を自力で見つ...
-[Q]どうやって挿入するの？
-[A]addで挿入位置を指定して追加します。
-[Q]どうやって削除するの？
-[A]removeで削除位置を指定して削除します。
-[Q]挿入や削除をすると、位置が変わってしまうと思うのだけ...
-[A]はいできます。objToIdxです。
-[Q]各要素は同型で同サイズである必要はありますか？
-[A]ありません。追加されたポインタフィールドしか見ていな...
** 性能検証 (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(...
return;
}
-適当なマシンでの実測値です。バックグラウンドでいくつかプ...
| |n=16(x524288) |n=32(x262144) |n=64(x1...
|KISL |RIGHT:1.314[sec]|RIGHT:1.773[sec]|RIGHT:2...
|ポインタ配列 |RIGHT:0.804[sec]|RIGHT:0.876[sec]|RIGHT:1...
|混合・自動切替|RIGHT:0.820[sec]|RIGHT:1.053[sec]|RIGHT:1...
-n=256からはKISLのほうが高速になっています。ちなみにポイ...
-KISL版では処理時間の伸びはかなり穏やかで、O(logN)を感じ...
-これを踏まえて、n=0のときはポインタ配列型で、n=96になっ...
--ちなみにn=48になったらポインタ配列に戻します。
--もっと大きな値で切り替えたほうがよさそうに思うかもしれ...
* こめんと欄
#comment
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
