2014-10-31 62 views
0

我有關於快速排序此快速排序here .The序言代碼前面的問題:跟蹤路由 - 序言

gt(X,Y):- X @>Y. 
conc([],List, List). 
conc([Head|Tail], List1, [Head|List2]):- conc(Tail, List1, List2). 

quicksort([],[]). 
quicksort([X|Tail],Sorted):- 
    split(X,Tail,Small,Big), 
    quicksort(Small,SortedSmall), 
    quicksort(Big,SortedBig), 
    conc(SortedSmall,[X|SortedBig],Sorted). 

[1]split(X,[],[],[]). 
[2]split(X,[Y|Tail],[Y|Small],Big):- 
    gt(X,Y),!, 
    split(X,Tail,Small,Big). 
[3]split(X,[Y|Tail],Small,[Y|Big]):- 
    split(X,Tail,Small,Big). 

例如該陣列爲[3,2,4,1,5] 。這是跟蹤路由的第一部分:

?- trace, quicksort([3,2,4,1,5], Sorted). 
1 Call: (7) quicksort([3, 2, 4, 1, 5], _G4136) ? creep 
2 Call: (8) split(3, [2, 4, 1, 5], _G4269, _G4270) ? creep 
3 Call: (9) gt(3, 2) ? creep 
4 Call: (10) [email protected]>2 ? creep 
5 Exit: (10) [email protected]>2 ? creep 
6 Exit: (9) gt(3, 2) ? creep 
7 Call: (9) split(3, [4, 1, 5], _G4261, _G4273) ? creep 
8 Call: (10) gt(3, 4) ? creep 
9 Call: (11) [email protected]>4 ? creep 
10 Fail: (11) [email protected]>4 ? creep 
11 Fail: (10) gt(3, 4) ? creep 
12 Redo: (9) split(3, [4, 1, 5], _G4261, _G4273) ? creep 
13 Call: (10) split(3, [1, 5], _G4261, _G4264) ? creep 

在2號線,序言申請拆分的規則[2],我們有Call: (8) split(3, [2, 4, 1, 5], _G4269, _G4270),我們有_G4269[2|Small]_G4270Big

然後比較3和2,gt(3,2)返回true,它不執行切割。繼續使用split(X,Tail,Small,Big)Call: (9) split(3, [4, 1, 5], _G4261, _G4273)

如果gt(X,Y)返回false,prolog將執行剪切,然後應用分割的規則[3](第11-12行)。

我做對了,爲什麼最後一個變量變成了新變量(_G4237而不是_G4270)?因爲在代碼中我認爲它是一樣的。

任何人都可以幫我清楚一些事情嗎? 非常感謝!

+0

每個對predicat的調用都有自己的變量。你的蹤跡顯示深度爲(8)的'_G4270'和深度爲(9)的'_G4273'。所以他們是不同的。 – lurker 2014-10-31 16:59:38

+0

您可以信任變量名稱,特別是何時由算法生成! – CapelliC 2014-10-31 23:58:56

回答

0

準確地說:你的問題的關注跟蹤的這一部分:

2 Call: (8) split(3, [2, 4, 1, 5], _G4269, _G4270) ? creep 
3 Call: (9) gt(3, 2) ? creep 
4 Call: (10) [email protected]>2 ? creep 
5 Exit: (10) [email protected]>2 ? creep 
6 Exit: (9) gt(3, 2) ? creep 
7 Call: (9) split(3, [4, 1, 5], _G4261, _G4273) ? creep 

相當於調用:

split(X,[Y|Tail],[Y|Small],Big):- 
    gt(X,Y),!, 
    split(X,Tail,Small,Big). 

,你是正確的,沒有可見理由由於使用了相同的變量Big,所以可以獲得不同的變量。我承認這很混亂。而且,你可以獲得相同的變量。這可以被示出直接調用split(3, [2, 4, 1, 5], S, B)痕跡然後(用SWI v6.6.6):

[trace] ?- split(3, [2, 4, 1, 5], S, B). 
    Call: (6) split(3, [2, 4, 1, 5], _G4537, _G4538) ? creep 
    Call: (7) gt(3, 2) ? creep 
    Call: (8) [email protected]>2 ? creep 
    Exit: (8) [email protected]>2 ? creep 
    Exit: (7) gt(3, 2) ? creep 
    Call: (7) split(3, [4, 1, 5], _G4630, _G4538) ? creep 

而且相同的變量被使用(_G4538)。

然而,解釋可以有看不見原因統一的變量X與新Y一個品牌並在隨後的計算中使用Y代替X。這是你的例子中發生的事情。調試時可以使用命令g(目標)來獲得回溯,該回溯將顯示當前堆棧跟蹤和當前變量綁定。回到你的例子,當你達到

7 Call: (9) split(3, [4, 1, 5], _G4261, _G4273) ? 

g有一個回溯,你得到的東西,如:

[9] split(3, [4, 1, 5], _G4261, _G4273) 
    [8] split(3, [2, 4, 1, 5], [2|_G4261], _G4273) 
    [7] quicksort([3, 2, 4, 1, 5], _G4136) 
    Call: (9) split(3, [4, 1, 5], _G4261, _G4273) ? 

現在你可以看到,​​是在深度相同的變量[8]和[9]。