關於性能 （一）

我個人知識淺薄，喜歡一些大裁大減的方法，我以一個「找相同和的子集」的問題為例。

有幸寫過一些prolog，而prolog恰好是支持constraint programming最舒適的語言之一。學prolog的學習曲線因人而異，一些人習慣邏輯流程的，學起來會非常快，而已經適應過程式編程的人，學習曲線可能會陡峭一點。

言歸正傳，constraint programming簡單一點來講就是規範一個solution的邊界，讓程序在這個solution空間里查找相應的結果。所以constraint programming可以從邏輯上提升性能。

比如我們希望從一個集合里尋找和都為0的子集，我們可以先定義一個predicate，這個predicate一部分中文翻譯為判定式，其實我不喜歡這個模糊的翻譯，因為predicate實際上是一個返出邏輯值的布爾函數。

所以整個問題可以被定義一個predicate：

subsetSum(L,R) :- map(L,R1,Map),domain(R1,0,1), resultingLst(L,R1,R).

這裡的Map我會在之後定義，和常見的Map函數作用相同，我希望這個predicate能map到整個子集，domain就是定義的尋找空間，這裡我做一個簡化就先定了一個小的空間，通過判斷符號而非具體值來提升性能, 只有0,-1,1 ，L指的是原集合，R1指的是子集合，而resultingLst（L，R1， R），可以視作resultingLst，predicate作用在L和R1上，如果正確，有R收集結果，如果錯誤，則R不收集結果。

resultingLst(L,R1,R) :- selfSum(L,R1,Sum),Sum #=0,labeling([ffc],R1), remove0(L,R1,G), R #= G,notEmpty(R).

這裡selfSum馬上介紹，Sum ＃＝0是需要被label的結果，labeling（［ffc］，R1）指的是從左到右，最先滿足contraint的先被label，這樣可以避免很多計算很多不滿足條件的子集，從而提升效率。remove0這個條件命名得不好，其實應該命名為extract0，旨在收集子集里的0，如果所有的元素都是0，正好，收集起來，如果不是，拿出0，然後再收集自己里的-1,1。所以這裡的selfSum就再一次成為提升性能的機會。

selfSum([],[],0).selfSum([A|CDRL],[B|CDRR],N):- N#=N1+A*B,selfSum(CDRL,CDRR,N1).

A＊B會告訴我結果是0，1還是-1,而且還可以直接判斷符號，｜表示去掉第一個元素，保留子集。這樣就可以在邏輯上形成一個遞歸。最後我其實只需要判斷一次符號就能確認結果是否滿足條件，從而提升了性能。

接下來就是很順理成章的一些helper predicate：

remove0([],[],[]).remove0([A|L],[B|S],K) :- B #= 1, remove0(L,S,K1), append([A],K1,K).remove0([A|L],[B|S],K) :- B #= 0, remove0(L,S,K).notEmpty(L) :- + is_empty(L),!.is_empty([]).is_empty(L) :- L == [].map(X,Y,Map):-var(Map),!, map_build(X,Y,Map).map(X,Y,Map):- map_get(X,Y,Map).map_build([],[],[]).map_build([A|As],[B|Bs],[(A,B)|Map]):- map_build(As,Bs,Map).map_get([],[],_):-!.map_get([A|As],[B|Bs],Map):-!, map_get(A,B,Map), map_get(As,Bs,Map).map_get(A,B,Map):- member((A,B),Map),!.

整個程序就結束了，雖然用C／C++也寫不了多少行，但是卻很難達到從邏輯上直接提升性能的效果，也很難像prolog一樣直觀地反映邏輯。所以這是prolog的強大之處。

以24個元素的子集為例，這樣需要找的子集一共個，大概是個需要查找的結果，我的程序能在平均1s內完成一個NP-Complete的問題。

推薦閱讀：