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

A>

A>import Data.List

A>firstPrimes ::Int->[Int]
A>firstPrimes  n= take n $ filter (isPrime) [2..]

A>count::Int->Int
A>count n= foldl' (+) 0 (firstPrimes  n)

A>isPrime::Int->Bool
A>isPrime x = null $ filter (\y ->  x `mod` y == 0) $ takeWhile (\y ->  y*y <= x) [2..]

A>main = do
A>        putStrLn $ (show . count) 5000
A>

Здесь есть "нечестная" оптимизация при поиске делителей (до квадратного корня), поэтому цифра фантастическая – 0,04c.

Я заменил эту проверку на \y -> y < x – и о чудо! – удалось выжать 3.7с на Haskell против 3.9с на Си! Круто, копаю дальше.

Заменил конструкцию takeWhile (\y -> y < x) [2..] на [2..x-1]... и получил уже 1.9с!

Стало весьма интересно, откуда всё это. С foldl' я уже пробовал баловаться вместо sum – разницы не было. Проведя несколько экспериментов, выяснил, что null xs работает гораааздо быстрее, чем length xs == 0. На данном примере – в 10 раз. В принципе, можно найти этому объяснение; тем не менее в Notes_about_speed об этом ни слова.

В приводимом мной коде делители считались от 1 до самого числа включительно, поэтому длину списка делителей нужно было сравнивать с 2. Т.е. null уже не подходит... И тут пришла идея сравнивать не длину списка делителей, а сам этот список с [1,x]. И чудо повторилось: программа выполнилась за 1,9с.

Таким образом, минимальным изменением время выполнения снизилось с 20с до 1,9с:

divisors num = filter (\i -> (mod num i) == 0 ) [1..num]

-- isPrime num = length (divisors num) == 2
isPrime num = (divisors num) == [1,num]

firstPrimes count = take count (filter isPrime [1..])

count = 5000

main = print $ sum ( firstPrimes count :: [Int])

В принципе, мне так даже больше нравится, но... может кто-нибудь объяснить, в чём здесь фокус?

P.S.: После замены mod на rem время снизилось ещё – до 1,5c.