關於性能 (一)

知乎上技術好的人很多,我恰好不是那一類,他們關於性能的一些回答,非常好。我這一篇就是個小補丁,寫得不好,才疏學淺。

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

有幸寫過一些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個元素的子集為例,這樣需要找的子集一共2^{24}-1個,大概是1.6*10^{7}個需要查找的結果,我的程序能在平均1s內完成一個NP-Complete的問題。

推薦閱讀:

從 Apache RocketMQ 和 Kafka 看 Topic 數量對單機性能的影響
【瓦罐態度】<WagonAttitue>性能之餘的姿態?Green RS4
阿里雲資料庫掌門人褚霸:騎行與數據人生
為您的 Node 性能選擇最佳的 JS 引擎

TAG:Prolog | 性能 | 約束求解 |