Haskell动态规划代码为何运行飞快？求代码优化建议

为什么代码未手动Memo却运行快速？ #

Haskell不会默认自动为递归函数做Memoization，你的代码运行快的原因大概率不是语言层面的自动优化，而是以下几点：

• 测试用例规模较小：如果测试的买家数量不多，哪怕是指数级复杂度的代码也能快速执行。比如当买家列表长度n很小时，即使每个步骤遍历O(k)个定价（k为当前买家的出价范围），总计算量也不大。
• 实际状态空间被自然剪枝：代码中只有当当前买家出价a > p时，才会遍历[p..a]的所有可能定价；当a <= p时直接递归处理剩余买家，没有分支。如果测试用例中大部分买家的出价不大于当前最低定价，递归分支会非常少。
• 惰性求值的隐性优化：Haskell的惰性求值可能避免了一些不必要的计算，但你的代码中l需要计算所有pc对应的maxP结果，所以这个影响相对有限，核心还是前两点。

Haskell风格优化建议 #

1. 用模式匹配替代head/tail #

head和tail是部分函数，遇到空列表会崩溃，且不符合Haskell惯用写法。直接用模式匹配解构列表更安全清晰：

maxP :: Int -> [Int] -> (Int, Int)
maxP p [] = (0, p)
maxP p (currentBid:rest)
  | currentBid < p  = (fst (maxP p rest), p)
  | currentBid == p = (p + fst (maxP p rest), p)
  | otherwise       = (maximum l, p + argmax l)
  where
    possiblePrices = [p .. currentBid]
    l = zipWith (+) possiblePrices $ map (fst . flip maxP rest) possiblePrices

2. 简化argmax函数 #

手动递归实现argmax过于繁琐，用标准库函数可以一行搞定，可读性和安全性更高：

argmax :: [Int] -> Int
argmax xs = snd $ maximum $ zip xs [0..]

这里zip xs [0..]将每个元素与索引配对，maximum按元素值取最大项，snd取出对应的索引。

3. 手动添加Memoization（针对大规模用例） #

如果要处理更大的买家列表，必须手动缓存maxP的结果以避免重复计算。可以用Data.MemoTrie库的memo2函数（需先安装memo-trie包）：

import Data.MemoTrie (memo2)

maxP :: Int -> [Int] -> (Int, Int)
maxP = memo2 maxP'
  where
    maxP' p [] = (0, p)
    maxP' p (currentBid:rest)
      | currentBid < p  = (fst (maxP p rest), p)
      | currentBid == p = (p + fst (maxP p rest), p)
      | otherwise       = (maximum l, p + argmax l)
      where
        possiblePrices = [p .. currentBid]
        l = zipWith (+) possiblePrices $ map (fst . flip maxP rest) possiblePrices

若不想用第三方库，也可以用Data.Map手动维护缓存，但实现稍繁琐。

4. 优化maxPI函数，避免reverse #

当前maxPI通过累加列表再reverse生成结果，改成直接递归构建正向列表更简洁：

maxPI :: Int -> [Int] -> [Int]
maxPI _ [] = []
maxPI p (bid:rest) = q : maxPI q rest
  where (_, q) = maxP p (bid:rest)

5. 调整参数顺序，提升可读性 #

把买家列表作为maxP的第一个参数，避免flip的使用，调用时更符合直觉：

maxP :: [Int] -> Int -> (Int, Int)
maxP = memo2 maxP'
  where
    maxP' [] p = (0, p)
    maxP' (currentBid:rest) p
      | currentBid < p  = (fst (maxP rest p), p)
      | currentBid == p = (p + fst (maxP rest p), p)
      | otherwise       = (maximum l, p + argmax l)
      where
        possiblePrices = [p .. currentBid]
        l = zipWith (+) possiblePrices $ map (fst . maxP rest) possiblePrices

对应的maxPI也可调整为：

maxPI :: Int -> [Int] -> [Int]
maxPI _ [] = []
maxPI p bidders = q : maxPI q (tail bidders)
  where (_, q) = maxP bidders p

6. 使用描述性变量名 #

将模糊的变量名（如q、a）改为有意义的名字，比如bidders、currentBid、possiblePrices，提升代码可读性。

内容的提问来源于stack exchange，提问作者Grigoris L.