J 中的记忆

Question

每次我使用 J 的 M. 副词时，性能都会大大降低。我怀疑艾弗森和阿辉比我聪明多了，我一定是做错了。

考虑 Collatz conjecture。这里似乎有各种各样的记忆机会，但无论我把 M. 放在哪里，性能都很糟糕。例如：

hotpo =: -:`(>:@(3&*))@.(2&|) M.
collatz =: hotpo^:(>&1)^:a:"0
#@collatz 1+i.10000x

没有 M.，这在我的机器上运行大约 2 秒。 M.，好吧，我等了十多分钟才完成，最后放弃了。我还把 M. 放在其他位置，结果也很糟糕，例如

hotpo =: -:`(>:@(3&*))@.(2&|)
collatz =: hotpo^:(>&1)M.^:a:"0
#@collatz 1+i.10000x

有人可以解释 M. 的正确用法吗？

Answer 1

M. 在这里对您没有任何作用。

您的代码正在构建一条链，一次 link：

    -:`(>:@(3&*))@.(2&|)^:(>&1)^:a:"0 M. 5 5
5 16 8 4 2 1
5 16 8 4 2 1

在这里，它记住了 5 导致 16、16 导致 8、8 导致 4 等等......但这对你有什么用呢？它用内存查找替换了一些简单的算术，但算术非常简单，可能比查找更快。（我很惊讶你的例子花了整整 10 分钟，但这不是重点。）

为了使记忆有意义，您需要更换更昂贵的计算。

对于这个特定的问题，您可能需要一个函数，它接受一个整数，并且 return 当序列到达 1 时为 1。例如：

    -:`(>:@(3&*))@.(2&|)^:(>&1)^:_"0 M. 5 5
1 1

我所做的只是将 ^:a: 替换为 ^:_，以丢弃中间结果。即使这样也没有太大区别，不过可以用timespacex看看效果：

   timespacex  '-:`(>:@(3&*))@.(2&|)^:(>&1)^:_"0     i.100000'
17.9748 1.78225e7
   timespacex  '-:`(>:@(3&*))@.(2&|)^:(>&1)^:_"0  M. i.100000'
17.9625 1.78263e7

附录： M. 相对于 "0 的位置似乎使一个巨大的差异。我以为我可能在那里犯了一个错误，但快速测试表明交换它们会导致时间和 space:

的巨大性能损失

   timespacex  '-:`(>:@(3&*))@.(2&|)^:(>&1)^:_ M. "0  i.100000'
27.3633 2.41176e7

M. 保留了底层动词的等级，所以两者在语义上是等价的，但我怀疑像这样在外面的 "0，M. 不知道它正在处理标量。所以我想这里的教训是确保 M. 知道它在处理什么。 :)

顺便说一句，如果 Collatz 猜想被证明是错误的，并且您为这段代码提供了一个反例，它会进入无限循环而不是产生答案。

要实际检测反例，您需要监控中间结果，直到找到一个循环，然后 return 循环中的最小数字。为此，您可能想要实现一个自定义副词来替换 ^:n.

J 中的记忆

Memoization in J

j