optimization - J:关于将过滤器序列最佳应用到列表

Question

设 {f(i)}, i = 1,...,n 是一个过滤器序列(列表的每个项目都映射到一个 bool 值value) 具有以下属性:if f(i) = 1 对于列表中的某个项目，则每个 f(j) = 1 对于 j > i 和相同的项目。非常简单的例子:

   [ t =: i.5   NB. sample data
0 1 2 3 4

   f1 =: 2&>           NB. is greater than 2
   f2 =: 2&> +. 0=2&|  NB. is greater than 2 OR even

   (f1 ,: f2) t
1 1 0 0 0
1 1 1 0 1

   (#~ f1 +. f2) t
0 1 2 4

显然没有必要将 f2 应用于 t 的前 2 项(f1 已经接受)。

问题:如何避免将f(j)应用于f(i)为j >接受的项目我？

我天真的实现

我。 -. f1 t - 那些不被 f1 接受的项目的索引。那么为什么不选择它们，应用 f2 并修改呢？我认为这是一种错误的方法，因为这种方法会占用大量内存，对吗？

   t #~ (f1 t) (I. -. f1 t)}~ f2 (I. -. f1 t) { t
0 1 2 4

而且许多过滤器的代码更难。

Answer 1

虽然可以按照您在此处寻求的方式避免计算，但这样做往往会“违背”J 的原则。值得注意的是，这样做可能会增加时间和空间要求。

一种技术是使用 f1 的结果过滤 f2 的参数，然后扩展 f2 的结果以与f1 的结果。这将涉及在内存中创建一个新数组以便准确地具有必要的值，加上一个临时结果数组，以及对该结果进行计算以使其符合原始参数的形状。这些东西不是免费的。

最重要的是，这种微观管理涉及摆脱 J 程序员所说的数组思维。涉及将名词“作为一个整体”(以及作为一致的矩形)处理的解决方案通常适合在 J 中进行简洁的表达。

对于某些类型的数据的某些类型的计算，您提出的问题类别可能很重要。在这种情况下，可能值得设计一些技术来传达部分结果并有选择地避免动词的可避免应用。我猜想 Power (^:) 在许多此类工作中会有用。但是这些解决方案都非常具体地针对出现实际性能问题的情况。

我冒险做出以下声明:您的问题没有一般答案，因为 J 的一般性不支持细粒度干预。我怀疑您很清楚 J 表现出这种偏见。这种偏见使您提出的问题成为技术难题。

由于此问题的解决方案通常不会在更短的时间内运行，也不会减少内存，也不会有助于表达的简洁性或功能的清晰性，因此“优化”似乎不太可能成为他们的标签。