0

私は次の問題に直面しています：

初期セットから、[1,2,3,4]すべての可能なサブセットを計算します。[[1],[2],[3],[4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4],[1,2,3],[1,2,4],[1,3,4],[2,3,4],[1,2,3,4]]

私generate.hsは正しい次の Haskell プログラムを書きました。

generateSets :: Eq a => [a] -> [[a]] -> [[a]] -> [[a]]
generateSets []  _  _  = []
generateSets src [] _  = let isets = growthup [] src in generateSets src iset iset
generateSets src sets rsets = if null sets' then rsets else generateSets src sets' (rsets++sets')
  where sets' = concatMap (flip growthup src) sets

growthup :: (Eq a) => [a] -> [a] -> [[a]]
growthup ps ss = map (\suf -> ps++[suf]) ss'
  where ss' = nextoccurence ps ss

nextoccurence :: (Eq a) => [a] -> [a] -> [a]
nextoccurence [] ys = ys
nextoccurence xs ys = tail ys'
  where ys' = dropWhile (/= last xs) ys

GHCインタプリタghciで実行中...

ghci> generate [1,2,3,4] [] []
ghci> [[1],[2],[3],[4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4],[1,2,3],[1,2,4],[1,3,4],[2,3,4],[1,2,3,4]]

すべてがうまくいきますが、たとえばサイズ 30 の小さなセットではプログラムに時間がかかりすぎます。

私の質問は: Haskell の怠惰、またはガベージ コレクターなどからより多くを得るためにコードを改善することは可能ですか?

私のコードは並列処理に適していますか?

返信ありがとうございます。

4

1 に答える 1

7

セットには多くのサブセットがあります。実際、n 個の要素のセットには2 n 個のサブセットがあるため、30 個の要素のセットには 10 億を超えるサブセットがあります。それらを生成するためにどの方法を使用しても、結果を反復処理するだけでも長い時間がかかります。より大きなセットの場合、宇宙の熱的死の前にそれらすべてを通過することをほとんど忘れることができます.

したがって、アルゴリズムの速度を 2 倍にしても、同時に 1 つ以上の要素のリストを処理することしかできないため、パフォーマンスに関してできることは限られています。ほとんどのアプリケーションにとって、本当の解決策は、最初からすべてのサブセットを列挙する必要がないようにすることです。

とは言っても、サブセットについて考える単純な帰納的な方法があり、これにより、適切なサブセット関数を等価比較を行うことなく簡単に定義でき、実装に関する問題のいくつかを解決できます。

基本ケースでは、空のセットには 1 つのサブセット、つまり空のセットがあります。

subsets [] = [[]]

少なくとも 1 つの要素(x:xs)を持つセットの場合、その要素を含むサブセットと含まないサブセットがあります。xを再帰的に呼び出すことで含まれていないサブセットを取得subsets xsでき、それらの先頭に追加することで残りを取得できますx。

subsets (x:xs) = subsets xs ++ map (x:) (subsets xs)

subsequencesinの定義はData.List同じ原則に基づいて機能しますが、少し最適化された方法で動作します。これにより、サブセットが異なる順序で返され、共有がより有効に利用されます。しかし、私が言ったように、長さ 30 のリストのサブセットを列挙することは、何があっても遅くなるでしょう。あなたの最善の策は、そもそもそれをしなければならないことを避けることです.

于 2012-05-12T02:16:06.733 に答える