是否可以使用Haskell来合理地解决大型DP问题

Question

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

我希望通过输入长度为10000的字符串,合理的内存(低于2GB的RAM)和合理的时间(低于5分钟)来完成此操作.

起初我正在使用生物库的内置功能,它运行速度太慢,在我杀死它之前吃了4GB的ram.

请注意,实现相同算法的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

是否有可能为这种更大的动态编程问题编写具有类似性能的Haskell代码.

当然是.使用相同的数据结构和相同的算法,您将获得相同(或更好,或更糟,通过常数因素)的性能.

您正在大量使用(中间)列表和盒装数组.请考虑使用矢量包.