実行スピードとメモリ消費のバランス。

Goldberg 氏の 2-level Bucket はとても早いのだが、
全米で 3GByte ほど消費してしまうので、カーナビに使用するには難しいだろう。

[実験環境]
CPU Xeon 2.33GHz / Mem 16GB

[実行結果]
BinTree　　　　/ 46.4[s] / 1.0 GB
1-level Bucket / 29.2[s] / 1.1 GB
2-level Bucket / 25.0[s] / 3.0 GB

現在、現実的なものとしては 1-Level Bucket になっている。
先読みも考慮した新たなデータ構造を考えている。

ダイクストラ法での走査の流れをもう少し詳しくおっていこうと思う。

ソースの整理１。

プログラム全体を見直し、少しは使い易くなった。
これからは高速かつ、メモリを食わないデータ構造を探していきたいと思う。


Xeon 3.0GHz / Mem 8GByte

c USA.p2p
c point-to-point shotest path
c for USA
p aux sp p2p 10
q 957498 10453327
q 19200797 7727679
q 13006257 40639
q 4314559 22779984
q 17261435 8424294
q 8077810 13186938
q 3048748 1475829
q 21869636 3531883
q 13446936 4981527
q 18549540 3230879



$ time ./sp_tree USA-road-d.USA.gr USA.p2p
shortest path route start at Thu Nov 29 17:12:47 2007
algorithm is dijkstra method
data structure is binary tree
input file is USA-road-d.USA.gr & USA.p2p
query num is 10
query type is point-to-point
graph type is dimacs graph
node / arc is 23947347 / 58333344
[ 1/10] 957498-10453327
Distance = 39503661, ScanNode = 20253158, CalcTime : 5566.2[ms]

[ 2/10] 19200797-7727679
Distance = 6652463, ScanNode = 4020891, CalcTime : 1192.8[ms]

[ 3/10] 13006257-40639
Distance = 15806743, ScanNode = 12775136, CalcTime : 4480.3[ms]

[ 4/10] 4314559-22779984
Distance = 31900664, ScanNode = 11812148, CalcTime : 3254.5[ms]

[ 5/10] 17261435-8424294
Distance = 2928315, ScanNode = 779311, CalcTime : 288.0[ms]

[ 6/10] 8077810-13186938
Distance = 33411726, ScanNode = 19326314, CalcTime : 5464.2[ms]

[ 7/10] 3048748-1475829
Distance = 13958246, ScanNode = 6669378, CalcTime : 1860.7[ms]

[ 8/10] 21869636-3531883
Distance = 18762398, ScanNode = 4643327, CalcTime : 1208.8[ms]

[ 9/10] 13446936-4981527
Distance = 36604539, ScanNode = 17550812, CalcTime : 5007.2[ms]

[10/10] 18549540-3230879
Distance = 20809134, ScanNode = 16722303, CalcTime : 5612.1[ms]

File Read Time : 48953.6[ms]
Total Calc Time : 33934.8[ms]

real 1m24.134s
user 1m22.888s
sys 0m1.246s

gprof でプロファイル２。

static リンクするとどうなるかとコメントを頂いたので、さっそく。
ライブラリを静的にリンクすることになるので、
数十 Kbyte のバイナリが 600 KByte ほどに。

静的にリンクしたことで、fscanf 等の関数までプロファイルすることができるようである。(?)_IO_vfscanf_internal は fscanf() のことを指していると思われるが、
fscanf() でグラフデータを格納しているので、３３％弱というのは納得がいく。 

