4

次の (最適ではない) コードは、特定のサブセットに対してサイズ N のすべてのサブセットを生成します。

このコードは機能しますが、前述のとおり、非常に最適ではありません。中間リストを使用して Set.insert の O(log(n)) を回避することは、後でリストを Set に再変換するコストが大きいため、役に立たないようです。

コードを最適化する方法を提案できる人はいますか?

import qualified Data.Set as Set


subsetsOfSizeN :: Ord a => Int -> Set.Set a -> Set.Set (Set.Set a)
subsetsOfSizeN n s
  | Set.size s < n || n < 0 = error "subsetOfSizeN: wrong parameters"
  | otherwise = doSubsetsOfSizeN n s
 where doSubsetsOfSizeN n s
        | n == 0 = Set.singleton Set.empty
        | Set.size s == n = Set.singleton s
        | otherwise =
           case Set.minView s of
             Nothing -> Set.empty
             Just (firstS, restS) ->
               let partialN n = doSubsetsOfSizeN n restS in
               Set.map (Set.insert firstS) (partialN (n-1)) `Set.union` partialN n
4

5 に答える 5

14

これは、パスカルの三角形に触発されています。

choose :: [b] -> Int -> [[b]]
_      `choose` 0       = [[]]
[]     `choose` _       =  []
(x:xs) `choose` k       =  (x:) `fmap` (xs `choose` (k-1)) ++ xs `choose` k
于 2013-01-11T20:24:52.403 に答える
7

このコードは機能しますが、私が言ったように、非常に最適ではありません。

私にはそれほどひどくはないようです。kサイズのセットのサイズのサブセットの数は、に対してnかなりn `choose` k速く増加しk ~ n/2ます。したがって、すべてのサブセットを作成することは、適切にスケーリングする必要があります。

中間リストを使用してのを回避することはO(log(n))、Set.insert後でリストをセットに再変換するための多大なコストのため、役に立たないようです。

うーん、パフォーマンスを向上させるためにリストを使用していることがわかりました。漸近的ではないと思いますが、多かれ少なかれ一定の要因は無視できません。

しかし、最初に、修復が簡単なコードの非効率性があります。

Set.map (Set.insert firstS) (partialN (n-1))

Set.mapツリーを最初から再構築する必要があることに注意してください。firstSしかし、それはのどのセットのどの要素よりも常に小さいことがわかっているpartialN (n-1)ので、セットSet.mapMonotonicのスパインを再利用できるものを使用できます。

そして、その原則はリストを魅力的なものにするものでもあり、サブセットは辞書式順序で生成されるためSet.fromList、より効率的なを使用する代わりにを使用できますSet.fromDistinctAscList。アルゴリズムを転記すると、

onlyLists :: Ord a => Int -> Set.Set a -> Set.Set (Set.Set a)
onlyLists n s
    | n == 0                    = Set.singleton Set.empty
    | Set.size s < n || n < 0   = error "onlyLists: out of range n"
    | Set.size s == n           = Set.singleton s
    | otherwise                 = Set.fromDistinctAscList . map Set.fromDistinctAscList $
                                                         go n (Set.size s) (Set.toList s)
      where
        go 1 _ xs = map return xs
        go k l (x:xs)
            | k == l = [x:xs]
            | otherwise = map (x:) (go (k-1) (l-1) xs) ++ go k (l-1) xs

私が実行したいくつかのベンチマークでは、sを使用して修正されたアルゴリズムよりも1.5〜2倍高速ですSet。

そしてそれは、私の基準ベンチマークでは、dave4420のほぼ2倍の速さです。

于 2013-01-10T23:16:01.060 に答える
1 
subsets :: Int -> [a] -> [[a]]
subsets 0 _ = [[]]
subsets _ [] = []
subsets k (x:xs) = map (x:) (subsets (k - 1) xs) ++ subsets k xs
于 2015-01-07T13:15:46.503 に答える
0

私はこれを見つけました、それはあなたを助けることができるかもしれません

f []  = [[1]]
f l   = (:) [u] l'
    where 
        u  = succ (head (head l))
        l' = (++) l (map(\x->(:) u x) l)

fix f n = if (n==0) then [] else f (fix f (n-1))

それをテストするには

$ length $ (fix f 10) => 1023 -- The empty set is always include then == 1024
于 2013-01-10T23:15:07.673 に答える
0

まず、より優れたアルゴリズムを使用します。

最終行を見てください：

           Set.map (Set.insert firstS) (partialN (n-1)) `Set.union` partialN n

評価には2 回doSubsetsOfSizeN k (Set.fromList $ 1:2:xs)の評価が含まれます( を挿入するときに1 回、 を挿入するときに 1 回)。この重複は無駄です。doSubsetsOfSizeN (k-1) (Set.fromList xs) 12

より良いアルゴリズムを入力してください。

mine :: Ord a => Int -> Set.Set a -> Set.Set (Set.Set a)
mine n s | Set.size s < n || n < 0 = Set.empty
         | otherwise               = Set.foldr cons nil s !! n
    where
        nil :: Ord a => [Set.Set (Set.Set a)]
        nil = Set.singleton Set.empty : repeat Set.empty
        cons :: Ord a => a -> [Set.Set (Set.Set a)] -> [Set.Set (Set.Set a)]
        cons x sets = zipWith Set.union sets
                               (Set.empty : map (Set.map $ Set.insert x) sets)

mine 9 (Data.Set.fromList [0..18]) `seq` ()よりも高速でsubsetsOfSizeN 9 (Data.Set.fromList [0..18]) `seq` ()あり、漸近的なパフォーマンスが向上するはずです。

これ以上の最適化は試みていません。もっと良いアルゴリズムがまだあるかもしれません。

insert(とのコストfromListが問題である場合は、セットのセットではなく、リストのリストを返すことを検討する必要があります。)

于 2013-01-10T22:53:47.617 に答える