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あなたの例では、不適切な組み合わせは完全に評価されるため、破棄されません。しかし、比較関数が組み合わせの浅い表現のみを必要とする場合、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  = ...

もう 1 つのアイデア - 結果のリストを複数蓄積する:

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 from containerspackageなど、より効率的な構造を使用することを検討してください。

于 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 に答える