跟踪路由 - 序言

我有关于快速排序此快速排序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]和_G4270是Big。

然后比较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）？因为在代码中我认为它是一样的。

任何人都可以帮我清楚一些事情吗？非常感谢！

来源

2014-10-31 Thơ Hoàng

每个对predicat的调用都有自己的变量。你的踪迹显示深度为（8）的'_G4270'和深度为（9）的'_G4273'。所以他们是不同的。 – lurker 2014-10-31 16:59:38

您可以信任变量名称，特别是何时由算法生成！ – CapelliC 2014-10-31 23:58:56

准确地说：你的问题的关注跟踪的这一部分：

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]。

来源

2014-11-01 10:34:16 didou

跟踪路由 - 序言

回答

相关问题