prog_0003
の編集
https://k.osask.jp/klog/?prog_0003
[
トップ
] [
編集
|
差分
|
バックアップ
|
添付
|
リロード
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
-- 雛形とするページ --
2012_0001
2013_0001
2013_0002
2013_0003
2014_0001
2015_0001
2016_07
2016_08
2016_09
2016_10
2016_11
2017_01
2017_02
2017_03
2017_04
2017_05
2018_01
2019_01
BracketName
FormattingRules
FrontPage
Help
InterWiki
InterWikiName
InterWikiSandBox
K
KH_SARC_00
KH_dha8
MenuBar
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
VC_install
WikiEngines
WikiName
WikiWikiWeb
YukiWiki
fdpl_memo0001
fdpl_memo0002
fdpl_memo0003
fdpl_memo0004
fdpl_memo0005
fdpl_memo0006
fdpl_memo0007
fdpl_memo0008
fdpl_memo0009
fdpl_memo0010
gg02_0004
gg02_0005
gg02_0006
gg02_0007
gg02_0008
gg02_0009
https
impressions
memo0001
memo0002
oisix01
osaskology
osaskology0
osecpu_0001
osecpu_0002
p20200229a
p20200303a
p20200310a
p20200321a
p20200401a
p20200730a
p20201230a
p20220628a
p20220701a
populars
prog_0001
prog_0002
prog_0003
prog_0004
prog_0005
* crit-bit tree -(by [[K]], 2014.10.14) ** (0) -今回は crit-bit tree の話。 ** (1) -crit-bit tree は、スキップリスト（参考：[[prog_0002]]）と同様に、基本操作(a)～(g)をO(logN)程度で実行できて、(h)もO(MlogN)くらいで実行できて、でも乱数は使わないし、アルゴリズムはより簡単。ただし代償として消費メモリはスキップリストよりも多い。 --省メモリ志向でも実装できそうだけど、それをやると少し速度が落ちそうな気がする。 --http://cr.yp.to/critbit.html --厳密にいうと演算量はlogNに比例するのではなく、演算量の上限がキーのビット長に比例する。 -crit-bit tree では、2つの要素を比較する際に、大小関係ではなく、どのビットで不一致になったのかを返す必要がある。また、キーのiビット目を取り出す関数も必要となる。 -実装したら速度重視でも280行くらいになった。スキップリストが350行くらいだったので、結構小さくなっている。 * こめんと欄 -p=1/4のスキップリストと crit-bit tree をベンチマークで比較してみたところ、 crit-bit tree のほうがメモリはたくさん使ってしまうけれど、速度は速かった。ただし、スキップリストのほうで「ずる」をして、乱数を使わずに理想的なlevelが設定できるようにしてやると（つまり正確に4個おきに上のレベルでつながっているようにすると）、スキップリストのほうが性能もよくなった。 -- ''K'' SIZE(10){2014-10-26 (日) 02:20:03} -ということで運がよければスキップリストのほうが高性能なんだけど、実用上は crit-bit tree のほうがいいのではないかと思う、メモリに余裕があるのなら。乱数を使わないアルゴリズムは、動作が安定するというメリットもある。 -- ''K'' SIZE(10){2014-10-26 (日) 02:22:23} #comment
タイムスタンプを変更しない
* crit-bit tree -(by [[K]], 2014.10.14) ** (0) -今回は crit-bit tree の話。 ** (1) -crit-bit tree は、スキップリスト（参考：[[prog_0002]]）と同様に、基本操作(a)～(g)をO(logN)程度で実行できて、(h)もO(MlogN)くらいで実行できて、でも乱数は使わないし、アルゴリズムはより簡単。ただし代償として消費メモリはスキップリストよりも多い。 --省メモリ志向でも実装できそうだけど、それをやると少し速度が落ちそうな気がする。 --http://cr.yp.to/critbit.html --厳密にいうと演算量はlogNに比例するのではなく、演算量の上限がキーのビット長に比例する。 -crit-bit tree では、2つの要素を比較する際に、大小関係ではなく、どのビットで不一致になったのかを返す必要がある。また、キーのiビット目を取り出す関数も必要となる。 -実装したら速度重視でも280行くらいになった。スキップリストが350行くらいだったので、結構小さくなっている。 * こめんと欄 -p=1/4のスキップリストと crit-bit tree をベンチマークで比較してみたところ、 crit-bit tree のほうがメモリはたくさん使ってしまうけれど、速度は速かった。ただし、スキップリストのほうで「ずる」をして、乱数を使わずに理想的なlevelが設定できるようにしてやると（つまり正確に4個おきに上のレベルでつながっているようにすると）、スキップリストのほうが性能もよくなった。 -- ''K'' SIZE(10){2014-10-26 (日) 02:20:03} -ということで運がよければスキップリストのほうが高性能なんだけど、実用上は crit-bit tree のほうがいいのではないかと思う、メモリに余裕があるのなら。乱数を使わないアルゴリズムは、動作が安定するというメリットもある。 -- ''K'' SIZE(10){2014-10-26 (日) 02:22:23} #comment
テキスト整形のルールを表示する
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
