Задача с Эйлера про гипотезу Коллатца

Найти длиннейшую сиракузскую последовательность со стартовым числом менее мильона

https://ru.wikipedia.org/wiki/%D0%93%D0%B8%D0%BF%D0%BE%D1%82%D0%B5%D0%B7%D0%B0_%D0%9A%D0%BE%D0%BB%D0%BB%D0%B0%D1%82%D1%86%D0%B0

import Data.List

collatzTransform :: Integral a => a -> a
collatzTransform n = if (n `mod` 2) == 0 then n `quot` 2 else 3*n + 1

collatzSequence :: Integral a => [a] -> [a]
collatzSequence (1:xs) = []
collatzSequence (x:xs) = newVal : collatzSequence(newVal:xs)
  where newVal = collatzTransform $ x

lens = map (\x -> (x, length $ collatzSequence [x]))  [1..999999]

sortGT (a1, b1) (a2, b2) = compare b1 b2

main = do print $ maximumBy sortGT lens

Ди Вельт аршинным заголовком: Вчера Гитлер и Данциг, сегодня Пуцен и Донецк

Высшие умы русского национализма в одной фотке

Ура, быстродействие Хаскелла реабилитировано!

C:\Users\dmitri\git\euler>ptime "c:\Program Files (x86)\nodejs\node.exe" bench.js
Execution time:1.874 s

C:\Users\dmitri\git\euler>ptime bench.exe
Execution time: 0.456

Теперь Хаскелл не в 4 раза медленне чем Ноде, а в 3 раза быстрее

Мощнейшее ускорение было достигнуто путем изменения алгоритма в Хаскелле

вместо

isPrimeBad x = length failedDividerCandidates == length dividerCandidates

поставил (как в js)

isPrimeGood n = all (doesNotDivide n) dividerCandidates

и это сразу дало ускорение в 12 раз.

Спасибо thesz за указание на разность алгоритмов.

Но тут возникает теперь совсем другая проблема. Ок, теперь я знаю, как сделать быстрее для этого случая. Но мне совершенно не было интуитивно очевидно, что такая простая операция, как построение списка натуральных чисел от 1 до корня из N - радикально замедляет алгоритм, в котором ПО ВСЯКОМ ПРИХОДИТСЯ делить на эти самые числа, от 1 до корня из N. Если нужно делить, то это УЖЕ гораздо больше работы, чем просто построить список.

Вообще конечно глупо САМОМУ проверять языкы программирования на быстродействие

Учитывая, что уже всё давно проверено умными и прилежными людьми

на нетривиальных, правильно написанных алгоритмах

Например, вот сравнения скоростей Жабы и Хаскеля

http://benchmarksgame.alioth.debian.org/u32/benchmark.php?test=all&lang=java&lang2=ghc&data=u32

(no subject)

А вот почему Вам, мистер Дейвид Линч

не снять еще какой-нибудь полнометражный фильм, в духе МД ?

Сколько можно отлынивать.

Порицаем.

(no subject)