quicksort - APL中快速排序的解释

Question

我试图了解 APL 中的经典快速排序:

Q←{1≥≢⍵:⍵ ⋄ S←{⍺⌿⍨⍺ ⍺⍺ ⍵} ⋄ ⍵((∇<S)⍪=S⍪(∇>S))⍵⌷⍨?≢⍵}

有些东西我不明白，有些风格选择让我很困扰，所以我将把它们全部列出来。我希望有人可以向我解释。

我知道在 { } 里面定义，⍺是左参数，⍵是正确的论点。什么是⍺⍺在 S←{⍺⌿⍨⍺ ⍺⍺ ⍵} ?同样，是否有 ⍵⍵ ? ⍺里面S引用 S 的左参数或 Q 的左参数?

我的猜测是 ⍺里面 S指 S 的左参数. ⍺⍺指 ⍺的封闭函数(即 Q 的 ⍺)。

为什么大量使用通勤(⍨)？代码是不是更清楚地写成:

Q←{1≥≢⍵:⍵ ⋄ S←{(⍺ ⍺⍺ ⍵)⌿⍺} ⋄ ⍵((∇<S)⍪=S⍪(∇>S))⍵[?≢⍵]}

我能想到的使用 commute 的唯一用途是减少括号的使用 ()和 [] ，但这似乎不值得失去易读性。我在这里错过了一些“APL方式”吗？

这实际上并没有执行快速排序，是吗？快速排序被定义为就地。但是，我对 APL 语义的理解是，这段代码实际上在递归子调用上构建了新数组，并使用 ⍪ 将它们连接起来。 .确实，这是 same criticism that is levelled at Haskell's quicksort .我在 APL 语义中是否遗漏了一些东西来告知此操作是“就地”完成的？请注意，我对“足够聪明的编译器”参数不感兴趣，因为数组分析从根本上具有挑战性。如果 APL 编译器真的把它变成了一个就地算法，我会非常重视它如何执行这个分析的细节——这是一个相当大的成就!

为什么使用≢⍵找到尺寸大小？为什么不 ⍴⍵ ?一般来说，我发现人们使用 ≢超过 ⍴查询沿最外层维度的大小，即使函数工作的唯一情况是一维。同样，我认为 APL 方式中我缺少某些东西。

非常感谢。

Answer 1

1. I understand that inside a { } defn, ⍺ is the left argument, and ⍵ is the right argument. What is ⍺⍺ in S←{⍺⌿⍨⍺ ⍺⍺ ⍵}? Similarly, is there an ⍵⍵?

S←{⍺⌿⍨⍺ ⍺⍺ ⍵}称为dop。类似于 dfn 是用户定义的函数，dop 是用户定义的运算符，其行为类似于 ¨ , ⍨ , 或 ∘ .

其语义总结:

如果一个 dop 只提到 ⍺⍺ (不是 ⍵⍵ )，它成为一元运算符，您可以将其用作 x (m S) y .

如果一个 dop 提到 ⍵⍵ ，它变成一个二元运算符，您可以将其用作 x (m S n) y .

在这两种情况下，⍺⍺ (其值为 m )和 ⍵⍵ (将具有 n )可以是数组或函数。

您也可以决定不使用 ⍺在 dop 的正文中，在这种情况下，您可以将其称为 (m S) y或 (m S n) y ，省略左参数。

m被称为左操作数，n是正确的操作数。这些与左参数( x )和右参数( y )不同。

在您的示例中， S仅提及 ⍺⍺ ，所以称为 x (m S) y .如果您调用 S喜欢 1 2 3 >S 2 ，它将评估为 1 2 3⌿⍨1 2 3 > 2 ，这将是一个 3。

Does the ⍺ inside the S refer to the left argument of S or the left argument of Q?

S的正文内部, 一切由 ⍺和 ⍵字符是指 S 的参数/操作数. Q 的原始论点是不可见的(除非它们首先被分配给一个变量，在这种情况下它们作为变量名可见)。

2. Why the copious use of commute (⍨)?

我相信这主要是一种风格选择。我也更喜欢编写带括号的代码而不是在生产代码中使用它，除非该用法很容易被识别为 APL 习惯用法。我确实写了例如 3÷⍨whatever而不是 (whatever)÷3用于除以常数。

3. This is not actually performing quicksort, is it?

你是对的。正如您已经提到的，Quicksort 旨在就地运行以真正成为 Quick (TM)。 APL 可以做内存预分配和数组共享，以减少一些内存复制和分配，但是在创建三个子数组(元素小于/等于/大于枢轴)时，至少有一些副本是不可避免的，并且后来串联起来。

需要注意的一点是，与 Haskell 不同，APL 确实有就地分配，看起来像 x[i]←v .如果要在 APL 中正确实现 Quicksort，则必须像在 C 中那样编写代码(将索引传递给递归调用等)。

4. Why the use of ≢⍵ to find the dimension size? Why not ⍴⍵?

≢在 ⍴ 时被称为“计数”称为“形”。 ≢总是返回一个标量值，而 ⍴返回一个向量(如果给定向量参数，它将是一个长度为一的向量)。虽然标量和长度为一的向量在大多数情况下表现相同，但它们是不同的东西，例如 1≡,1是假的。

我相信区分两者是一个好习惯，尽可能使用标量而不是长度为一的向量。一个值得注意的异常(exception)是当您需要一个显式封闭的数组(不能封闭标量)时。