APL中快速排序的解释

Question

我试图理解 APL 中的经典快速排序：

\n\n

Q\xe2\x86\x90{1\xe2\x89\xa5\xe2\x89\xa2\xe2\x8d\xb5:\xe2\x8d\xb5 \xe2\x8b\x84 S\xe2\x86\x90{\xe2\x8d\xba\xe2\x8c\xbf\xe2\x8d\xa8\xe2\x8d\xba \xe2\x8d\xba\xe2\x8d\xba \xe2\x8d\xb5} \xe2\x8b\x84 \xe2\x8d\xb5((\xe2\x88\x87<S)\xe2\x8d\xaa=S\xe2\x8d\xaa(\xe2\x88\x87>S))\xe2\x8d\xb5\xe2\x8c\xb7\xe2\x8d\xa8?\xe2\x89\xa2\xe2\x8d\xb5}\n

\n\n

有些事情我不明白，有些风格选择困扰我，所以我要把它们全部列出来。我希望有人可以向我解释它们。

\n\n

\n
1. 我知道在{ }defn 中，\xe2\x8d\xba是左参数，\xe2\x8d\xb5是右参数。\xe2\x8d\xba\xe2\x8d\xba里面是什么 S\xe2\x86\x90{\xe2\x8d\xba\xe2\x8c\xbf\xe2\x8d\xa8\xe2\x8d\xba \xe2\x8d\xba\xe2\x8d\xba \xe2\x8d\xb5}？同样，有一个\xe2\x8d\xb5\xe2\x8d\xb5? \xe2\x8d\xba里面的是S指 的左参数S还是 的左参数Q？
\n

\n\n

我的猜测是，\xe2\x8d\xba里面的S指的是 的左边参数S。the\xe2\x8d\xba\xe2\x8d\xba指的是封闭函数\xe2\x8d\xba的 的（即Q 的 ）。\xe2\x8d\xba

\n\n

\n
2. 为什么要大量使用通勤（\xe2\x8d\xa8）？代码写成这样是不是更清晰了：
\n

\n\n

Q\xe2\x86\x90{1\xe2\x89\xa5\xe2\x89\xa2\xe2\x8d\xb5:\xe2\x8d\xb5 \xe2\x8b\x84 S\xe2\x86\x90{(\xe2\x8d\xba \xe2\x8d\xba\xe2\x8d\xba \xe2\x8d\xb5)\xe2\x8c\xbf\xe2\x8d\xba} \xe2\x8b\x84 \xe2\x8d\xb5((\xe2\x88\x87<S)\xe2\x8d\xaa=S\xe2\x8d\xaa(\xe2\x88\x87>S))\xe2\x8d\xb5[?\xe2\x89\xa2\xe2\x8d\xb5]}\n

\n\n

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

\n\n

\n

3. 这实际上并不是在执行快速排序，是吗？快速排序被定义为就地排序。然而，我对 APL 语义的理解是，这段代码实际上在递归子调用上构建新数组，并使用\xe2\x8d\xaa. 事实上，这与 Haskell 的快速排序所受到的批评是一样的。APL 语义中是否缺少某些内容来通知此操作是“就地”完成的？请注意，我对“足够智能的编译器”参数不感兴趣，因为数组分析从根本上来说是具有挑战性的。如果 APL 编译器确实将其转换为就地算法，我将非常重视它如何执行此分析的详细信息 --- 这是一项相当大的成就！

\n

4. 为什么要使用 来\xe2\x89\xa2\xe2\x8d\xb5查找尺寸大小？为什么不\xe2\x8d\xb4\xe2\x8d\xb5？一般来说，我发现人们使用\xe2\x89\xa2over\xe2\x8d\xb4来查询沿最外层维度的大小，即使函数工作的唯一情况是 1D。再次，我认为 APL 方式中有一些我遗漏的东西。

\n

\n\n

多谢。

\n

Answer 1

\n

\n
1. 我知道在{ }defn 中，\xe2\x8d\xba是左参数，\xe2\x8d\xb5是右参数。\xe2\x8d\xba\xe2\x8d\xba里面是什么S\xe2\x86\x90{\xe2\x8d\xba\xe2\x8c\xbf\xe2\x8d\xa8\xe2\x8d\xba \xe2\x8d\xba\xe2\x8d\xba \xe2\x8d\xb5}？同样，是否有一个\xe2\x8d\xb5\xe2\x8d\xb5?
\n

