Как повысить эффективность с помощью функционального программирования?

Недавно я изучал руководство « Learn You a Haskell for Great Good», и на практике я хотел решить с ним задачу Project Euler 5 , в которой указано:

Какое наименьшее положительное число равномерно делится на все числа от 1 до 20?

Я решил сначала написать функцию, определяющую, делится ли данное число на эти числа:

divisable x = all (\y -> x `mod` y == 0)[1..20]

Затем я рассчитал наименьшее из них, используя head:

sm = head [x | x <- [1..], divisable x]

И, наконец, написал строку для отображения результата:

main = putStrLn $ show $ sm

К сожалению, это заняло около 30 секунд, чтобы закончить. Выполнение того же действия с числами от 1 до 10 дает результат почти сразу, но с другой стороны, результат намного меньше, чем решение для 1 до 20.

Я решил это ранее в C, и там результат для 1 до 20 также был вычислен почти мгновенно. Это заставляет меня поверить, что я неправильно понимаю, как интерпретировать эту проблему для Хаскелла. Я просмотрел решения других людей и нашел это:

main = putStrLn $ show $ foldl1 lcm [1..20]

Честно говоря, здесь используется встроенная функция, но почему конечный результат намного медленнее, если вы делаете это самостоятельно? В руководствах рассказывается, как использовать Haskell, но я не вижу особой помощи в преобразовании алгоритмов в быстрый код.

Прежде всего вы должны убедиться, что у вас есть оптимизированный двоичный файл, прежде чем думать, что проблема в языке. Прочитайте раздел « Профилирование и оптимизация» в Real Wolrd Haskell. Стоит отметить, что в большинстве случаев высокоуровневая природа языка стоит вам хотя бы части производительности.

Однако обратите внимание, что другое решение не быстрее, потому что оно использует встроенную функцию, а просто потому, что оно использует гораздо более быстрый алгоритм : чтобы найти наименьшее общее кратное из набора чисел, вам нужно найти только несколько GCD. Сравните это с вашим решением, которое перебирает все числа от 1 до foldl lcm [1..20]. Если вы попробуете с 30, разница между временем выполнения будет еще больше.

Посмотрите на сложности: ваш алгоритм имеет O(ans*N)время выполнения, где ansответ и Nчисло, до которого вы проверяете делимость (20 в вашем случае).
Другой алгоритм выполняет Nвремя lcm, однако lcm(a,b) = a*b/gcd(a,b), и GCD имеет сложность O(log(max(a,b))). Поэтому второй алгоритм имеет сложность O(N*log(ans)). Вы можете судить сами, что быстрее.

Итак, подведем итог:
ваша проблема в вашем алгоритме, а не в языке.

Обратите внимание, что существуют специализированные языки, которые функциональны и ориентированы на сложные математические программы, такие как Mathematica, которая для задач, ориентированных на математику, вероятно, быстрее, чем что-либо еще. Он имеет очень оптимизированную библиотеку функций и поддерживает функциональную парадигму (правда, он также поддерживает императивное программирование).

Моей первой мыслью было, что только числа, кратные всем простым числам <= 20, будут делиться на все числа, меньшие 20. Поэтому вам нужно учитывать только числа, кратные 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 , Такое решение проверяет 1/9 699 690 столько же чисел, сколько и метод грубой силы. Но ваше быстрое решение Haskell работает лучше, чем это.

Если я понимаю «быстрое решение Haskell», оно использует foldl1, чтобы применить функцию lcm (наименьшее общее кратное) к списку чисел от 1 до 20. Таким образом, он применил бы lcm 1 2, давая 2. Затем lcm 2 3, давая 6 Затем lcm 6 4, получая 12 и так далее. Таким образом, функция lcm вызывается только 19 раз, чтобы получить ваш ответ. В обозначении Big O это O (n-1) операций, чтобы прийти к решению.

Ваше медленное решение Haskell проходит номера 1-20 для каждого числа от 1 до вашего решения. Если мы называем решение s, то решение с медленным Haskell выполняет O (s * n) операций. Мы уже знаем, что s превышает 9 миллионов, что, вероятно, объясняет медлительность. Даже если все ярлыки и в среднем получаются в середине списка чисел 1-20, это все равно только O (s * n / 2).

Вызов headне спасает вас от выполнения этих вычислений, они должны быть выполнены, чтобы вычислить первое решение.

Спасибо, это был интересный вопрос. Это действительно расширило мои знания Хаскеля. Я не смог бы ответить на это вообще, если бы я не изучал алгоритмы прошлой осенью.

Я изначально не планировал писать ответ. Но мне сказали, что после того, как другой пользователь сделал странное утверждение, что просто умножение простых чисел первой пары было более вычислительно дорогим, чем повторное применение lcm. Итак, вот два алгоритма и некоторые тесты:

Мой алгоритм:

Алгоритм генерации простых чисел, дающий мне бесконечный список простых чисел.

isPrime :: Int -> Bool
isPrime 1 = False
isPrime n = all ((/= 0) . mod n) (takeWhile ((<= n) . (^ 2)) primes)

toPrime :: Int -> Int
toPrime n 
    | isPrime n = n 
    | otherwise = toPrime (n + 1)

primes :: [Int]
primes = 2 : map (toPrime . (+ 1)) primes

Теперь используем этот простой список для вычисления результата для некоторых N:

solvePrime :: Integer -> Integer
solvePrime n = foldl' (*) 1 $ takeWhile (<= n) (fromIntegral <$> primes)

Теперь другой основанный на lcm алгоритм, который, по общему признанию, является довольно лаконичным, главным образом потому, что я реализовал простое генерирование с нуля (и не использовал алгоритм понимания супер сжатого списка из-за его низкой производительности), тогда как он lcmбыл просто импортирован из Prelude.

solveLcm :: Integer -> Integer
solveLcm n = foldl' (flip lcm) 1 [2 .. n]
-- Much slower without `flip` on `lcm`

Теперь для тестов, код, который я использовал для каждого, был прост: ( -prof -fprof-auto -O2тогда +RTS -p)

main :: IO ()
main = print $ solvePrime n
-- OR
main = print $ solveLcm n

Для n = 100,000, solvePrime:

total time = 0.04 secs
total alloc = 108,327,328 bytes

против solveLcm:

total time = 0.12 secs
total alloc = 117,842,152 bytes

Для n = 1,000,000, solvePrime:

total time = 1.21 secs
total alloc = 8,846,768,456 bytes

против solveLcm:

total time = 9.10 secs
total alloc = 8,963,508,416 bytes

Для n = 3,000,000, solvePrime:

total time = 8.99 secs
total alloc = 74,790,070,088 bytes

против solveLcm:

total time = 86.42 secs
total alloc = 75,145,302,416 bytes

Я думаю, что результаты говорят сами за себя.

Профилировщик указывает, что генерация простых чисел занимает все меньше и меньше процента времени выполнения по мере nувеличения. Так что это не узкое место, поэтому мы можем пока игнорировать это.

Это означает, что мы действительно сравниваем вызов, lcmгде один аргумент идет от 1 до n, а другой геометрически от 1 до ans. Для звонков *с такой же ситуацией и дополнительным преимуществом пропуска каждого непростого номера (асимптотически бесплатно, из-за более дорогой природы *).

И хорошо известно, что *это быстрее, чем lcm, что lcmтребует многократного применения mod, и modасимптотически медленнее ( O(n^2)против ~O(n^1.5)).

Таким образом, приведенные выше результаты и краткий анализ алгоритма должны сделать очень очевидным, какой алгоритм быстрее.