使用 Haskell 查找 LCS 的性能问题

Question

这是一个经典的编程问题https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

JS 实现通过了所有测试，但 Haskell 实现消耗过多内存并被杀死。

我做错了什么？

-- TOP TO BOTTOM
commonChild s1 s2 = L.foldl g l1 l ! n
    where
    n  = length s1
    l1 = arr $ replicate (n + 1) 0
    l  = [ [(x,i,y,j) | (y,j) <- zip s2 [1..]] 
           | (x,i) <- zip s1 [1..]]
    g a = L.foldl (\a' (x,i,y,j) -> let x' = if x == y
                                             then 1 + a ! (j - 1) 
                                             else max (a ! j) (a' ! (j - 1)) 
                                    in a' // [(j,x')]) 
                  l1

arr l = array (0,length l-1) $ zip [0..] l

function lcs(a,b) {
  let n = a.length
  let a1 = []
  for (let i = 0; i <= n; i++) {
    a1.push(0)
  }
  for (let i = 0; i < b.length; i++) {
    let a2 = [0]
    for (let j = 0; j < n; j++) {
      let x = b[i] == a[j] ? 1 + a1[j] : Math.max(a1[j+1],a2[j])
      a2.push(x)
    }
    a1 = a2
  }
  return a1[n]
}

console.log(lcs("SHINCHAN","NOHARAAA"))

https://repl.it/@leonbobster/LCS#main.hs

https://www.hackerrank.com/challenges/common-child/problem

Answer 1

您使用 Data.Array 中的 // 确实会降低您的性能。如果你阅读 the docs ，它说它“构造一个与第一个参数相同的数组，除了它已被正确参数中的关联更新”，这意味着每次调用它时，您都在构造一个全新的数组。这与您的 js 实现非常不同，后者只是附加。

您可能认为数组是获得性能提升的明显选择，但这是常规旧列表就可以正常工作的时候之一。与其在折叠的每次迭代中生成一个新数组，每个迭代都在前一个元素之上添加一个新元素，不如直接将 cons 放入列表中。考虑以下子函数 g 的定义:

g a = arr . reverse . L.foldl (inner a) [0]
inner a a'@(z:_) (x,i,y,j) =
  let x' = if x == y
            then 1 + a ! (j - 1)
            else max (a ! j) z
  in x':a'

---

注意:我上面所做的更改都是关于选择更好的数据结构，但请参阅@chi 的回答以了解更多提高性能的方法，这些方法与协商惰性/严格性和特定于 GHC 的行为有关东西。