使用Haskell查找LCS的性能问题
这是一个经典的编程问题 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
回答
你对//from 的使用Data.Array真的会扼杀你的表现。如果您阅读文档，它会说“构造一个与第一个参数相同的数组，只是它已被正确参数中的关联更新”，这意味着每次调用它时，您都在构建一个全新的数组. 这与您的 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 的事情有关。