3

假设一个人想对一组组合进行某种比较，例如：

combs []     r = [r]
combs (x:xs) r = combs xs (x:r) ++ combs xs r

answer = minimumBy (\a b -> compare (length . compress $ a) 
                                    (length . compress $ b)) list 

  where compress = 
           ...something complicated involving values external to the list.


*Main> combs "ABCD" [] --Imagine a larger list of larger combinations.
["DCBA","CBA","DBA","BA","DCA","CA","DA","A",
 "DCB","CB","DB","B","DC","C","D",""]

（实际的列表将是一个更复杂的字符串组合构造，但同样徒劳无功，并且任何列表x都不会提供对总组合是否充分的洞察力）

如果列表变得非常大，在我们构造和丢弃不充分的组合时以某种方式更新一个结果，而不是在代表整个列表的值上调用比较会更有效吗？

例如，（伪）

loop = do c <- nextComb
       if c > r then c else r
       loop

在 Haskell 中如何做到这一点？或者 Haskell 的编译器会answer通过自动丢弃列表的元素来优化值吗？或者我可能会错过的其他东西？

4

2 回答 2

3

在您的示例中，不会丢弃不适当的组合，因为会map sum强制对它们进行全面评估。但是，如果比较函数只需要组合的浅层 repr，那么 Haskell 懒惰没有理由不工作：

-- many combinations are evaluated only "of 1 elem depth"
answer = maximum . combs [1..4] $ []

想想启发式方法，它可以帮助您减少枚举：

combs (x:xs) r
    | x > 0     = combs xs (x:r) ++ combs xs r
    | otherwise = combs xs r

保留一些关于丢弃元素的信息可能对它有用：

-- or combs discarded (x:xs) r = ...
combs least (x:xs) r
    | x < least  = combs x xs r
    | x == least = ...
    | otherwise  = ...

还有一个想法 - 累积多个结果列表：

combs (x:xs) negatives positives
    | x < 0     = (nns ++ ns, ps)
    | otherwise = (ns, pps ++ ps)
  where
    (ns, ps) = combs xs negatives positives
    (nns, _) = combs xs (x:negatives) positives
    (_, pps) = combs xs negatives (x:positives)

您可以在 Richard Bird的“Pearls of Functional Algorithm Design”一书中找到很多关于优化这种置换指数算法的想法。

然而，在现实世界中使用惰性 Haskell 列表结构很容易成为瓶颈。考虑使用更有效的结构，例如包中的Seq。containers

于 2013-06-07T14:24:32.680 回答
0

如果compress函数是严格离线的（在绝对不可预测的意义上，在构造整个组合之前不能对结果做出任何假设）并且源字符串的长度小于或等于 64（我怀疑它是，无法想象 >运行时 2^64 个 Haskell 列表 :) 以下“非 Haskell 方式”解决方案确实有助于减少内存占用：

import Data.Bits

-- see http://programmers.stackexchange.com/a/67087/44026
gosper :: Int64 -> Int64
gosper set = ...


answer source = go 1 0 (key 0)
  where
    go set r rV
        | set > limit = r
        | sV > rV     = go (gosper set) set sV
        | otherwise   = go (gosper set) r rV
      where
        sV = key set
    key = length . compress . comb
    comb set = [ch | (ch, i) <- (zip source [1..len]), testBit set i]
    limit = 2 ^ len - 1
    len = length source

否则（compress根据部分输入可预测），请参阅我的第一个答案并考虑启发式...

于 2013-06-07T19:22:07.750 回答