Я играл с динамическим программированием в Haskell. Практически каждый учебник, который я видел по этому вопросу, дает тот же, очень элегантный алгоритм, основанный на memoization и лень типа Array. Вдохновленный этими примерами, я написал в качестве теста следующий алгоритм:
-- pascal n returns the nth entry on the main diagonal of pascal 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 секунды для вычисления pascal 1000
, что примерно в 160 раз медленнее, чем эквивалентная неоптимизированная программа на С++. И разрыв только расширяется с большими входами.
Кажется, я пробовал все возможные перестановки вышеприведенного кода вместе с предложенными альтернативами, такими как библиотека данных-воспоминаний, и все они имели одинаковую или худшую производительность. Единственное, что я не пробовал, это ST Monad, и я уверен, что можно было запустить программу только медленнее, чем версия C. Но я действительно хотел бы написать его в идиоматическом Haskell, и я не понимаю, почему идиоматическая версия настолько неэффективна. У меня есть два вопроса:
-
Почему приведенный выше код настолько неэффективен? Это кажется простой итерацией через матрицу с арифметической операцией в каждой записи. Ясно, что Хаскелл делает что-то за кулисами, которые я не понимаю.
-
Есть ли способ сделать его намного более эффективным (не более 10-15 раз времени выполнения программы C), не жертвуя своей безрепортивной рекурсивной формулировкой (по сравнению с реализацией с использованием изменяемых массивов в ST Monad)?
Большое спасибо.
Изменить: используемый модуль массива - это стандартный Data.Array