При решении некоторых Euler проблем Проекта для изучения Haskell (поэтому в настоящее время я - completly новичок) я приехал через проблему 12. Я записал это (наивное) решение:
--Get Number of Divisors of n
numDivs :: Integer -> Integer
numDivs n = toInteger $ length [ x | x<-[2.. ((n `quot` 2)+1)], n `rem` x == 0] + 2
--Generate a List of Triangular Values
triaList :: [Integer]
triaList = [foldr (+) 0 [1..n] | n <- [1..]]
--The same recursive
triaList2 = go 0 1
where go cs n = (cs+n):go (cs+n) (n+1)
--Finds the first triangular Value with more than n Divisors
sol :: Integer -> Integer
sol n = head $ filter (\x -> numDivs(x)>n) triaList2
Это решение для n=500
(sol 500)
является чрезвычайно медленным (работающий больше 2 часов теперь), таким образом, я задался вопросом, как узнать, почему это решение является настолько медленным. Есть ли какие-либо команды, которые говорят мне, где большая часть времени вычисления проведена так, я знаю, какая часть моей haskell-программы является медленной? Что-то как простой профилировщик.
Для прояснения я не прошу более быстрое решение, но способ найти это решение. Как Вы запустили бы, если у Вас не будет haskell знания?
Я пытался записать два triaList
функции, но найденный никаким способом протестировать, какой быстрее, таким образом, это - то, где мои проблемы запускаются.
Спасибо
как узнать, почему это решение такое медленное. Существуют ли какие-либо команды, которые сообщают мне, на что тратится большая часть времени вычислений, чтобы я знал, какая часть моей программы haskell является медленной?
Точно! GHC предоставляет множество отличных инструментов, в том числе:
Учебное пособие по использованию пространственно-временного профилирования является частью Real World Haskell .
Статистика GC
Во-первых, убедитесь, что вы компилируете с использованием ghc -O2. И вы можете убедиться, что это современный GHC (например, GHC 6.12.x)
Первое, что мы можем сделать, это проверить, не проблема ли сборка мусора. Запустите вашу программу с помощью + RTS -s
$ time ./A +RTS -s
./A +RTS -s
749700
9,961,432,992 bytes allocated in the heap
2,463,072 bytes copied during GC
29,200 bytes maximum residency (1 sample(s))
187,336 bytes maximum slop
**2 MB** total memory in use (0 MB lost due to fragmentation)
Generation 0: 19002 collections, 0 parallel, 0.11s, 0.15s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 13.15s ( 13.32s elapsed)
GC time 0.11s ( 0.15s elapsed)
RP time 0.00s ( 0.00s elapsed)
PROF time 0.00s ( 0.00s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 13.26s ( 13.47s elapsed)
%GC time **0.8%** (1.1% elapsed)
Alloc rate 757,764,753 bytes per MUT second
Productivity 99.2% of total user, 97.6% of total elapsed
./A +RTS -s 13.26s user 0.05s system 98% cpu 13.479 total
. Это уже дает нам много информации: у вас есть только куча 2M, а сборка мусора занимает 0,8% времени. Так что не нужно беспокоиться, что проблема заключается в распределении.
Временные профили
Получить временной профиль для вашей программы просто: скомпилируйте с -prof -auto-all
$ ghc -O2 --make A.hs -prof -auto-all
[1 of 1] Compiling Main ( A.hs, A.o )
Linking A ...
И для N = 200:
$ time ./A +RTS -p
749700
./A +RTS -p 13.23s user 0.06s system 98% cpu 13.547 total
, который создает файл, A.prof, содержащий:
Sun Jul 18 10:08 2010 Time and Allocation Profiling Report (Final)
A +RTS -p -RTS
total time = 13.18 secs (659 ticks @ 20 ms)
total alloc = 4,904,116,696 bytes (excludes profiling overheads)
COST CENTRE MODULE %time %alloc
numDivs Main 100.0 100.0
Указывает, что все ваше время тратится в numDivs, и это также источник всех ваших выделений.
Профили кучи
Вы также можете получить разбивку этих распределений, запустив команду + RTS -p -hy, которая создает A.hp, который вы можете просмотреть, преобразовав его в файл postscript (hp2ps -c A.hp), генерируя:
, который говорит нам, что нет ничего плохого в использовании вашей памяти: она распределяется в постоянном пространстве.
Итак, ваша проблема - алгоритмическая сложность numDivs:
toInteger $ length [ x | x<-[2.. ((n `quot` 2)+1)], n `rem` x == 0] + 2
Исправьте это, что составляет 100% вашего рабочего времени, а все остальное легко.
Оптимизация
Это выражение является хорошим кандидатом для оптимизации слияния потоков , поэтому я его перепишу использовать Data.Vector , например так:
numDivs n = fromIntegral $
2 + (U.length $
U.filter (\x -> fromIntegral n `rem` x == 0) $
(U.enumFromN 2 ((fromIntegral n `div` 2) + 1) :: U.Vector Int))
Который должен сливаться в один цикл без ненужного выделения кучи. То есть она будет иметь лучшую сложность (с постоянными коэффициентами), чем версия со списком. Вы можете использовать инструмент ghc-core (для опытных пользователей) для проверки промежуточного кода после оптимизации.
При тестировании ghc -O2 --make Z.hs
$ time ./Z
749700
./Z 3.73s user 0.01s system 99% cpu 3.753 total
Таким образом, время выполнения для N = 150 сократилось в 3,5 раза, без изменения самого алгоритма.
Заключение
Ваша проблема - numDivs. Это 100% вашего рабочего времени, и он ужасно сложен. Подумайте о numDivs и о том, как, например, для каждого N вы генерируете [2 .. n div
2 + 1] N раз.
Попробуйте запомнить это, поскольку значения не меняются.
Чтобы измерить, какая из ваших функций работает быстрее, рассмотрите возможность использования критерия , который предоставит статистически надежную информацию о субмикросекундных улучшениях времени работы.
Дополнение
Поскольку numDivs составляет 100% вашего рабочего времени, прикосновение к другим частям программы не имеет большого значения, однако в педагогических целях мы также можем переписать их, используя слияние потоков.
Мы также можем переписать trialList и полагаться на fusion, чтобы превратить его в цикл, который вы пишете вручную в trialList2, которая представляет собой функцию "сканирования префикса" (также известную как scanl):
triaList = U.scanl (+) 0 (U.enumFrom 1 top)
where
top = 10^6
Аналогично для sol:
sol :: Int -> Int
sol n = U.head $ U.filter (\x -> numDivs x > n) triaList
С тем же общим временем работы, но немного более чистым кодом.
Ответ Дона прекрасен, но не является спойлером, поскольку дает прямое решение проблемы.
Здесь я хочу предложить небольшой инструмент , который я написал недавно. Это экономит ваше время при написании аннотаций SCC вручную, если вам нужен более подробный профиль, чем профиль по умолчанию ghc -prof -auto-all
. Кроме того, это красочно!
Вот пример кода, который вы указали (*), зеленый - в порядке, красный - медленный:
Все время идет на создание списка делителей. Это говорит о том, что вы можете сделать следующее:
1. Сделайте фильтрацию n rem x == 0
быстрее, но поскольку это встроенная функция, вероятно, она и так быстрая.
2. Составьте более короткий список. Вы уже сделали что-то в этом направлении, проверив только до n quot 2
.
3. Полностью откажитесь от генерации списков и используйте математику, чтобы получить более быстрое решение. Это обычный способ решения задач Эйлера проекта.
(*) Я получил это, поместив ваш код в файл с именем eu13.hs
, добавив основную функцию main = print $ sol 90
. Затем запустите visual-prof -px eu13.hs eu13
, и результат будет в eu13.hs.html
.
Вы можете запускать свою программу с флагами, чтобы включить профилирование времени. Примерно так:
./program +RTS -P -sprogram.stats -RTS
Это должно запустить программу и создать файл с именем program.stats, в котором будет указано, сколько времени было потрачено на каждую функцию. Дополнительную информацию о профилировании с помощью GHC можно найти в руководстве пользователя GHC . Для тестирования есть библиотека Criterion. Я обнаружил , что эта запись в блоге содержит полезное введение.
Замечание по Haskell: triaList2
, конечно, быстрее, чем triaList
, потому что последний выполняет множество ненужных вычислений. Для вычисления n первых элементов triaList
потребуется квадратичное время, но линейно для triaList2
. Есть еще один элегантный (и эффективный) способ определения бесконечного ленивого списка чисел треугольника:
triaList = 1 : zipWith (+) triaList [2..]
Примечание, связанное с математикой: нет необходимости проверять все делители до n / 2, достаточно проверить до sqrt (n) .