Доброе время суток!
Написали мы программу, которая находит первые N простых чисел и вычисляет их сумму. Написали на C и на Haskell. Алгоритм тупой, но суть в том, что он одинаковый. В результате, программа на C выполняет задачу за 4 с, а на Haskell -- за 54 c. Из опций стоит только -O2.
Почему же такая разница? Привожу исходники:
int isPrime( int num ) {
int count = 0;
int i = 1;
for( ; i <= num ; ++i ) {
if( num % i == 0 ) ++count;
}
return 2 == count;
}
#define COUNT 5000
#include <stdio.h>
int main( void ) {
int count = 0;
int num = 1;
int sum = 0;
for( ; count < COUNT ; ++num ) {
if( isPrime( num ) ) {
sum += num;
++count;
}
}
printf( "%d\n" , sum );
return 0;
}
divisors num = filter (\i -> (mod num i) == 0 ) [1..num]
isPrime num = length (divisors num) == 2
firstPrimes count = take count (filter isPrime [1..])
count = 5000
main = print $ sum $ firstPrimes count
Впрочем, видно, что вариант на Haskell весь из себя ленивый и использует списки. Я пробовал расставлять строгость (сначала обдуманно, потом где попало) -- не помогло. Затем я подглядел вариант с параметром-аккумулятором и получился вот такой (страшный) код:
incDiv num i acc | mod num i == 0 = 1+acc
| otherwise = acc
divisors num i acc | i <= num = divisors num (i+1) (incDiv num i acc)
| otherwise = acc
isPrime' num = divisors num 1 0 == 2
primesSum count num acc | count > 0 = if isPrime' num
then primesSum (count-1) (num+1) (num+acc)
else primesSum count (num+1) acc
| otherwise = acc
count = 5000
main = print (primesSum count 1 0)
Однако я получил всё те же 54 с. Подскажите, пожалуйста, что я делаю не так, и возможно ли вообще в данном случае приблизить время исполнения к сишному варианту (хотя бы в два раза медленнее, но не в 13).
--
Спасибо за внимание!