0

包含テストでサブセットを生成する簡単なプログラムをテストしています。たとえば、与えられた

*Main Data.List> factorsets 7
[([2],2),([2,3],1),([3],1),([5],1),([7],1)]

を呼び出しchooseP 3 (factorsets 7)て、取得したい (右から左に読む、a la cons)

[[([5],1),([3],1),([2],2)]
,[([7],1),([3],1),([2],2)]
,[([7],1),([5],1),([2],2)]
,[([7],1),([5],1),([2,3],1)]
,[([7],1),([5],1),([3],1)]]

しかし、私のプログラムは余分なものを返しています[([7],1),([5],1),([3],1)]（そして欠落しています
[([7],1),([5],1),([2],2)]）：

[[([5],1),([3],1),([2],2)]
,[([7],1),([3],1),([2],2)]
,[([7],1),([5],1),([3],1)]
,[([7],1),([5],1),([2,3],1)]
,[([7],1),([5],1),([3],1)]]

包含テストは次のとおりです。タプルのメンバーの最初の部分には、null 交差が必要です。

機能することがテストされると、各サブセットの内積sndを累積するのではなく合計することが計画されます。

以前に同様の質問をしたことがあるので、再帰が [2,3] で分岐するときに、スキップされたセクションを通過すると、2 つ目の分岐が同じ可能性を超えて実行されるため、余分な分岐が生成されると思います。それを解決する方法についての指針をいただければ幸いです。また、そのような製品の組み合わせをより効率的に列挙して合計する方法についてのアイデアを共有したい場合も、それは素晴らしいことです.

Haskell コード:

chooseP k xs = chooseP' xs [] 0 where
  chooseP' [] product count = if count == k then [product] else []
  chooseP' yys product count
    | count == k = [product]
    | null yys   = []
    | otherwise  = f ++ g
   where (y:ys) = yys
         (factorsY,numY) = y
         f = let zzs = dropWhile (\(fs,ns) -> not . and . map (null . intersect fs . fst) $ product) yys
             in if null zzs
                   then chooseP' [] product count
                   else let (z:zs) = zzs in chooseP' zs (z:product) (count + 1)
         g = if and . map (null . intersect factorsY . fst) $ product
                then chooseP' ys product count
                else chooseP' ys [] 0
4

1 に答える 1

2

あなたのコードは非常に複雑なので、最初からやり直すことをお勧めします。これが私がどのように進めるかです。

  1. 仕様を書きます。必要に応じて馬鹿げたほど非効率にしましょう。たとえば、以下で選択した仕様では、リストから要素のすべての組み合わせを構築kし、悪いものを除外します。フィルターでさえ、ばかげたほど遅くなります。

    sorted   xs = sort xs == xs
unique   xs = nub xs == xs
disjoint xs = and $ liftM2 go xs xs where
    go x1 x2 = x1 == x2 || null (intersect x1 x2)

-- check that x is valid according to all the validation functions in fs
-- (there are other fun ways to spell this, but this is particularly
-- readable and clearly correct -- just what we want from a spec)
allFuns fs x = all ($x) fs

choosePSpec k = filter good . replicateM k where
    good pairs = allFuns [unique, disjoint, sorted] (map fst pairs)

    正しいことを確認するために、プロンプトでテストできます。

    *Main> mapM_ print $ choosePSpec 3 [([2],2),([2,3],1),([3],1),([5],1),([7],1)]
[([2],2),([3],1),([5],1)]
[([2],2),([3],1),([7],1)]
[([2],2),([5],1),([7],1)]
[([2,3],1),([5],1),([7],1)]
[([3],1),([5],1),([7],1)]

    いいね。

  2. 仕様ができたので、一度に 1 つのリファクタリングで速度を改善し、常に仕様と一致することを確認できます。私が最初にやりたいことは、入力を並べ替えて「増加する方法で」物事を選択するだけで、一意性と並べ替えを保証できることに注意することです。これを行うために、指定された長さのサブシーケンスを選択する関数を定義できます。これは関数に便乗してtailsいます。これは、入力リストを分割する場所を非決定論的に選択していると考えることができます。

    subseq 0 xs = [[]]
subseq n xs = do
    x':xt <- tails xs
    xs'   <- subseq (n-1) xt
    return (x':xs')

    この関数の動作例を次に示します。

    *Main> subseq 3 [1..4]
[[1,2,3],[1,2,4],[1,3,4],[2,3,4]]

    choosePに置き換えることreplicateMで、少し速く書くことができますsubseq。ただし、入力は既にソート済みで一意であると想定していることを思い出してください。

    choosePSlow k = filter good . subseq k where
    good pairs = disjoint $ map fst pairs

    上記の特定の入力に対して実行することで、動作していることを確認できます。

    *Main> let i = [([2],2),([2,3],1),([3],1),([5],1),([7],1)]
*Main> choosePSlow 3 i == choosePSpec 3 i
True

    または、QuickCheck を使用してストレス テストを行うこともできます。もう少しコードが必要です。この状態k < 5は、仕様が絶望的に​​遅いため、大きな値がk永遠にかかるためです。

    propSlowMatchesSpec :: NonNegative Int -> OrderedList ([Int], Int) -> Property
propSlowMatchesSpec (NonNegative k) (Ordered xs)
    =   k < 5 && unique (map fst xs)
    ==> choosePSlow k xs == choosePSpec k xs

*Main> quickCheck propSlowMatchesSpec
+++ OK, passed 100 tests.

  3. 物事をより速くする機会は他にもいくつかあります。たとえば、代わりに;disjointを使用してテストを高速化できます。または、要素の選択中に素性を確保し、検索をさらに早期に切り詰めることができる場合があります。ここからどのように改善したいかは、あなたに任せますが、基本的なテクニック (愚かで遅いものから始めて、よりスマートにし、徐々にテストする) は役に立ちます。choose 2liftM2

于 2013-09-27T17:33:46.363 に答える