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

中的第三个项称为“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中找到另一个数字。在给出的例子中，x将每个阵列分成两个相等的4个数的部分。在第一部分中，9是最大值直到78遇到，并且在第二部分50是最大值直到69遇到。
这很容易理解，我可以盲目地使用它，但我想了解它是如何工作的，因为apl习语本质上是由运算符和函数组成的算法。要很好地理解apl，很重要的一点是理解大师们是如何将它编织成如此简洁优雅的代码行的。
我发现这个特殊的习语尤其难以理解，因为索引嵌套了两层深。所以我的问题是，是什么让这个成语得体？

最佳答案

这个习语可以分解成更小的习语，最重要的是，它包含了来自Finnapl图书馆的习语11，题为：
分级（）用于排序由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）的第四位；3表示第二位中的第三位（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的x1 1 2 1 2 2 2 1的排序累积加法（sca）是compress left和compress right的组合。与1对齐的A的所有值都向左移动，而与2对齐的A的所有值都向右移动当然，如果X有更多的1s，它将按照SCA结果值指示的顺序压缩和定位压缩包例如，如果x的sca类似于3 3 2 1 2 2 1 1 1，那么您将得到对应于1s的4位数字，然后是对应于2s的3位数字，最后是对应于3s的2位数字。
你可能已经注意到了，我跳过了一步，这一步将显示升级的效果：

(+\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文章中所讨论的，它有效地充当了秩同样在那篇文章中，我也谈到了等级和指数是如何本质上是同一枚硬币的两面，你可以使用grade up在两者之间切换因此，这就是这里所发生的事情：sca被转换为一个应用于的索引，其效果是按x所示对排序的子向量进行分级。
从排序子向量到累积最大值
如前所述，对子向量排序的结果是一个索引，当应用于y时，该索引将数据压缩为数据包，并根据x排列这些数据包。重点是，它是一个索引，然后再次应用grade 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

关于algorithm - APL中X表示的累积最大值，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/17447610/