Ответ 1
как узнать, почему это решение так медленно. Есть ли какие-нибудь команды, которые говорят мне, где большая часть времени вычислений тратится, поэтому я знаю, какая часть моей программы haskell медленна?
Точно! GHC предоставляет множество отличных инструментов, в том числе:
- статистика времени выполнения
- профилирование времени
- профилирование кучи
- анализ потоков
- основной анализ.
- сравнительный бенчмаркинг
- Настройка GC
Учебник по использованию профилирования времени и пространства часть 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
Что уже дает нам много информации: у вас есть только куча 2М, а GC занимает 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,5x без изменения самого алгоритма.
Заключение
Ваша проблема - numDivs. Это 100% от вашего времени работы и имеет ужасную сложность. Подумайте о numDivs и о том, как, например, для каждого N вы генерируете [2.. n div 2 + 1] N раз.
Попытайтесь запомнить это, поскольку значения не меняются.
Чтобы измерить, какая из ваших функций выполняется быстрее, рассмотрите возможность использования criterion, который предоставит статистически достоверную информацию о улучшениях в субмикросекундах время.
Addenda
Так как numDivs составляет 100% от вашего времени работы, касание других частей программы не будет иметь большого значения, однако для педагогических целей мы также можем переписать те, которые используют слияние потоков.
Мы также можем переписать trialList и полагаться на слияние, чтобы превратить его в цикл, который вы пишете вручную в trialList2, которая является функцией "префиксного сканирования" (aka 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
С таким же общим временем работы, но с более чистым кодом.