%   cumulative   self              self     total time   seconds   seconds    calls   s/call   s/call  name 
35.02     22.72    22.72       10     2.27     4.03  DijkstraWithBinTreeP2P
21.95     36.97    14.25                             _IO_vfscanf_internal
20.71     50.41    13.44 128723320     0.00     0.00  BinTreeInsert 
 8.34     55.82     5.41                             ____strtol_l_internal
 4.68     58.85     3.04 120640933     0.00     0.00  BinTreeGetMinNode
 1.57     59.87     1.02  8029936     0.00     0.00  BinTreeDeleteNode
 1.13     60.60     0.73                             cfree
 1.07     61.30     0.70                             _IO_sputbackc
 1.06     61.99     0.69                             _int_free
 0.91     62.58     0.59                             __read_nocancel
 0.87     63.14     0.57                             malloc
 0.82     63.67     0.53                             _int_malloc
 0.51     64.00     0.33        1     0.33     0.33  ReadSortedGr
 0.23     64.15     0.15                             __getclktck
 0.22     64.30     0.15                             fscanf
 0.18     64.41     0.12                             __profile_frequency
 0.15     64.51     0.10                             _IO_default_seekoff
 0.11     64.58     0.07                             __secure_getenv
 0.11     64.65     0.07                             __strtol_internal
 0.06     64.69     0.04                             munmap
 0.06     64.73     0.04                             realloc_check  
 0.06     64.77     0.04                             strtoul
 0.05     64.80     0.04       10     0.00     0.00  BinTreeFree
 0.05     64.83     0.03                             mallopt
 0.04     64.86     0.03                             printf
 0.02     64.87     0.01                             _IO_file_underflow
 0.02     64.88     0.01                             __uflow
 0.01     64.88     0.01                             calloc
 0.01     64.89     0.01                             dprintf
 0.00     64.89     0.00       22     0.00     0.00  GetRusageSec
 0.00     64.89     0.00       10     0.00     0.00  BinTreeFree2
 0.00     64.89     0.00       10     0.00     0.00  BinTreeInit
 0.00     64.89     0.00        1     0.00     0.00  GraphFree
 0.00     64.89     0.00        1     0.00     0.00  GraphMalloc
 0.00     64.89     0.00        1     0.00     0.00  QueryFree 
 0.00     64.89     0.00        1     0.00     0.00  QueryMalloc
 0.00     64.89     0.00        1     0.00     0.00  ReadDimacsQueryP2P
 0.00     64.89     0.00        1     0.00    40.58  main

gprof でプロファイル。

前回、地道に呼出回数を数えていくという方法をとったが、
今回は gprof でお手軽にプロファイルしてみた。

gprof を利用するためには、このようにすれば良い。

% gcc -O -g -pg sample.c
% ./a.out
% gprof a.out




結果を見ると、思ったよりも挿入作業がボトルネックになっていることがわかる。
ただ、ReadSortedGr の実行時間が 0.34 秒というのはおかしい
（ファイルからのデータ読み込みは２４秒ほどかかっているはず）ので、
gprof について、もう少し調べてみる必要がありそうだ。
Intel の VTune などの高性能なプロファイラーを用いる方がいいのかもしれない。

  %   cumulative   self  self  total time  seconds   seconds     calls   s/call   s/call  name
55.65      21.47   21.47        10     2.15     3.83 DijkstraWithBinTreeP2P
32.81      34.13   12.66 128723320     0.00     0.00  BinTreeInsert
 7.93      37.19    3.06 120640933     0.00     0.00  BinTreeGetMinNode  
 2.79      38.26    1.08   8029936     0.00     0.00  BinTreeDeleteNode  
 0.88      38.60    0.34         1     0.34     0.34  ReadSortedGr  
 0.08      38.63    0.03        10     0.00     0.00  BinTreeFree
 0.00      38.63    0.00        22     0.00     0.00  GetRusageSec  
 0.00      38.63    0.00        10     0.00     0.00  BinTreeFree2  
 0.00      38.63    0.00        10     0.00     0.00  BinTreeInit
 0.00      38.63    0.00         1     0.00     0.00  GraphFree
 0.00      38.63    0.00         1     0.00     0.00  GraphMalloc 
 0.00      38.63    0.00         1     0.00     0.00  QueryFree  
 0.00      38.63    0.00         1     0.00     0.00  QueryMalloc
 0.00      38.63    0.00         1     0.00     0.00  ReadDimacsQueryP2P

最短路に用いるデータ構造２。

単純な（前処理なしで、A* などを用いない）Dijkstra 法は
Andrew V. Goldberg 氏による multi-level buckets を用いたものが早いらしいのだが、
現在までずっと Binary Tree を用いてきたので簡単に乗り換えるのではなく、
一種の悪あがき的に新しいデータ構造に乗り換える前にプロファイルしてみた。
具体的には関数の呼出回数やループをカウントする。
これにより無駄・非効率と思われるコードを最適化できた。

