performance - Haskell 中的埃拉托斯特尼筛法执行时间

Question

我是 Haskell 的新手，正在编写使用列表解决埃拉托斯特尼筛问题的代码。这是代码

primes m = 2 : primes' m [3,5 ..m] [] where
primes' m integers@(p : xs) acc   | p*p>m =  reverse acc ++ integers
                                  | True  = primes' m (xs `remove` [p*p, p*p+2*p..m]) (p:acc)

remove integers@(x:xs) multiples@(y:ys) | x < y = x : remove xs multiples
                                        | x == y =    remove xs ys
                                        | x > y =     remove integers ys

remove integers multiples = integers

如果我输入 m = 2000000，代码大约需要 14 秒才能打印出所有结果。我认为 90% 的时间都花在了打印上，而不是实际执行代码。有没有办法找到这个特定程序的正确执行时间？

Answer 1

尝试一下

main = print $ last $ primes 2000000

所以它只会显示最后找到的素数。

使用-O2编译它并使用+RTS -s运行以查看总体计时和内存统计信息。

一定要在几个尺寸点进行测量，找出empirical orders of growth !真正的筛子运行速度约为 ~ n^1.1，产生 n 个素数。 ~ n^1.5 以内的任何内容都是可以的。 ~ n^2 很糟糕，比这更慢的就更糟糕了。 :)

从外观上看，你的应该没问题。