j - 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.在这里对你没有任何帮助。

您的代码正在构建一个链，一次一个链接:

    -:`(>:@(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 分钟，但这不是重点。)

为了使内存有意义，您需要替换更昂贵的计算。

对于这个特定问题，您可能需要一个函数，该函数接受一个整数并在序列到达 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似乎使
巨大的差异。我以为我可能在那里犯了一个错误，但是快速测试表明交换它们会在时间和空间上造成巨大的性能损失:

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

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

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

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