基本的に以下の５つさえあれば十分であるが、
特に[→]で表した３つの関数は全体の実行時間に大きな影響を及ぼす。
　・初期化する　　　　　　　　　　　　　void BinTreeInit (void)
→・新たにデータを挿入する　　　　　　　void BinTreeInsert (int a_pot, int a_num)
→・キーが最小であるデータを取り出す　　int BinTreeGetMinNode (void)
→・データを削除する　　　　　　　　　　void BinTreeDeleteNode (int a_pot, int a_num)
　・２分木内のデータを開放する　　　　　void BinTreeFree (void)

関数呼出のオーバーヘッドも馬鹿にならないので、
「データを開放する」関数以外では再帰呼び出しは用いていない。



shortest path route start at Mon Nov 26 12:40:04 2007
algorithm is dijkstra method
data is ../ShortestPath/data/USA/USA-road-t.USA.grap
query is data/p2p/USA.p2p
mode is p2p & Sorted Graph
node number is 23947347
arc number is 58333344



------profile------
BinTreeInsert() = 21719633
InsertSearch = 357653143

BinTreeGetMinNode() = 20358763
GetMinSearch = 179981007
GetMinSwap = 20358763

BinTreeDeleteNode() = 1357591
DeleteSearch = 20710051
DeleteSearch2 = 231822
DeleteSwap = 1357591

BinTreeFree() = 6559
[ 1/10] 957498-10453327
Distance = 41922812, ScanNode = 20358763, CalcTime : 7411.9[ms]



------profile------
BinTreeInsert() = 4657459
InsertSearch = 75768261

BinTreeGetMinNode() = 4429158
GetMinSearch = 38404289
GetMinSwap = 4429158

BinTreeDeleteNode() = 223056
DeleteSearch = 3338129
DeleteSearch2 = 38833
DeleteSwap = 223056

BinTreeFree() = 10491
[ 2/10] 19200797-7727679
Distance = 8047405, ScanNode = 4429158, CalcTime : 1685.7[ms]



------profile------
BinTreeInsert() = 14375086
InsertSearch = 256352154

BinTreeGetMinNode() = 13443219
GetMinSearch = 129103637
GetMinSwap = 13443219

BinTreeDeleteNode() = 924297
DeleteSearch = 15408115
DeleteSearch2 = 141669
DeleteSwap = 924297

BinTreeFree() = 15141
[ 3/10] 13006257-40639
Distance = 18835334, ScanNode = 13443219, CalcTime : 6392.0[ms]



------profile------
BinTreeInsert() = 14232379
InsertSearch = 229433023

BinTreeGetMinNode() = 13290596
GetMinSearch = 115644903
GetMinSwap = 13290596

BinTreeDeleteNode() = 937115
DeleteSearch = 14076707
DeleteSearch2 = 153597
DeleteSwap = 937115

BinTreeFree() = 9337
[ 4/10] 4314559-22779984
Distance = 36904098, ScanNode = 13290596, CalcTime : 4804.3[ms]



------profile------
BinTreeInsert() = 1038438
InsertSearch = 15196655

BinTreeGetMinNode() = 971469
GetMinSearch = 7223363
GetMinSwap = 971469

BinTreeDeleteNode() = 64025
DeleteSearch = 863560
DeleteSearch2 = 11560
DeleteSwap = 64025

BinTreeFree() = 5889
[ 5/10] 17261435-8424294
Distance = 4202750, ScanNode = 971469, CalcTime : 379.9[ms]



------profile------
BinTreeInsert() = 20339739
InsertSearch = 332226258

BinTreeGetMinNode() = 19042418
GetMinSearch = 166082821
GetMinSwap = 19042418

BinTreeDeleteNode() = 1293387
DeleteSearch = 19604645
DeleteSearch2 = 217896
DeleteSwap = 1293387

BinTreeFree() = 7869
[ 6/10] 8077810-13186938
Distance = 35317539, ScanNode = 19042418, CalcTime : 7049.9[ms]



------profile------
BinTreeInsert() = 8759589
InsertSearch = 142715504

BinTreeGetMinNode() = 8263299
GetMinSearch = 72398087
GetMinSwap = 8263299

BinTreeDeleteNode() = 487996
DeleteSearch = 7312158
DeleteSearch2 = 84456
DeleteSwap = 487996

BinTreeFree() = 16589
[ 7/10] 3048748-1475829
Distance = 16883055, ScanNode = 8263299, CalcTime : 3101.5[ms]



