通常scan，左变体和右变体，在空间和时间上都是 O(n)。不过，APL 似乎\运算符就像scanl但似乎表现不同，因为它是右关联的并且每次都在数组上运行，使其成为 O(n^2)。
例如，
nums ← 10?10 ⍝ 1 7 4 5 10 3 9 6 2 8
⌈\nums ⍝ 1 7 7 7 10 10 10 10 10 10
给了我正确的行为，但根据右关联性相当于
(1 f (7 f (4 f (5 f (10 f (3 f (9 f (6 f (2 f 8))))))))) ⍝ where f ← (⊣,⌈)
所以最后一个操作是1 f (7 7 7 10 10 10 10 10 10)
这不是效率低下吗？这里实际的大 O 复杂度是多少和/或是否有一些惯用的优化？
你的算法描述 Scan 是正确的，在一般情况下，它确实是 O(N²) 。然而，到目前为止，它最常见的用途是与一组已知的标量基元（包括+, ∨, ∧, ⌈, ⌊, <, ≤, ≠）。这些由解释器识别，然后解释器使用特殊的代码 O(n)（或更少，因为它们可能会提前离开）代码。
我们可以通过比较性能来轻松证明这一点+与功能相同的+∘⊢（另外，正确的参数由恒等函数预处理）：
'cmpx'⎕CY'dfns'
a←?2000⍴127
cmpx'+∘⊢\a'
1.8E¯1
a←?4000⍴127
cmpx'+∘⊢\a'
7.6E¯1
我们可以看到+∘⊢\当我们将小整数的数量从 2000 增加到 4000 时，花费了大约 4 倍的时间 (0.2 s → 0.8 s)。然而：
a←?2000⍴127
cmpx'+\a'
1.5E¯6
a←?4000⍴127
cmpx'+\a'
2.9E¯6
+\当从 2000 到 4000 个小整数时，仅加倍（15 ms → 29 ms）。另请注意优化情况和非优化情况之间的极端性能差异。
Scan 从Reduce 获取其评估顺序。Iverson https://apl.wiki/Ken_Iverson解释在评估顺序约定 https://www.jsoftware.com/papers/EvalOrder.htm:
- 在定义中
F/x ≡ x1 F x2 F x3 F ... F x⍴x
从右到左约定比从左到右约定为非关联函数 F 提供了更有用的定义。例如，-/x表示各分量的交替和x，而在从左到右的约定中，它将表示第一个分量减去其余分量的总和。因此如果d是表示数字的十进制数字的向量n，那么表达式的值0=9|+/d决定了可分性n by 9;在从右到左的约定中，类似的表达式0=11|-/d确定整除性11 .
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
