7

我需要计算foo n = maximumBy (comparing p) [1..n]，哪里p :: Int -> Int慢。但我知道这一点p n < n，n > 0并希望使用这个事实来加速这个计算，方法如下：我从down to开始计算p x，记住当前的最大值。一旦我达到小于或等于当前最大值的值，我就知道这个最大值必须是全局最大值，我就完成了。xn1x

所以我的尝试看起来像这样：

foo n = go (0, 0) n where
    go (c, _) 1 = c
    go (c, c') !x = if c' >= x then c else go (c2, c'2) (x-1) where
        x' = p x
        (c2, c'2) = if c' >= x' then (c, c') else (x, x')

这有效，但看起来不是很地道。所以我正在寻找一个更优雅的解决方案。你有什么建议吗？

4

2 回答 2

6

您可以使用模式匹配来减少使用 if ... then ... else
另一个技巧是给变量一个数字，它可以让您记住起始案例var0并且对于其他递归调用，您可以使用nicer var
最后请注意，如果在相同形式的谓词之后返回相同的值并共享相同的环境，那么您可能可以将它们组合在一起。 

foo n0 = go (0, 0) n0
  where
    go (x, y) n
        | (n  == 1) || (y >= n) = x
        | y < (p n) = go (n, (p n)) (n-1)
        | otherwise = go (x, y) (n-1)

重写考虑到评论， 

foo n0 = go 0 0 n0
  where
    go x y n
        | (n  == 1) || (y >= n) = x
        | pn > y                = go n pn (n-1)
        | otherwise             = go x y (n-1)
          where
            pn = p n
于 2013-03-26T12:26:12.403 回答
4

好的，那么让我看看我是否正确地围绕着这个问题......你这么说很p n < n有趣n。你想计算p x,x = n to 1直到x变得小于迄今为止p x看到的最大？

好吧，看起来您可以将所有的计算p x为惰性列表。现在问题已简化为扫描此列表，直到找到所需内容。我建议takeWhile，除了我们还需要折叠列表以找到当前最大值。嗯，也许我们可以将每个值与运行最大值配对？

就像是

foo n =
  let
    ps = [ p x | x <- [n, n-1 .. 1] ]
    qs = fold (\ px' (px, maxPX) -> (px', maxPX `max` px') ) ps
  in last . takeWhile (\ (px, maxPX) -> px >= maxPX) qs

或类似的？

于 2013-03-26T11:55:03.060 回答