Haskell 中最长的非递减子序列很慢。如何改进？

Question

longest'inc'subseq seq = maximum dp
    where dp = 1 : [val n | n <- [1..length seq - 1]]
          val n = (1 +) . filter'and'get'max ((<= top) . (seq!!)) $ [0..pred n]
            where top = seq!!n
          -----
          filter'and'get'max f []     = 0
          filter'and'get'max f [x]    = if f x then dp!!x else 0
          filter'and'get'max f (x:xs) = if f x then ( if vx > vxs then vx else vxs ) else vxs
            where vx  = dp!!x
                  vxs = filter'and'get'max f xs

大约需要 1-2 秒，seq 长度 = 1000 中是立即出现的

而在python

def longest(s):
    dp = [0]*len(s)
    dp[0] = 1
    for i in range(1,len(s)):
        need = 0
        for j in range (0, i):
            if s[j] <= s[i] and dp[j] > need:
                need = dp[j]
        dp[i] = need + 1
    return max(dp)

，当seq的长度为10000时，haskell程序运行时间太长 而python在10-15秒后返回答案

我们可以提高haskell的速度吗？

Answer 1

你的核心问题是你在 Haskell 中为这个算法使用了错误的数据结构。您已将一种依赖于对序列进行 O(1) 次查找的算法（如您的 Python 代码中所示）转换为对序列进行 O(n) 次查找的算法Haskell 中的列表。

使用同类的数据结构，然后你的复杂性问题就会自行解决。在这种情况下，这意味着使用类似 Data.Vector.Unboxed 的东西来表示序列，它具有 O(1) 索引，并且通常具有较低的常量开销。

Answer 2

当输入列表为 [1..10000] 时，我只需将列表真正无意识地包装到向量中即可，只需 2.5 秒。

import qualified Data.Vector as V
import Data.Vector (Vector, (!))

main = print $ liss [0..10000]

liss :: [Int] -> Int
liss seqL = V.maximum dp
    where dp = V.fromList $ 1 : [val n | n <- [1..length seqL - 1]]
          seq = V.fromList seqL
          val n = (1 +) . filter'and'get'max ((<= top) . (seq!)) $ [0..pred n]
            where top = seq!n
          -----
          filter'and'get'max :: (Int -> Bool) -> [Int] -> Int
          filter'and'get'max f []     = 0
          filter'and'get'max f [x]    = if f x then dp!x else 0
          filter'and'get'max f (x:xs) = if f x then ( if vx > vxs then vx else vxs ) else vxs
            where vx  = dp!x
                  vxs = filter'and'get'max f xs

编译和执行：

tommd@Mavlo:Test$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 7.0.3
tommd@Mavlo:Test$ ghc -O2 so.hs
[1 of 1] Compiling Main             ( so.hs, so.o )
Linking so ...
tommd@Mavlo:Test$ time ./so
10001

real    0m2.536s
user    0m2.528s

对 filter' 和 'get'max 进行工作包装器转换似乎又节省了一秒钟。

另外，我不明白为什么你需要中间情况（filter'and'get'max f [x]），如果没有它，它不应该正常工作吗？我想如果 dp!x dp!x 这会改变结果0 。请注意，消除此操作可以节省 0.3 秒。

您提供的 python 代码大约需要 10.7 秒（添加了对 longest(range(1,10000)); 的调用）。

tommd@Mavlo:Test$ time python so.py

real    0m10.745s
user    0m10.729s