J中的记忆

Question

每次我使用J的M.副词时,性能都会大幅降低.因为我怀疑艾弗森和慧比我聪明得多,所以我一定做错了.

考虑一下Collat​​z猜想.这里似乎有各种各样的记忆机会,但无论我在哪里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分钟,但那不是重点.)

要使memoization有意义,您需要替换更昂贵的计算.

对于此特定问题,您可能需要一个取整数的函数,并在序列到达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.