扰流板警报:这与来自Euler项目的Problem 14有关。
以下代码大约需要15秒才能运行。我有一个以1s运行的非递归Java解决方案。我认为我应该能够使这段代码更接近于此。
import Data.List
collatz a 1 = a
collatz a x
| even x = collatz (a + 1) (x `div` 2)
| otherwise = collatz (a + 1) (3 * x + 1)
main = do
print ((foldl1' max) . map (collatz 1) $ [1..1000000])
我已经使用
+RHS -p进行了概要分析，发现分配的内存很大，并且随着输入的增长而增长。对于n = 100,000，分配了1gb(!)，对于n = 1,000,000，分配了13gb(!!)。再一次，
-sstderr显示，尽管分配了很多字节，但总内存使用量为1mb，生产力为95％+，因此13gb可能是红鲱鱼。我可以想到几种可能性:
foldl1'，但也许我需要做更多的事情？是否可以标记collatz严格(甚至有意义吗？collatz不是优化尾部功能。我认为应该，但是不要知道一种确认方法。
一次仅需要将
collatz的两个结果存储在内存中(最大和当前)有什么建议么？
这几乎是Why is this Haskell expression so slow?的副本，尽管我会注意到快速Java解决方案不必执行任何备注。有什么方法可以加快速度而不必诉诸此方法吗？
供参考，这是我的分析输出:
Wed Dec 28 09:33 2011 Time and Allocation Profiling Report (Final)
scratch +RTS -p -hc -RTS
total time = 5.12 secs (256 ticks @ 20 ms)
total alloc = 13,229,705,716 bytes (excludes profiling overheads)
COST CENTRE MODULE %time %alloc
collatz Main 99.6 99.4
individual inherited
COST CENTRE MODULE no. entries %time %alloc %time %alloc
MAIN MAIN 1 0 0.0 0.0 100.0 100.0
CAF Main 208 10 0.0 0.0 100.0 100.0
collatz Main 215 1 0.0 0.0 0.0 0.0
main Main 214 1 0.4 0.6 100.0 100.0
collatz Main 216 0 99.6 99.4 99.6 99.4
CAF GHC.IO.Handle.FD 145 2 0.0 0.0 0.0 0.0
CAF System.Posix.Internals 144 1 0.0 0.0 0.0 0.0
CAF GHC.Conc 128 1 0.0 0.0 0.0 0.0
CAF GHC.IO.Handle.Internals 119 1 0.0 0.0 0.0 0.0
CAF GHC.IO.Encoding.Iconv 113 5 0.0 0.0 0.0 0.0
和-sstderr:
./scratch +RTS -sstderr
525
21,085,474,908 bytes allocated in the heap
87,799,504 bytes copied during GC
9,420 bytes maximum residency (1 sample(s))
12,824 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 40219 collections, 0 parallel, 0.40s, 0.51s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 35.38s ( 36.37s elapsed)
GC time 0.40s ( 0.51s elapsed)
RP time 0.00s ( 0.00s elapsed) PROF time 0.00s ( 0.00s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 35.79s ( 36.88s elapsed) %GC time 1.1% (1.4% elapsed) Alloc rate 595,897,095 bytes per MUT second
Productivity 98.9% of total user, 95.9% of total elapsed
和Java解决方案(不是我的解决方案，取自Project Euler论坛，删除了备忘录):
public class Collatz {
public int getChainLength( int n )
{
long num = n;
int count = 1;
while( num > 1 )
{
num = ( num%2 == 0 ) ? num >> 1 : 3*num+1;
count++;
}
return count;
}
public static void main(String[] args) {
Collatz obj = new Collatz();
long tic = System.currentTimeMillis();
int max = 0, len = 0, index = 0;
for( int i = 3; i < 1000000; i++ )
{
len = obj.getChainLength(i);
if( len > max )
{
max = len;
index = i;
}
}
long toc = System.currentTimeMillis();
System.out.println(toc-tic);
System.out.println( "Index: " + index + ", length = " + max );
}
}
最佳答案
一开始，我认为您应该尝试在collatz的a之前加上一个感叹号:
collatz !a 1 = a
collatz !a x
| even x = collatz (a + 1) (x `div` 2)
| otherwise = collatz (a + 1) (3 * x + 1)
(您需要将
{-# LANGUAGE BangPatterns #-}放在源文件的顶部，以使其正常工作。)我的推理如下:问题是您在collatz的第一个参数中建立了一个庞大的thunk:它以
1开头，然后变成1 + 1，然后变成(1 + 1) + 1，...都没有被强迫。此bang pattern会在每次调用时强制强制collatz的第一个参数，因此它以1开始，然后变为2，依此类推，而不会建立大量未经评估的重击:它只是保持为整数。注意bang模式只是使用
seq 的简写；在这种情况下，我们可以如下重写collatz:collatz a _ | seq a False = undefined
collatz a 1 = a
collatz a x
| even x = collatz (a + 1) (x `div` 2)
| otherwise = collatz (a + 1) (3 * x + 1)
这里的技巧是迫使a进入后卫，然后总是评估为False(因此，身体无关紧要)。然后，对已经评估过的下一种情况继续进行评估。但是，爆炸模式更清晰。
不幸的是，当使用
-O2编译时，它的运行速度没有原始的快!我们还能尝试什么？好吧，我们可以做的一件事是假设两个数字永远不会溢出机器大小的整数，并为collatz提供这种类型的注释:collatz :: Int -> Int -> Int
我们将保留“爆炸”模式，因为我们仍然应该避免积累重击，即使它们不是性能问题的根源。这使我的(慢速)计算机上的时间减少到8.5秒。
下一步是尝试使其更接近Java解决方案。首先要意识到的是，在Haskell中，
div相对于负整数以数学上更正确的方式运行，但比“常规” C除法(在Haskell中称为quot)要慢。用div替换quot可使运行时间缩短至5.2秒，而用x `quot` 2替换x `shiftR` 1(导入Data.Bits)以匹配Java解决方案则可以将运行时间缩短至4.9秒。这大约是我目前能得到的，但是我认为这是一个很好的结果。由于您的计算机比我的计算机快，因此它应该更接近Java解决方案。
这是最终的代码(在此过程中，我做了一些清理工作):
{-# LANGUAGE BangPatterns #-}
import Data.Bits
import Data.List
collatz :: Int -> Int
collatz = collatz' 1
where collatz' :: Int -> Int -> Int
collatz' !a 1 = a
collatz' !a x
| even x = collatz' (a + 1) (x `shiftR` 1)
| otherwise = collatz' (a + 1) (3 * x + 1)
main :: IO ()
main = print . foldl1' max . map collatz $ [1..1000000]
查看该程序的GHC Core(带有
ghc-core )，我认为这可能和它获得的效果差不多。 collatz循环使用未装箱的整数，程序的其余部分看起来正常。我能想到的唯一改进是消除了map collatz [1..1000000]迭代中的装箱。顺便说一句，不用担心“总分配”这个数字。它是在程序生命周期内分配的总内存，即使GC回收了该内存，它也永远不会减少。数TB的数字很常见。