SLIM時間計測 の変更点
Top / SLIM時間計測
- 追加された行はこの色です。
- 削除された行はこの色です。
- SLIM時間計測 へ行く。
- SLIM時間計測 の差分を削除
-主に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||