Как написать эффективные алгоритмы динамического программирования на Haskell?
Я экспериментировал с динамическим программированием на Haskell. Практически каждый учебник, который я видел по этому вопросу, дает один и тот же очень элегантный алгоритм, основанный на запоминании и ленивости типа Array. Вдохновленный этими примерами, я написал следующий алгоритм в качестве теста:
-- pascal n returns the nth entry on the main diagonal of pascal's triangle
-- (mod a million for efficiency)
pascal :: Int -> Int
pascal n = p ! (n,n) where
p = listArray ((0,0),(n,n)) [f (i,j) | i <- [0 .. n], j <- [0 .. n]]
f :: (Int,Int) -> Int
f (_,0) = 1
f (0,_) = 1
f (i,j) = (p ! (i, j-1) + p ! (i-1, j)) `mod` 1000000
Моя единственная проблема — эффективность. Даже используя GHC -O2, эта программа занимает 1,6 секунды для вычисления паскалей 1000, что примерно в 160 раз медленнее, чем эквивалентная неоптимизированная программа на C++. И разрыв только увеличивается с большими входами.
Похоже, что я перепробовал все возможные перестановки приведенного выше кода, а также предложенные альтернативы, такие как библиотека data-memocombinators, и все они имели одинаковую или худшую производительность. Единственная вещь, которую я не пробовал, - это ST Monad, которую, я уверен, можно заставить работать программу лишь немного медленнее, чем C-версию. Но мне бы очень хотелось написать это на идиоматическом Haskell, и я не понимаю, почему идиоматическая версия настолько неэффективна. У меня два вопроса:
Почему приведенный выше код настолько неэффективен? Это похоже на простую итерацию по матрице с арифметической операцией для каждой записи. Ясно, что Haskell делает что-то за кулисами, чего я не понимаю.
Есть ли способ сделать его намного более эффективным (максимум в 10-15 раз больше времени выполнения программы на C), не жертвуя его рекурсивной формулировкой без сохранения состояния (по сравнению с реализацией, использующей изменяемые массивы в ST Monad) ?
Большое спасибо.
Изменить: используется стандартный модуль массива Data.Array