7

を計算する必要がありますがfoo n = maximumBy (comparing p) [1..n]、p :: Int -> Int遅いです。しかし、私はそれp n < nをすべて知っておりn > 0、この事実を使用してこの計算を次のように高速化したいと考えています。現在の最大値を記憶して、から始めて計算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
を覚えておくことができ、他の再帰呼び出しでは、より良い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

OK、それで私がこれに私の脳を正しく包んだかどうか見てみましょう...あなたはp n < nすべての興味深いことについてそれを言っていますn。そして、これまでに見られた最大値よりも小さくなるまで、を計算p xしたいですか？x = n to 1xp 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 に答える