haskell - 可以用Haskell合理解决大DP问题吗

Question

我编写了使用 Smith-Waterman 算法解决局部对齐问题的代码。

我想通过输入长度为 10000 的字符串、合理的内存(低于 2GB ram)和合理的时间(低于 5 分钟)来做到这一点。

起初，我为此使用了 bio 库的内置函数，它运行速度太慢，在我杀死它之前吃掉了 4GB 的内存。

注意java程序jAligner，它实现了同样的算法，可以用不到1GB的内存和不到20秒的时间解决这个问题。

当我写了一个未装箱的版本时，程序给了我 <<loop>> .我认为这是因为数组需要在完全构建数组之前访问数组中的项目。

所以我想知道是否有可能为这种更大的动态编程问题编写具有类似性能的 Haskell 代码。

module LocalAlign where
--import Data.Array.Unboxed
import Data.Tuple
import Data.Array


localAffineAlignment :: (Char -> Char -> Int)
                                    -> Int
                                    -> Int
                                    -> String
                                    -> String
                                    -> (Int, (String, String, String, String))
localAffineAlignment f g e s' t' = (score, best) where
    n = length s'
    m = length t'
    s= array (0,n-1) $ zip [0..n-1] s'
    t= array (0,m-1) $ zip [0..m-1] t'
    table :: (Array (Int,Int) Int,Array (Int,Int) Int)
    table   = (c,d)
      where --a :: UArray (Int,Int) Int
          a = array ((0,0),(n,m)) [((x,y),a' x y)|x<-[0..n],y<-[0..m]] --s end with gap
          b = array ((0,0),(n,m)) [((x,y),b' x y)|x<-[0..n],y<-[0..m]] --t end with gap
          c = array ((0,0),(n,m)) [((x,y),fst (c' x y))|x<-[0..n],y<-[0..m]] -- best 
          d = array ((0,0),(n,m)) [((x,y),snd (c' x y))|x<-[0..n],y<-[0..m]] -- direction
          a' i j
            | i==0 || j==0  = inf
            | otherwise     = max (a!(i-1,j)-e) (c!(i-1,j)-g-e)
          b' i j
            | i==0 || j==0  = inf
            | otherwise     = max (b!(i,j-1)-e) (c!(i,j-1)-g-e)
          c' i j
            | min i j == 0  = (0,0)
            | otherwise     = maximum [(b!(i,j),3),(a!(i,j),2),(c!(i-1,j-1) + f u v,1),(0,0)]
            where u = s!(i-1)
                  v = t!(j-1)
          inf = -1073741824
    score :: Int
    score = maximum $ elems $ fst table
    best :: (String, String, String, String)
    best = (drop si $ take ei s',drop sj $ take ej t',b1,b2)
      where (a,d') = table
            (si,sj,b1,b2) = build ei ej [] []
            (ei,ej) = snd $ maximum $ map swap $ assocs a
            build x y ss tt
             | o == 0       = (x,y,ss,tt)
             | d == 1       = build (x-1) (y-1) (u:ss) (v:tt) 
             | d == 2       = build (x-1) y     (u:ss) ('-':tt) 
             | otherwise    = build x (y-1)     ('-':ss) (v:tt) 
             where o = a!(x,y)
                   d = d'!(x,y)
                   u = s!(x-1)
                   v = t!(y-1)

Answer 1

is it even possible to write Haskell code with similar performance for this kind of larger dynamic programming problems.

是的当然。使用相同的数据结构和相同的算法，您将获得相同(或更好，或更差，因常数因素)的性能。

您正在大量使用(中间)列表和盒装数组。考虑改用 vector 包。