Я наткнулся на Haskell и FP и был ошеломлен возможностями. И старый математик-ботаник внутри меня без проблем написал наивный код для реальных полезных целей. Однако, несмотря на все чтения, мне все еще трудно понять, как не попасть в некоторые неожиданные узкие места производительности.
Итак, я пишу очень короткие куски кода с наивными реализациями, а затем пробую небольшие изменения, чтобы увидеть, как реагирует производительность.
И вот один пример, который я действительно не могу понять ... Я написал эту функцию, которая находит решение проблемы Иосифа , с целью с реализацией наивного списка.
m = 3
n = 3000
main = putStr $ "Soldier #" ++ (show $ whosLeft [1..n]) ++ " survived...\n"
whosLeft [lucky] = lucky
whosLeft soldiers = whosLeft $ take (length soldiers -1) $ drop m $ cycle soldiers
Последний работает за 190 мс, с производительностью 63% по RTS.
Тогда первое, что я хотел попробовать, это удалить (длина солдата -1) и заменить его убывающим целым числом.
Время выполнения увеличилось до 900 мс, а производительность - до 16%, и использует в 47 раз больше памяти, чем простой код выше! Поэтому я добавил строгую оценку, принудительно ввел тип Int, попробовал такие вещи, как удаление глобальных переменных и другие, но без особой пользы. И я просто не могу понять это замедление.
m = 3::Int
n = 3000::Int
main = putStr $ "Soldier #" ++ (show $ whosLeft n [1..n]) ++ " survived...\n"
whosLeft 1 [lucky] = lucky
whosLeft n' soldiers = n' `seq` left `seq` whosLeft (n'-1) left
where left = take (n'-1) $ drop m $ cycle soldiers
Я просеял через статьи и посты, связанные с производительностью, но мне просто не кажется, что это подсказка. Все еще будучи новичком на Haskell, я, должно быть, упускаю что-то большое ... Как этот один добавленный параметр (предварительно разжеванные вычисления ...) может так сильно снизить скорость?
PS: Я знаю, что если бы Иосиф действительно имел 3000 солдат, им бы не потребовалось самоубийство ...