------profile------
BinTreeInsert() = 4809684
InsertSearch = 73649036

BinTreeGetMinNode() = 4511822
GetMinSearch = 38538004
GetMinSwap = 4511822

BinTreeDeleteNode() = 294455
DeleteSearch = 4244206
DeleteSearch2 = 42489
DeleteSwap = 294455

BinTreeFree() = 6815
[ 8/10] 21869636-3531883
Distance = 21836097, ScanNode = 4511822, CalcTime : 1433.8[ms]



------profile------
BinTreeInsert() = 21575235
InsertSearch = 359693596

BinTreeGetMinNode() = 20211716
GetMinSearch = 181259979
GetMinSwap = 20211716

BinTreeDeleteNode() = 1357637
DeleteSearch = 21097667
DeleteSearch2 = 217532
DeleteSwap = 1357637

BinTreeFree() = 11765
[ 9/10] 13446936-4981527
Distance = 42431566, ScanNode = 20211716, CalcTime : 7936.8[ms]



------profile------
BinTreeInsert() = 17216078
InsertSearch = 299413743

BinTreeGetMinNode() = 16118473
GetMinSearch = 151036991
GetMinSwap = 16118473

BinTreeDeleteNode() = 1090377
DeleteSearch = 17693984
DeleteSearch2 = 168372
DeleteSwap = 1090377

BinTreeFree() = 14457
[10/10] 18549540-3230879
Distance = 22838781, ScanNode = 16118473, CalcTime : 7235.9[ms]

File Read Time : 23784.4[ms]
Total Calc Time : 47431.8[ms]

最短路に用いるデータ構造。

ダイクストラ法はとても効率的に最短路を求めることができるアルゴリズムであるが、
走査した際に求めたポテンシャルをどのように格納するかでかなり差が出ることが分かった。


■現時点では「BinaryTree」か「BinaryHeap」で格納している。
○BinaryTree
　こちらは BinaryTree へ値を挿入・削除するたびに、malloc/free している。
　BinaryTree にデータがある場合とない場合で場合分けをしている。
　　ある→それを削除し、更新したものを改めて挿入する
　　ない→挿入する

○BinaryHeap
　一度に配列で確保しているので、この部分に関しては「BinaryTree」よりは効率である。
　頂いたプログラムをそのまま加えただけなので、場合分けはしていない。



■用いたデータ
Distance graph :
DIMACS Full USA (23947347 nodes and 58333344 arcs)

Query :
10
957498 10453327
19200797 7727679
13006257 40639
4314559 22779984
17261435 8424294
8077810 13186938
3048748 1475829
21869636 3531883
13446936 4981527
18549540 3230879


○Pentium M 1.60GHz / 896MB
　FileReadTime　　　　　　　　　８１秒
　Dijkstra With BinaryTree　　１０６秒
　Dijkstra With BinaryHeap　　１３２秒


○Xeon 3.0GHz x 2 / 8GB
　FileReadTime　　　　　　　　　２３秒
　Dijkstra With BinaryTree　　　４５秒
　Dijkstra With BinaryHeap　　　５７秒


このように現時点では「BinaryTree」の方が高速なのだが、
場合分けを採用すれば「BinaryHeap」にもまだまだ分があるだろう。

ポインタは遅いと言われてきたがここまで差があるのであれば、
やはり「Fibonacci Heap」が有効なのかもしれない。
とりあえず授業（Ｒやらプレゼン）が一段落したので、作ってみよう。

R はひとまず終了。

結果はともかく終わったので、もとの生活に戻ります。
しかし今週プレゼンが２回。
それぞれ１人１回ずつなのに、なぜこの週に集中したんだろうか。

しかも違うテーマで、片方は１時間やってほしいと。。
たくさんスライドを持っている最短路と、スライドづくりが比較的に面倒だった分枝限定法（こっちが１時間）。
どちらも作り終えたので、あとは発表のみ。

正直、毎回授業で PowerPoint 使っている方はすごいと思います。

R って。

いろいろ動かしてみるほどに、１週間くらいの時間では把握しきれないだろうことを痛感させられた。
もともと統計の知識が乏しいことも災いしているだろう。

とりあえず明日が課題の提出期限ではあるが、
出来るかどうかすらも分からないものが、とりあえず出来たといったところである。
このまま提出するのはあまりにも申し訳ないが、これ以上厳しいというのも事実である。

