SeijiWiki
SLIM時間計測
の編集
Top
/ SLIM時間計測
-- 雛形とするページ --
???±??¢Ã???Ñ??¢±
Adsense Arbitrage Contest Beating Major Adsense Arbitragers Along at the Game
BracketName
Farming Recommendations And Traveler's Bag For Incredible Gold
FormattingRules
FrontPage
Help
hyperlink仕様まとめ
InterWiki
InterWikiName
InterWikiSandBox
LINK
MenuBar
PaperWriting
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
QuickTimeInstaller
RecentDeleted
SandBox
SLIM callback関連 メモ
SLIM時間計測
TopPage
uniq
vista - ubuntu8.04(on VMware)間での共有フォルダ設定
Vistaで自動シャットダウン
WikiEngines
WikiName
WikiWikiWeb
YukiWiki
ノート
ラウンジ
研究日誌とうめき
研究日誌とうめき_
研究日誌とつぶやき
研究日誌とぼやき
実験TA シフト表
卒論
卒論タイトル
卒論概要
読み物
-主にCHRとLMNtalの実行時間比較をまとめるためのページ #contents * 最短経路問題 [#p77394d2] -chr_sssp : 先週の全対用のプログラムを少し変えてノード1からの最短経路のみを求める --たったの2ルール --O(N^7)のプログラムを、N個のノードからではなくノード1からの探索のみにしたのでO(N^6) |node|10|20|30|40|50| |time|0.02|1.15|14.47|83.96|330.00| |t/(n/10)^6|0.023|0.018|0.019|0.020|0.021| -chr_dijkstra_Fheap : ダイクストラ法+優先度付きキュー(フィボナッチヒープで表現) --O(M+NlogN)で最も速いとされている方法、Mはエッジ数 --CHRで書いたらO(N*I+M*D+N*E)、IやらDはルール適用回数 --dijkstra+Fheapモジュールで26ルールくらいある --今回のクエリ(有向完全グラフ)ではO(N^4)より若干低いくらいになるはず &br; |node|10|20|30|40|50|60| |time|0.01|0.05|0.17|0.45|1.03|1.95| |t/(n/10)^4|0.01|0.00312|0.00213|0.00175|0.00164|0.00150| *other examples [#kaa8fae2] -CHRでも測定してみる予定 **フィボナッチ数(fib_bottomup) [#l95ca64a] -nまでのフィボナッチ数を求める -chr(swi):cputime関数で測定 -lmn(slim):-O3 --use-findatom2でコンパイル、-p3で測定 |n|512|1024|2048|4096| |chr|1.333|5.313|21.196|85.183| |lmn|6.94|54.06|421.58|| **最短経路問題(dijkstra_Fheap) [#l95ca64a] -1点から他点への最短経路(single source shortest path) -dijkstra法+fib_heapを利用して記述 -chr(swi):cputime関数で測定 -lmn(slim):-O3 --use-findatom2でコンパイル、-p3で測定 |node|512|1024|2048|4096| |edge|2048|4096|8192|16384| |chr|0.72|2.51|10.47|over| |lmn|2.34|8.89|35.55|143.12| **辞書式順序(lexicographic) [#l95ca64a] -2つのリストの比較 -chr(swi):cputime関数で測定 -lmn(slim):-O3 --use-findatom2でコンパイル、-p3で測定 |n(要素数)|10|10|10|10| |m(list数)|512|1024|2048|4096| |chr||0.466|0.993|1.960| |lmn||0.143|0.420|1.503| **CHR_leq [#uce4f55b] **find loop [#f222768f] **Union Find [#e12748ab] -どうやって測ろう... **babble sort [#e12748ab] -lmn(slim):-O3 --use-findatom2でコンパイル、-p3で測定 -n要素持つリストを生成、要素は乱数 |n|512|1024|2048|4096| |lmn|0.116|0.423|1.640|6.560| **quick sort [#e12748ab] -lmn(slim):-O3 --use-findatom2でコンパイル、-p3で測定 |n|512|1024|2048|4096| |lmn|0.223|1.013|5.266|33.673| **merge sort [#e12748ab] -lmn(slim):-O3 --use-findatom2でコンパイル、-p3で測定 |n|512|1024|2048|4096| |lmn|5.060|32.373||| **Spanning Spider [#e12748ab] -クエリを見直したほうがいい -lmn(slim):-O3 --use-findatom2でコンパイル、-p3で測定 |nxn|2x2|3x3|4x4| |lmn|0.01|114.24||
タイムスタンプを変更しない
-主にCHRとLMNtalの実行時間比較をまとめるためのページ #contents * 最短経路問題 [#p77394d2] -chr_sssp : 先週の全対用のプログラムを少し変えてノード1からの最短経路のみを求める --たったの2ルール --O(N^7)のプログラムを、N個のノードからではなくノード1からの探索のみにしたのでO(N^6) |node|10|20|30|40|50| |time|0.02|1.15|14.47|83.96|330.00| |t/(n/10)^6|0.023|0.018|0.019|0.020|0.021| -chr_dijkstra_Fheap : ダイクストラ法+優先度付きキュー(フィボナッチヒープで表現) --O(M+NlogN)で最も速いとされている方法、Mはエッジ数 --CHRで書いたらO(N*I+M*D+N*E)、IやらDはルール適用回数 --dijkstra+Fheapモジュールで26ルールくらいある --今回のクエリ(有向完全グラフ)ではO(N^4)より若干低いくらいになるはず &br; |node|10|20|30|40|50|60| |time|0.01|0.05|0.17|0.45|1.03|1.95| |t/(n/10)^4|0.01|0.00312|0.00213|0.00175|0.00164|0.00150| *other examples [#kaa8fae2] -CHRでも測定してみる予定 **フィボナッチ数(fib_bottomup) [#l95ca64a] -nまでのフィボナッチ数を求める -chr(swi):cputime関数で測定 -lmn(slim):-O3 --use-findatom2でコンパイル、-p3で測定 |n|512|1024|2048|4096| |chr|1.333|5.313|21.196|85.183| |lmn|6.94|54.06|421.58|| **最短経路問題(dijkstra_Fheap) [#l95ca64a] -1点から他点への最短経路(single source shortest path) -dijkstra法+fib_heapを利用して記述 -chr(swi):cputime関数で測定 -lmn(slim):-O3 --use-findatom2でコンパイル、-p3で測定 |node|512|1024|2048|4096| |edge|2048|4096|8192|16384| |chr|0.72|2.51|10.47|over| |lmn|2.34|8.89|35.55|143.12| **辞書式順序(lexicographic) [#l95ca64a] -2つのリストの比較 -chr(swi):cputime関数で測定 -lmn(slim):-O3 --use-findatom2でコンパイル、-p3で測定 |n(要素数)|10|10|10|10| |m(list数)|512|1024|2048|4096| |chr||0.466|0.993|1.960| |lmn||0.143|0.420|1.503| **CHR_leq [#uce4f55b] **find loop [#f222768f] **Union Find [#e12748ab] -どうやって測ろう... **babble sort [#e12748ab] -lmn(slim):-O3 --use-findatom2でコンパイル、-p3で測定 -n要素持つリストを生成、要素は乱数 |n|512|1024|2048|4096| |lmn|0.116|0.423|1.640|6.560| **quick sort [#e12748ab] -lmn(slim):-O3 --use-findatom2でコンパイル、-p3で測定 |n|512|1024|2048|4096| |lmn|0.223|1.013|5.266|33.673| **merge sort [#e12748ab] -lmn(slim):-O3 --use-findatom2でコンパイル、-p3で測定 |n|512|1024|2048|4096| |lmn|5.060|32.373||| **Spanning Spider [#e12748ab] -クエリを見直したほうがいい -lmn(slim):-O3 --use-findatom2でコンパイル、-p3で測定 |nxn|2x2|3x3|4x4| |lmn|0.01|114.24||
テキスト整形のルールを表示する