素数的计算比较哈斯克尔和C的速度 [英] Comparing speed of Haskell and C for the computation of primes
问题描述
我最初写这个（蛮力和低效），有使用之间的速度没有差别与确保的意图计算素数的方法IF-THEN-ELSE与在Haskell卫士（并没有什么区别！ ）。但后来我决定写一个C程序进行比较，我得到了以下（Haskell的速度慢一些刚刚超过25％）：
I initially wrote this (brute force and inefficient) method of calculating primes with the intent of making sure that there was no difference in speed between using "if-then-else" versus guards in Haskell (and there is no difference!). But then I decided to write a C program to compare and I got the following (Haskell slower by just over 25%) :
（注意：我使用了REM，而不是mod的观点，并在从以下职位的编译器调用的O3选项：<一个href=\"http://stackoverflow.com/questions/6716315/on-improving-haskells-performance-compared-to-c-in-fibonacci-micro-benchmark\">On提高Haskell的性能相比到C斐波纳契微基准）
(Note I got the ideas of using rem instead of mod and also the O3 option in the compiler invocation from the following post : On improving Haskell's performance compared to C in fibonacci micro-benchmark)
哈斯克尔：Forum.hs 的
Haskell : Forum.hs
divisibleRec :: Int -> Int -> Bool
divisibleRec i j
| j == 1 = False
| i `rem` j == 0 = True
| otherwise = divisibleRec i (j-1)
divisible::Int -> Bool
divisible i = divisibleRec i (i-1)
r = [ x | x <- [2..200000], divisible x == False]
main :: IO()
main = print(length(r))
C：的main.cpp 的
C : main.cpp
#include <stdio.h>
bool divisibleRec(int i, int j){
if(j==1){ return false; }
else if(i%j==0){ return true; }
else{ return divisibleRec(i,j-1); }
}
bool divisible(int i){ return divisibleRec(i, i-1); }
int main(void){
int i, count =0;
for(i=2; i<200000; ++i){
if(divisible(i)==false){
count = count+1;
}
}
printf("number of primes = %d\n",count);
return 0;
}
我得到的结果如下：
The results I got were as follows :
编译时间的
Compilation times
time (ghc -O3 -o runProg Forum.hs)
real 0m0.355s
user 0m0.252s
sys 0m0.040s
time (gcc -O3 -o runProg main.cpp)
real 0m0.070s
user 0m0.036s
sys 0m0.008s
和以下运行时间：
Ubuntu上运行时间32位的
Running times on Ubuntu 32 bit
Haskell
17984
real 0m54.498s
user 0m51.363s
sys 0m0.140s
C++
number of primes = 17984
real 0m41.739s
user 0m39.642s
sys 0m0.080s
我是哈斯克尔的运行时间pssed相当IM $ P $。但是我的问题是这样的：我可以做任何事情，而不以加快哈斯克尔程序：
I was quite impressed with the running times of Haskell. However my question is this : can I do anything to speed up the haskell program without :
- 更改底层的算法（很显然，大规模的加速可以通过改变算法来获得，但我只是想了解什么，我可以在语言/编译器侧做，以提高性能）
- 调用LLVM编译器（因为我没有这个安装）
的
由Alan评论后，我注意到，在C程序使用的内存恒定的量，其中作为哈斯克尔计划增长缓慢的内存大小。起初我以为这有一些东西需要用递归，但GSPR下面解释为什么发生这种情况，并提供了解决方案。请问尼斯提供了一种替代解决方案，（如GSPR的解决方案）也保证了内存是静态的。
After a comment by Alan I noticed that the C program uses a constant amount of memory where as the Haskell program slowly grows in memory size. At first I thought this had something to do with recursion, but gspr explains below why this is happening and provides a solution. Will Ness provides an alternative solution which (like gspr's solution) also ensures that the memory remains static.
的
测试的最大数量1:200,000：
max number tested : 200,000:
（54.498s / 41.739s）= 哈斯克尔慢30.5％的
(54.498s/41.739s) = Haskell 30.5% slower
测试的最大数量40万：
max number tested : 400,000:
3m31.372s / 2m45.076s = 211.37s / 165s = 慢哈斯克尔28.1％的
3m31.372s/2m45.076s = 211.37s/165s = Haskell 28.1% slower
测试的最大数量：800000：
max number tested : 800,000:
14m3.266s / 11m6.024s = 843.27s / 666.02s = 慢哈斯克尔26.6％的
14m3.266s/11m6.024s = 843.27s/666.02s = Haskell 26.6% slower
的
这是我早前写的不具有递归和我20万测试code：
This was the code that I had written earlier which does not have recursion and which I had tested on 200,000 :
#include <stdio.h>
bool divisibleRec(int i, int j){
while(j>0){
if(j==1){ return false; }
else if(i%j==0){ return true; }
else{ j -= 1;}
}
}
bool divisible(int i){ return divisibleRec(i, i-1); }
int main(void){
int i, count =0;
for(i=2; i<8000000; ++i){
if(divisible(i)==false){
count = count+1;
}
}
printf("number of primes = %d\n",count);
return 0;
}
对于C code使用和不使用递归的结果如下（800,000）：
The results for the C code with and without recursion are as follows (for 800,000) :
使用递归：11m6.024s
With recursion : 11m6.024s
无递归：11m5.328s
Without recursion : 11m5.328s
请注意，该可执行文件似乎占用60KB（如在系统监视器看到的），不考虑的最大数量，因此，我怀疑是编译器检测此递归。
Note that the executable seems to take up 60kb (as seen in System monitor) irrespective of the maximum number, and therefore I suspect that the compiler is detecting this recursion.
推荐答案
这是不是真的回答你的问题，而是你在评论有关要求越来越多的内存使用，当数20万的增长。
This isn't really answering your question, but rather what you asked in a comment regarding growing memory usage when the number 200000 grows.
在这个数字的增长，所以没有列表研究。您code需要的所有研究的在最后，计算它的长度。在C code，而另一方面，只是增加一个计数器。你必须，如果你想不断的内存使用情况做在Haskell类似的东西了。在code依然会非常Haskelly，一般来说这是一个明智的命题：你并不真正需要的号码列表为其整除是假，你只需要知道有多少。
When that number grows, so does the list r. Your code needs all of r at the very end, to compute its length. The C code, on the other hand, just increments a counter. You'll have to do something similar in Haskell too if you want constant memory usage. The code will still be very Haskelly, and in general it's a sensible proposition: you don't really need the list of numbers for which divisible is False, you just need to know how many there are.
您可以尝试
main :: IO ()
main = print $ foldl' (\s x -> if divisible x then s else s+1) 0 [2..200000]
（与foldl'是一个严格的与foldl 从 Data.List模块可避免的thunk被建造）。
(foldl' is a stricter foldl from Data.List that avoids thunks being built up).
这篇关于素数的计算比较哈斯克尔和C的速度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
