２次割り当て問題の解を評価する(2)
というわけで、評価関数をc++で書くことにした。適当に書いて100000回計算させて360ms。xyzzy上での344倍の速度である。ここまで差があると、xyzzy上で走らせるのはもったいない・・・。
しかし、探索アルゴリズムをlispで試したい。そこで、c++でdllを作って、解の評価を外部で行わせることにした。
まず、c++でdllを作る。
//qap.h // lispで出力(あとから読み込ませるのが面倒) // (format t "const int distance[~A][~@*~A] =~% {~{{~{~A~^,~}}~^,~%~}};" *size* *distance*) // (format t "const int flow[~A][~@*~A] =~% {~{{~{~A~^,~}}~^,~%~}};" *size* *flow*) // 変数は省略 //intの手前にあるのはdllを作るのに必要なおまじない extern "C" __declspec(dllexport) int eval (int *x); //qap.cpp #include "QAP.h" //こちらは普通に書く。初期化関数DLLmain()は勝手に作られる。 int eval (int *x) { int res = 0; for (int i=0;i<size;i++) for (int j=0;j<size;j++) res += distance[i][j] * flow[x[i]][x[j]]; return res; }
と用意して、makeか何かで
g++ -O3 -o qap.o -c qap.cpp g++ -mdll -o qap.dll qap.o
のように作る。
qap.dllをxyzzyから分かる位置に置いて、xyzzy側では次のように書く。配列の扱いが異なるので、ラッパが必要なのが玉に瑕。
(c:define-dll-entry c:int qap-eval-inner ((c:int *)) "qap.dll" "eval") (c:define-c-struct int-seq (c:int seq 30)) (defun qap-eval (x) (let* ((obj (make-int-seq))) (do ((i 0 (+ 4 i)) (lst x (cdr lst))) ((>= i 120) (qap-eval-inner obj)) ;(* 30 4)->120 (si:pack-int32 obj i (car lst)))))
速度は
(compile 'qap-eval) (time (dotimes (a 10000) (qap-eval x))) | 734 (time (dotimes (a 10000))) | 328 (/ (- 12390 328) (- 734 328) 1.0) | 29.70936
で、内部速度にして30倍。c++比では20倍遅いのだが、軽く試すならやっても良いレベルにはなったと思いたい。
