EssenMemo0004
の編集
https://khfdpl.osask.jp:443/wiki/?EssenMemo0004
[
トップ
] [
編集
|
差分
|
バックアップ
|
添付
|
リロード
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
-- 雛形とするページ --
2016_10
2016_11
2016_12
BracketName
Essen
Essen0
Essen1
Essen2
Essen3
Essen4
EssenMemo0001
EssenMemo0002
EssenMemo0003
EssenMemo0004
EssenMemo0005
EssenMemo0006
EssenMemo0007
EssenMemo0008
EssenMemo0009
EssenMemo0010
EssenMemo0011
EssenR2
EssenR2_ess03f
EssenR2_ess03h
EssenR2_ess03i
EssenR2_ideas
EssenR2_jit00
EssenR2_jit01
FormattingRules
FrontPage
Help
IP
InterWiki
InterWikiName
InterWikiSandBox
K
KHPC
KHPC_v000doc01
KHPC_v001doc01
KHPC_v002doc01
KHPC_v003doc01
MenuBar
OSC
OSC20181027
OSC20190222
OSC20191123
OSC20230401
OSC20230528
OSC20231021
OSC20240310
OSC20241026
PHP
PukiWiki
PukiWiki/1.4
PukiWiki/1.4/Manual
PukiWiki/1.4/Manual/Plugin
PukiWiki/1.4/Manual/Plugin/A-D
PukiWiki/1.4/Manual/Plugin/E-G
PukiWiki/1.4/Manual/Plugin/H-K
PukiWiki/1.4/Manual/Plugin/L-N
PukiWiki/1.4/Manual/Plugin/O-R
PukiWiki/1.4/Manual/Plugin/S-U
PukiWiki/1.4/Manual/Plugin/V-Z
RecentDeleted
SandBox
SltVA
VariableArray
WikiEngines
WikiName
YukiWiki
advcal20161205
advcal20161206
advcal20161209
advcal20161210
advcal20161215
eoml0001
eoml0002
essen_ex01_0001
impressions
kcl_malloc
khfdpl_result1
members
memo0001
memo0002
note0001
note0002
note0003
note0004
note0005
note0006
oldworks
oldworks00
oldworks06
oldworks12
oldworks13
osaskjp_index
persistent_C
populars
pr20161105
pr20161105b
scsc
seccamp2017
spam_test
uxf
uxf_01
uxf_02
uxp
* 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%83%E3%83%97%E3%83%AA%E3%82%B9%E3%83%88 -それで、ノードの高さは乱数では決め「ない」。リンクの幅が簡単に得られるのを利用して、不自然な長さになったら近くのノードのレベルを上げ下げして調節する。つまりリバランスする。 --もともとのスキップリストでは、リバランスがいらないことがアルゴリズムのシンプルさにつながっていて長所の一つだったが、Essen内のスキップリストではその長所は捨てて安定動作を目指したことになる。 -pをいくつにするか。1/2か1/4か1/8か1/16か。 --仮にN=65536のスキップリストがあったとする。リバランスによって、幅は理想値の1/2~2倍に調整されているとする。ポインタの幅はひとまず4バイトを仮定する。 |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/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 |RIGHT:1.314[sec]|RIGHT:1.773[sec]|RIGHT:2.068[sec]|RIGHT:3.055[sec]|RIGHT:3.490[sec]|RIGHT:4.437[sec]|RIGHT: 4.286[sec]|RIGHT: 4.747[sec]| |ポインタ配列 |RIGHT:0.804[sec]|RIGHT:0.876[sec]|RIGHT:1.324[sec]|RIGHT:2.387[sec]|RIGHT:4.433[sec]|RIGHT:7.854[sec]|RIGHT:15.435[sec]|RIGHT:30.572[sec]| |混合・自動切替|RIGHT:0.820[sec]|RIGHT:1.053[sec]|RIGHT:1.333[sec]|RIGHT:3.456[sec]|RIGHT:3.701[sec]|RIGHT:4.429[sec]|RIGHT: 4.080[sec]|RIGHT: 4.772[sec]| -n=256からはKISLのほうが高速になっています。ちなみにポインタ配列版も要素を追加していくとそれに応じて配列をreallocして拡張していく感じなので、その分のオーバーヘッドを含んでいます。 -KISL版では処理時間の伸びはかなり穏やかで、O(logN)を感じさせます。ポインタ配列版は、O(N)な感じです。 -これを踏まえて、n=0のときはポインタ配列型で、n=96になったらKISLに切り替えることにします。→混合・自動切り替え --ちなみにn=48になったらポインタ配列に戻します。 --もっと大きな値で切り替えたほうがよさそうに思うかもしれませんが、実際のケースではO(N)操作が多くなるケースもあるかもしれないので、早めにKISLに切り替えるようにしました。 * こめんと欄 #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%83%E3%83%97%E3%83%AA%E3%82%B9%E3%83%88 -それで、ノードの高さは乱数では決め「ない」。リンクの幅が簡単に得られるのを利用して、不自然な長さになったら近くのノードのレベルを上げ下げして調節する。つまりリバランスする。 --もともとのスキップリストでは、リバランスがいらないことがアルゴリズムのシンプルさにつながっていて長所の一つだったが、Essen内のスキップリストではその長所は捨てて安定動作を目指したことになる。 -pをいくつにするか。1/2か1/4か1/8か1/16か。 --仮にN=65536のスキップリストがあったとする。リバランスによって、幅は理想値の1/2~2倍に調整されているとする。ポインタの幅はひとまず4バイトを仮定する。 |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/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 |RIGHT:1.314[sec]|RIGHT:1.773[sec]|RIGHT:2.068[sec]|RIGHT:3.055[sec]|RIGHT:3.490[sec]|RIGHT:4.437[sec]|RIGHT: 4.286[sec]|RIGHT: 4.747[sec]| |ポインタ配列 |RIGHT:0.804[sec]|RIGHT:0.876[sec]|RIGHT:1.324[sec]|RIGHT:2.387[sec]|RIGHT:4.433[sec]|RIGHT:7.854[sec]|RIGHT:15.435[sec]|RIGHT:30.572[sec]| |混合・自動切替|RIGHT:0.820[sec]|RIGHT:1.053[sec]|RIGHT:1.333[sec]|RIGHT:3.456[sec]|RIGHT:3.701[sec]|RIGHT:4.429[sec]|RIGHT: 4.080[sec]|RIGHT: 4.772[sec]| -n=256からはKISLのほうが高速になっています。ちなみにポインタ配列版も要素を追加していくとそれに応じて配列をreallocして拡張していく感じなので、その分のオーバーヘッドを含んでいます。 -KISL版では処理時間の伸びはかなり穏やかで、O(logN)を感じさせます。ポインタ配列版は、O(N)な感じです。 -これを踏まえて、n=0のときはポインタ配列型で、n=96になったらKISLに切り替えることにします。→混合・自動切り替え --ちなみにn=48になったらポインタ配列に戻します。 --もっと大きな値で切り替えたほうがよさそうに思うかもしれませんが、実際のケースではO(N)操作が多くなるケースもあるかもしれないので、早めにKISLに切り替えるようにしました。 * こめんと欄 #comment
テキスト整形のルールを表示する