\n

\n\n

S\xe2\x86\x90{\xe2\x8d\xba\xe2\x8c\xbf\xe2\x8d\xa8\xe2\x8d\xba \xe2\x8d\xba\xe2\x8d\xba \xe2\x8d\xb5}称为dop。与dfn是用户定义函数类似， dop是用户定义运算符，其行为类似于\xc2\xa8、\xe2\x8d\xa8或\xe2\x88\x98。

\n\n

其语义总结：

\n\n

\n
• 如果 dop 仅提及\xe2\x8d\xba\xe2\x8d\xba(not \xe2\x8d\xb5\xe2\x8d\xb5)，它就会成为一元运算符，您可以将其用作x (m S) y。
\n
• 如果 dop 提到\xe2\x8d\xb5\xe2\x8d\xb5，它就变成二元运算符，您可以将其用作x (m S n) y。
\n
• 在这两种情况下，\xe2\x8d\xba\xe2\x8d\xba( 其值为m) 和\xe2\x8d\xb5\xe2\x8d\xb5( 其值为n) 可以是数组或函数。
\n
• 您还可以决定不在\xe2\x8d\xbadop 的主体中使用，在这种情况下，您可以将其称为(m S) yor (m S n) y，省略左侧参数。
\n
• m称为左操作数，n称为右操作数。这些与左参数( x) 和右参数( )不同y。
\n

\n\n

在您的示例中，S仅提及\xe2\x8d\xba\xe2\x8d\xba，因此它被称为 as x (m S) y。如果你调用Slike 1 2 3 >S 2，它将计算为1 2 3\xe2\x8c\xbf\xe2\x8d\xa81 2 3 > 2，这将是一个 3。

\n\n

\n

\xe2\x8d\xba里面的是S指 的左参数S还是 的左参数Q？

\n

\n\n

在 的体内，所有由和字符S组成的内容都指的是 的参数/操作数。的原始参数是不可见的（除非它们首先分配给变量，在这种情况下它们作为变量名可见）。\xe2\x8d\xba\xe2\x8d\xb5SQ

\n\n

\n

\n
2. 为什么要大量使用通勤（\xe2\x8d\xa8）？
\n

\n

\n\n

我相信这主要是一种风格选择。我还更喜欢编写带括号的代码，而不是在生产代码中使用它，除非该用法很容易被识别为 APL 习惯用法。我确实写了eg3\xc3\xb7\xe2\x8d\xa8whatever而不是(whatever)\xc3\xb73除以常量。

\n\n

\n

\n
3. 这实际上并不是在执行快速排序，是吗？
\n

\n

\n\n

你是对的。正如您已经提到的，快速排序被设计为就地运行以真正成为快速排序（TM）。APL可以进行内存预分配和数组共享，以减少一些内存复制和分配，但至少在创建三个子数组（元素小于/等于/大于主元）时不可避免地会产生一些副本后来串联起来。

\n\n

需要注意的一件事是，与 Haskell 不同，APL 确实有就地赋值，看起来像x[i]\xe2\x86\x90v. 如果要在 APL 中正确实现快速排序，就必须像在 C 中编码一样进行编码（将索引传递给递归调用等）。

\n\n

\n

\n
4. 为什么要使用 来\xe2\x89\xa2\xe2\x8d\xb5查找尺寸大小？为什么不\xe2\x8d\xb4\xe2\x8d\xb5？
\n

\n

\n\n

\xe2\x89\xa2称为“理”，\xe2\x8d\xb4称为“形”。\xe2\x89\xa2始终返回标量值，而\xe2\x8d\xb4返回向量（如果给定向量参数，则它将是长度为 1 的向量）。虽然标量和长度为一的向量在大多数情况下表现相同，但它们是不同的东西，例如1\xe2\x89\xa1,1为假。

\n\n

我相信区分两者是一个好习惯，只要有可能，就倾向于使用标量而不是长度为一的向量。一个值得注意的例外是当您需要一个显式封闭的数组（不能封闭标量）时。

\n