SLIM時間計測
Last-modified: 2010-04-26 (月) 17:06:09 (5126d)
Top / SLIM時間計測
- 主にCHRとLMNtalの実行時間比較をまとめるためのページ
最短経路問題 †
- 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)より若干低いくらいになるはず
| 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 †
- CHRでも測定してみる予定
フィボナッチ数(fib_bottomup) †
- 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) †
- 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) †
- 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 †
find loop †
Union Find †
- どうやって測ろう...
babble sort †
- lmn(slim):-O3 --use-findatom2でコンパイル、-p3で測定
- n要素持つリストを生成、要素は乱数
n 512 1024 2048 4096 lmn 0.116 0.423 1.640 6.560
quick sort †
- lmn(slim):-O3 --use-findatom2でコンパイル、-p3で測定
n 512 1024 2048 4096 lmn 0.223 1.013 5.266 33.673
merge sort †
- lmn(slim):-O3 --use-findatom2でコンパイル、-p3で測定
n 512 1024 2048 4096 lmn 5.060 32.373
Spanning Spider †
- クエリを見直したほうがいい
- lmn(slim):-O3 --use-findatom2でコンパイル、-p3で測定
nxn 2x2 3x3 4x4 lmn 0.01 114.24