Приветствую,

Я решаю задачи Project Euler на Haskell. Обычно время выполнения задач (при использовании одинаковых алгоритмов)
получаются не намного медленнее чем на C.

Однако с задачей 145 здесь не получилось.
На языке С она решается прямым перебором за меньше минуты. На Haskell же получить результат хотя-бы за пол-часа не вышло.

Код на С:

const int lim = 1000000000;

bool isNumberOk ( int *digits, int digLen ) {
    int *ptr1 = digits;
    int *ptr2 = digits+digLen-1;
    bool carry = false;
    
    if (digits[0] == 0) {
    return false;
    }
    
    for( ; digLen; --digLen ) {
        int tmp = *ptr1++ + *ptr2--;
        if (carry) {
            tmp++;
        }
        carry = tmp >= 10;
        if (tmp % 2 == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int digits[10];
    int cntr = 0;
    for( int i=1; i<lim; ++i ) {
        int j=0;
        int tmp = i;
        for( ;tmp; ++j ) { 
            digits[j] = tmp % 10; 
            tmp /= 10;
        }
        if (isNumberOk(digits,j) ) {
            cntr += 1;
        }    
    }
    printf( "%d\n", cntr );
    return 0;
}

Код на Haskell:

digits :: Int -> [Int]
digits 0 = [0]
digits n = digits' n

digits' 0 = []
digits' n = dg : (digits' rest)
    where
        (rest, dg) = n `divMod` 10

addLists [] [] c = []
addLists (h1:t1) (h2:t2) c = r1 : (addLists t1 t2 c1)
    where
        r1 = h1+h2+c
        c1 = if r1 >= 10 then 1 else 0
        
isOk :: [Int] -> Bool
isOk nDgts
    | head nDgts == 0 || head revN == 0            = False
    | otherwise                                 = all odd $ addLists nDgts revN 0
    where 
        revN = reverse nDgts


makeDgts2 n = tail $ map (dropWhile (==0)) $ makeDgts n 
makeDgts 0 = [[]] 
makeDgts n = [ x:y | x <- [0..9], y <- makeDgts (n-1) ]

prb cndExp = length $ filter isOk  cnds
    where
        cnds = makeDgts2 cndExp

prb2 cands = length $ filter isOk $ map digits cands

problem = prb 8

cands = [1..10^9]
-- problem = prb2 cands

Вопросы: Почему тормозит haskell решение? Что с ним можно сделать с целью ускорения (но оставив алгоритм прямого перебора)?

Александр.

P.S. Да, я знаю, что можно поменять алгоритм. Да, я видел оптимизированный алгоритм на haskell.org.

работает 2 минуты 13 секунд. неужели это слишком долго?
и, кстати, часть кода не используется (digits, prb2, cands, digits')

Здравствуйте, Аноним, Вы писали:

А>работает 2 минуты 13 секунд. неужели это слишком долго?

Как?

У меня ghc 6.10.4, Core2Duo 3GHz.
Пробовал запускать из ghci.
Пробовал компилировать с ключом -O и запускать exe-файл.

Распишите, пожалуйста, по шагам, как для чайника, как получено такое время?

Александр.

Здравствуйте, az1976, Вы писали:

А>>работает 2 минуты 13 секунд. неужели это слишком долго?

A>Как?

A>У меня ghc 6.10.4, Core2Duo 3GHz.
A>Пробовал запускать из ghci.
A>Пробовал компилировать с ключом -O и запускать exe-файл.

A>Распишите, пожалуйста, по шагам, как для чайника, как получено такое время?

У меня вот это решение:

prb cndExp = length $ filter isOk  cnds
    where
        cnds = makeDgts2 cndExp

problem = prb 8

main = print problem

Отрабатывает за 47 секунд. Сишная программа — за 32. Вот только память оно ест как не в себя, максимальное потребление около 1,5 ГБ. Список-то вычисляется лениво, но, насколько я понимаю, GC не может сразу подбирать обработанные узлы. Жаль, vacuum-cairo мне завести так и не удалось, визуализировать получающуюся структуру в уме сложно.

GHC 6.12.1, GCC 4.3.3, Linux x86-64, Phenom II X3 @2.6 ГГц