Почему на Haskell получается так медленно?
От: Kirikaza Россия kirikaza.ru
Дата: 21.12.11 19:04
Оценка:
Доброе время суток!

Написали мы программу, которая находит первые 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).

--
Спасибо за внимание!
haskell slow медленный
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.