剧透警告:这与 Problem 14 有关来自欧拉计划。
以下代码需要大约 15 秒才能运行。我有一个在 1 秒内运行的非递归 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
为 n = 1,000,000
分配了 1gb(!)分配了 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,依此类推,而不会产生大量未评估的 thunk:它只是保持为整数。请注意,爆炸模式只是使用
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 (因此 body 是无关紧要的)。然后评估继续下一个案例,a 已经被评估。但是,刘海模式更清晰。
不幸的是,当使用
-O2
编译时,这并不比原来的运行速度更快!我们还能尝试什么?好吧,我们可以做的一件事是假设这两个数字永远不会溢出机器大小的整数,并给出 collatz
这种类型注释:collatz :: Int -> Int -> Int
我们将把 bang 模式留在那里,因为我们仍然应该避免建立 thunk,即使它们不是性能问题的根源。这使我的(慢速)计算机上的时间缩短到 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 核心(带有
ghc-core
),我认为这可能是最好的; collatz
循环使用未装箱的整数,程序的其余部分看起来没问题。我能想到的唯一改进是从 map collatz [1..1000000]
中删除拳击。迭代。顺便说一句,不要担心“total alloc”这个数字;它是在程序生命周期内分配的总内存,即使 GC 回收该内存,它也不会减少。数 TB 的数字很常见。
关于haskell - 为什么这个简单的haskell算法这么慢?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8659345/