algorithm - APL 中 X 指示的累积最大值

Question

FinnAPL Library 中的第三项称为“由 X 指示的 Y 的子向量的累积最大值 (⌈)”，其中 X 是二进制向量，Y 是数字向量。下面是它的用法示例:

X←1 0 0 0 1 0 0 0
Y←9 78 3 2 50 7 69 22
Y[A⍳⌈\A←⍋A[⍋(+\X)[A←⍋Y]]]       ⍝ output 9 78 78 78 50 50 69 69

您可以看到，从 X 数组中的开头或任意 1 值开始，为 Y 中的所有对应数字找到累积最大值，直到在 X 中找到另一个 1。在给出的示例中，X 将数组分为两个相等的部分，每个部分 4 个数字。在第一部分中，9 是最大值，直到遇到 78，在第二部分中，50 是最大值，直到遇到 69。

这很容易理解，我可以照原样盲目使用它，但我想了解它是如何工作的，因为 APL 习语本质上是由运算符和函数组成的算法。要很好地理解 APL，重要的是要了解大师们如何将它们编织成如此紧凑而优雅的代码行。

我发现这个特殊的习语特别难以理解，因为索引嵌套了两层。所以我的问题是，是什么让这个成语成为现实？

Answer 1

这个习语可以分解成更小的习语，最重要的是，它包含来自 FinnAPL 图书馆的习语 #11，标题为:

Grade up (⍋) 用于对 X 指示的 Y 的子向量进行排序

对问题中给出的 X 和 Y 使用相同的值，这是其用法示例:

X←1 0 0 0 1 0 0 0
Y←9 78 3 2 50 7 69 22
A[⍋(+\X)[A←⍋Y]]             ⍝ output 4 3 1 2 6 8 5 7

和以前一样，X 将向量分成两半，输出表明，对于每个位置，需要 Y 的哪个数字来对每一半进行排序。因此，输出中的 4 表示它需要第一个位置的 Y (2) 的第 4 个数字； 3 表示第 2 个位置的第 3 个数字 (3)； 1 表示第 3 个位置的第 1 个数字 (9)；等等。因此，如果我们将此索引应用于 Y，我们将得到:

Y[A[⍋(+\X)[A←⍋Y]]]          ⍝ output 2 3 9 78 7 22 50 69

为了理解这个升级习语中的索引，请考虑以下情况:

(+\X)[A←⍋Y]                 ⍝ Sorted Cumulative Addition

逐步分解:

A←⍋Y                        ⍝ 4 3 6 1 8 5 7 2
+\X                         ⍝ 1 1 1 1 2 2 2 2
(+\X)[A←⍋Y]                 ⍝ 1 1 2 1 2 2 2 1 SCA
A[⍋(+\X)[A←⍋Y]]             ⍝ 4 3 1 2 6 8 5 7

您可以看到应用于 A 的 X 1 1 2 1 2 2 2 1 的排序累积加法 (SCA) 充当压缩左和压缩右的组合. A 中与 1 对齐的所有值都向左移动，与 2 对齐的所有值向右移动。当然，如果 X 有更多的 1，它将按照 SCA 结果的值指示的顺序压缩和定位压缩包。例如，如果 X 的 SCA 类似于 3 3 2 1 2 2 1 1 1，您最终会得到对应于 1 的 4 位数字，然后是3位对应2，最后2位对应3。

你可能已经注意到我跳过了显示升级效果的步骤⍋:

(+\X)[A←⍋Y]                 ⍝ 1 1 2 1 2 2 2 1 SCA
⍋(+\X)[A←⍋Y]                ⍝ 1 2 4 8 3 5 6 7 Grade up
A[⍋(+\X)[A←⍋Y]]             ⍝ 4 3 1 2 6 8 5 7

SCA 无法单独实现压缩和重排的效果。正如我在另一个 post 中讨论的那样，它有效地充当了等级。 .同样在那篇文章中，我谈到了等级和索引本质上是同一枚硬币的两个面，您可以使用等级提升在两者之间切换。因此，这就是这里发生的事情:SCA 正在转换为一个索引以应用于 A，并且效果是升级排序的子向量，如 X 所示。

从排序子向量到累积最大值

如前所述，对子向量排序的结果是一个索引，当应用于 Y 时，将数据压缩成数据包并根据 X 排列这些数据包。关键是它是一个索引，再次是等级up 被应用，它将索引转换为排名:

⍋A[⍋(+\X)[A←⍋Y]]            ⍝ 3 4 2 1 7 5 8 6

这里的问题是，为什么？好吧，下一步是应用累积最大值，只有将其应用于表示每个数据包内相对大小的等级值时，这才真正有意义。查看这些值，您可以看到 4 是第一组 4 的最大值，8 是第二组的最大值。这些值对应于我们想要的输入值 78 和 69。将最大值应用于表示位置的索引值是没有意义的(至少在这种情况下)，因此转换为排名是必要的。应用累积最大值给出:

⌈\A←⍋A[⍋(+\X)[A←⍋Y]]        ⍝ 3 4 4 4 7 7 8 8

剩下最后一步来完成索引。在进行了累积最大值运算之后，向量值仍然表示等级，因此需要将它们转换回索引值。为此，使用索引运算符。它采用右侧参数中的值并返回它们在左侧参数中找到的位置:

A⍳⌈\A←⍋A[⍋(+\X)[A←⍋Y]]      ⍝ 1 2 2 2 5 5 7 7

为了更容易看到:

3 4 2 1 7 5 8 6             left argument
3 4 4 4 7 7 8 8             right argument
1 2 2 2 5 5 7 7             result

4 在左侧参数中位于第二个位置，因此结果显示右侧参数中每 4 个 2。索引完成，将其应用于Y，我们得到预期的结果:

Y[A⍳⌈\A←⍋A[⍋(+\X)[A←⍋Y]]]    ⍝ 9 78 78 78 50 50 69 69