研究がおもしろくなってきたところであって、そちらに気持ちがいってしまっているといっても、
授業は授業でしっかりやらなくてはと思っていたのだが。

はじめてのR。

授業の課題で初めてＲを使うことになったので、とりあえず RGui をインストールしてみました。
ちなみにＲはデータ解析用言語Ｓから開発されたクローンだそうです。

インストールが簡単だった（[次へ]を押すだけ）ので、とにかくいろいろ使ってみました。
ほんの数行を入力するだけで、きれいなグラフなどをプロットできます。
とりあえずいろいろ遊んでみて使い方を覚えたいと思います。

最短路。

以前作成した Dijsktra 法で最短路を解くプログラムを見返してみた。
その当時、できるだけのことはしたつもりだったが、今更になってよくない部分がたくさん見つかった。
以前はそういった部分を発見する力がなかったのだろうか。

結局、気になってほぼすべてのソースを見直すことになってしまったが、
その甲斐もあり、54.5 秒程かかっていた実行時間を 45.5 秒 程に落とすことが出来た。

まだブロッキング等の最適化手法を用いていないので、まだまだ高速化できそうだ。


[xxxxx@xxxx src]$ ./shortestpath p2p s ../../../data/USA/USA-road-t.USA.grap ../../../data/USA/query_USA.p2p
shortest path route start at Mon Nov 5 17:27:31 2007
algorithm is dijkstra method
mode is p2p & sorted dimacs graph
data (.gr) is ../../../data/USA/USA-road-t.USA.grap
query (.ss) is ../../../data/USA/query_USA.p2p
node number is 23947347
arc number is 58333344

[ 1/10] 957498-10453327
Distance = 41922812, ScanNode = 20358763, CalcTime : 7155.9[ms]

[ 2/10] 19200797-7727679
Distance = 8047405, ScanNode = 4429158, CalcTime : 1629.8[ms]

[ 3/10] 13006257-40639
Distance = 18835334, ScanNode = 13443219, CalcTime : 6105.1[ms]

[ 4/10] 4314559-22779984
Distance = 36904098, ScanNode = 13290596, CalcTime : 4628.3[ms]

[ 5/10] 17261435-8424294
Distance = 4202750, ScanNode = 971469, CalcTime : 371.9[ms]

[ 6/10] 8077810-13186938
Distance = 35317539, ScanNode = 19042418, CalcTime : 6776.0[ms]

[ 7/10] 3048748-1475829
Distance = 16883055, ScanNode = 8263299, CalcTime : 2973.5[ms]

[ 8/10] 21869636-3531883
Distance = 21836097, ScanNode = 4511822, CalcTime : 1393.8[ms]

[ 9/10] 13446936-4981527
Distance = 42431566, ScanNode = 20211716, CalcTime : 7601.8[ms]

[10/10] 18549540-3230879
Distance = 22838781, ScanNode = 16118473, CalcTime : 6877.0[ms]

File Read Time : 23819.4[ms]
Total Calc Time : 45513.1[ms]

分枝限定法。

ある授業で「分枝限定法」について発表することになったので、
ナップサック問題を解くソルバーを作ってみた。
それにしても、なんてアバウトなテーマなのかと思ってしまう。

全列挙法や、ラグランジュ緩和を用いた分枝限定法、
また更に釘つけテストを適応したものと３つ作ってみた。

１．全列挙法
　　とりあえず、すべての解を列挙。最適値を保存しておく。
　　
２．ラグランジュ緩和による分枝限定法
　　線形緩和問題を解き、その値と現在までの上界値を欲張り法により算出。
　　効率の良い順に探索しておけば何もしないときに比べ、
　　早い段階で最適解が求まる可能性が高いので途中で止められる。

３．枝付けテストを用いた分枝限定法
　　変数の多い問題を解く際に、実際には意味のない変数を前処理を行って見分け、取り除く。
　　各変数を固定して（釘付けして）分枝限定法を行う。


実行時間は　１＞２＞３　となり、まあうまくいっていると言えるだろう。


ただ小さな問題であると、動的確保したメモリを用いると処理が遅くなってしまう。
全列挙法などでは、たかだか３０程のアイテムでも待つことになるので、
静的にとってしまった方がよいだろう。