Как написать эффективные алгоритмы динамического программирования в Haskell?

Question

Я играл с динамическим программированием в Haskell. Практически каждый учебник, который я видел по этому вопросу, дает тот же, очень элегантный алгоритм, основанный на memoization и лень типа 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 секунды для вычисления pascal 1000, что примерно в 160 раз медленнее, чем эквивалентная неоптимизированная программа на C++. И разрыв только расширяется с большими входами.

Похоже, я пробовал все возможные перестановки вышеприведенного кода вместе с предложенными альтернативами, такими как библиотека данных-воспоминаний, и все они имели одинаковую или худшую производительность. Единственное, что я не пробовал, это ST Monad, и я уверен, что можно было запустить программу только медленнее, чем версия C. Но я действительно хотел бы написать его в идиоматическом Haskell, и я не понимаю, почему идиоматическая версия настолько неэффективна. У меня есть два вопроса:

1. Почему этот код так неэффективен? Это кажется простой итерацией через матрицу с арифметической операцией в каждой записи. Ясно, что Хаскелл делает что-то за кулисами, которые я не понимаю.

2. Есть ли способ сделать его намного более эффективным (не более 10-15 раз времени выполнения программы на C), не жертвуя своей безгосударственной рекурсивной формулировкой (по сравнению с реализацией с использованием изменяемых массивов в ST Монада)?

Большое спасибо.

Edit: Модуль массива используется стандартный Data.Array

Answer 1

Ну, алгоритм может быть разработана немного лучше , Используя vector пакет и быть умным о только держа одну строку в памяти, в то время, мы можем получить то, что это идиоматическое иначе:

{-# LANGUAGE BangPatterns #-} 
import Data.Vector.Unboxed 
import Prelude hiding (replicate, tail, scanl) 

pascal :: Int -> Int 
pascal !n = go 1 ((replicate (n+1) 1) :: Vector Int) where 
    go !i !prevRow 
    | i <= n = go (i+1) (scanl f 1 (tail prevRow)) 
    | otherwise = prevRow ! n 
    f x y = (x + y) `rem` 1000000 

Это оптимизирует вниз очень плотно, особенно потому, что vector пакет включает в себя некоторые довольно изобретательные трюки, чтобы прозрачно оптимизировать операции массива, написанные в идиоматическом стиле.

Answer 2

1 Почему приведенный выше код так неэффективно? Это кажется простой итерацией через матрицу с арифметической операцией в каждой записи. Ясно, что Хаскелл делает что-то за кулисами, которые я не понимаю.

Проблема в том, что код записывает thunks в массив. Затем, когда считывается запись (n,n), оценка thunks снова перескакивает по всему массиву, повторяясь до тех пор, пока не будет найдено значение, не требующее дальнейшей рекурсии. Это вызывает много ненужного распределения и неэффективности.

Код C++ не имеет этой проблемы, значения записываются и считываются напрямую, без дополнительной оценки. Как это было бы с STUArray. Есть

p = runSTUArray $ do 
    arr <- newArray ((0,0),(n,n)) 1 
    forM_ [1 .. n] $ \i -> 
     forM_ [1 .. n] $ \j -> do 
      a <- readArray arr (i,j-1) 
      b <- readArray arr (i-1,j) 
      writeArray arr (i,j) $! (a+b) `rem` 1000000 
    return arr 

действительно выглядит так плохо?

2 Есть ли способ сделать это гораздо более эффективным (в большинстве 10-15 раз во время выполнения программы C), не жертвуя его без гражданства, рекурсивной формулировки (визави реализацию с использованием изменяемых массивов в ST Monad)?

Я не знаю ни одного. Но может быть.

Добавление:

После того, как один использует STUArray с или Unboxed Vector с, есть еще значительная разница в эквивалентной реализации C. Причина в том, что gcc заменяет % комбинацией умножений, сдвигов и вычитаний (даже без оптимизаций), поскольку модуль известен. Проделав то же самое вручную в Haskell (поскольку GHC не [еще] сделать это),

-- fast modulo 1000000 
-- for nonnegative Ints < 2^31 
-- requires 64-bit Ints 
fastMod :: Int -> Int 
fastMod n = n - 1000000*((n*1125899907) `shiftR` 50) 

получает версии Haskell на одном уровне с C.

Answer 3

Трюк состоит в том, чтобы подумать о том, как написать весь проклятый алгоритм сразу, а затем использовать нераспознанные векторы в качестве вашего типа данных поддержки. Например, работает следующая примерно в 20 раз быстрее, на моей машине, чем ваш код:

import qualified Data.Vector.Unboxed as V 

combine :: Int -> Int -> Int 
combine x y = (x+y) `mod` 1000000 

pascal n = V.last $ go n where 
    go 0 = V.replicate (n+1) 1 
    go m = V.scanl1 combine (go (m-1)) 

тогда я написал две main функции, названной к твоему и моему с аргументом 4000; они выполнялись в 10.42s и 0.54s соответственно. Конечно, как я уверен, вы знаете, они оба получают взорваны из воды (0.00s) версия, которая использует улучшенный алгоритм:

pascal' :: Integer -> Integer 
pascal :: Int -> Int 
pascal' n = product [n+1..n*2] `div` product [2..n] 
pascal = fromIntegral . (`mod` 1000000) . pascal' . fromIntegral