快速排序算法的跟踪路径 - prolog [英] trace route of the quicksort algorithm - prolog

问题描述

我之前有一个关于这个快速排序的问题 这里.快速排序的序言代码:

I have that previous question about this quicksort here.The prolog code for quicksort:

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].这是跟踪路由的第一部分:

The array for example is [3,2,4,1,5]. This is the first part of the trace route:

?- 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) 3@>2 ? creep
5  Exit: (10) 3@>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) 3@>4 ? creep
10 Fail: (11) 3@>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 行，prolog 应用了 split 的规则 [2]，我们有 Call: (8) split(3, [2, 4, 1, 5], _G4269, _G4270)我们有 _G4269 是 [2|Small] 而 _G4270 是 Big.

At the line 2, prolog apply the rule [2] of split and we have Call: (8) split(3, [2, 4, 1, 5], _G4269, _G4270) and we have _G4269 is [2|Small] and _G4270 is Big.

然后比较 3 和 2，gt(3,2) 返回 true 并且不执行剪切.继续split(X,Tail,Small,Big)，即Call: (9) split(3, [4, 1, 5], _G4261, _G4273)

It then compare 3 and 2, gt(3,2) return true and it does not execute the cut. Continue with split(X,Tail,Small,Big) which is Call: (9) split(3, [4, 1, 5], _G4261, _G4273)

如果 gt(X,Y) 返回 false，prolog 将执行切割，然后应用拆分的规则 [3](第 11-12 行).

If the gt(X,Y) return false, prolog will execute the cut and then apply the rule [3] of the split (line 11-12).

我做得对吗?为什么最后一个变量变成了一个新变量(_G4237 而不是 _G4270)?因为在代码中我认为是一样的.

Am I doing right and why the last variable has become a new one (_G4237 instead of _G4270)? Because in the code I thought it is the same.

谁能帮我清理一下?非常感谢！

Anyone could help me clear things out? Many thanks!

推荐答案

准确地说:您的问题涉及跟踪的这一部分:

To be precise: your question concerns this part of the trace:

2  Call: (8) split(3, [2, 4, 1, 5], _G4269, _G4270) ? creep
3  Call: (9) gt(3, 2) ? creep
4  Call: (10) 3@>2 ? creep
5  Exit: (10) 3@>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，所以没有 VISIBLE 理由来获取不同的变量.我承认这很令人困惑.而且，您可以获得相同的变量.这可以显示为直接调用 split(3, [2, 4, 1, 5], S, B) 然后跟踪是(使用 swi v6.6.6):

and you are right there is no VISIBLE reason to obtain different variables since the same variable Big is used. I admit it is confusing. And, you could obtain the same variable. This can be shown calling directly split(3, [2, 4, 1, 5], S, B) the trace is then (with 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) 3@>2 ? creep
   Exit: (8) 3@>2 ? creep
   Exit: (7) gt(3, 2) ? creep
   Call: (7) split(3, [4, 1, 5], _G4630, _G4538) ? creep

并且使用了相同的变量(_G4538).

And the same variable is used (_G4538).

然而，解释器可以有 INVISIBLE 的理由将一个变量 X 与一个全新的 Y 统一起来并使用 Y 而不是 X 在后续计算中.这就是您的示例中发生的情况.您可以在调试时使用命令 g (goals) 来获取回溯，这将显示具有当前变量绑定的当前堆栈跟踪.回到你的例子，当你到达

However, the interpreter can have INVISIBLE reason to unify a variable X with a brand new one Y and use Yinstead of X in subsequent computations. It is what occurs in your example. You can use the command g (goals) when debugging to obtain a backtrace, which will show the current stack trace with current variable bindings. Returning to your example, when you reach

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

键入 g 以进行回溯，您将获得如下内容:

type g to have a backtrace and you obtain something like:

  [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) ? 

现在您可以看到 _G4273 在深度 [8] 和 [9] 上是相同的变量.

And now you can see that _G4273 is the same variable in depth [8] and [9].

这篇关于快速排序算法的跟踪路径 - prolog的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！