5

コード例は千の言葉に値するので、それから始めます。

testList = [1,2,2,3,4,5]
testSet = map sumMapper $ tails testList
          where sumMapper [] = []
                sumMapper (a:b) = sumMap a b
                sumMap a b = map (+ a) b

このコードはリストを取り、すべての要素を合計してそれらすべての合計を取得します (これの効率にも興味があります)。testSet の出力は次のとおりです。

[[3,3,4,5,6],[4,5,6,7],[5,6,7],[7,8],[9],[],[]]

これらのリストの和集合を見つけたい(セットにするため)が、次のように感じます:

whatIWant = foldl1 union testSet

パフォーマンスが低下します (実際のリストは数千の要素になります)。

これは正しい解決策ですか、それとも明らかな何かが欠けていますか?

4

3 に答える 3

5

例のように、型クラスのメンバーである要素を使用している場合はOrd、次を使用できますData.Set。

import qualified Data.Set as Set

whatYouWant = foldl' (Set.union . Set.fromList) Set.empty testSet

これには、ソリューションのように連結リスト全体のサイズではなく、最大のサブリストのサイズに比例してスペースを確保できるという利点がありSet.fromList . concatます。また、strictfoldl'は未評価のサンクの蓄積を防ぎ、O(n)スタックとヒープ領域の使用を防ぎます。

一般的に言えば、制約はツリーを構築できるためOrd、制約よりも効率的なアルゴリズムを可能にします。Eqこれが理由でもnubありO(n^2)ます: より効率的なアルゴリズムにOrdは、Eq.

于 2014-09-25T18:01:13.143 に答える
1

unionは連想演算 ( a+(b+c)==(a+b)+c ) であるため、ツリー型の折り畳みを使用して、時間の複雑さを対数的に有利にすることができます。

_U []     = []
_U (xs:t) = union xs (_U (pairs t))

pairs (xs:ys:t)  = union xs ys : pairs t
pairs t          = t

もちろん、Data.List.unionそれ自体は一般的にO(n 2 )testListですが、 が非減少である場合は、すべてのリストも減少し、 のordUnion代わりに線形を使用してunion、全体的に線形であり、リークしないソリューションを得ることができますスペース：

ordUnion :: (Ord a) => [a] -> [a] -> [a]
ordUnion a      []     = a
ordUnion []     b      = b
ordUnion (x:xs) (y:ys) = case compare x y of
   LT -> x : ordUnion xs  (y:ys)
   EQ -> x : ordUnion xs     ys
   GT -> y : ordUnion (x:xs) ys

すり抜ける可能性のある重複を防ぐために、_Uの出力を処理するためにもう 1 つの関数が必要ですordNub :: (Ord a) => [a] -> [a]。

左優先を使用すると、(\(x:xs) ys -> x:ordUnion xs ys)全体的にさらに生産的になります (各瞬間に入力のより小さな部分を強制します)。

g testList = ordNub . _U $ [map (+ a) b | (a:b) <- tails testList]
  where
    _U []         = []
    _U ((x:xs):t) = x : ordUnion xs (_U (pairs t))
    pairs ((x:xs):ys:t) = (x : ordUnion xs ys) : pairs t
    pairs t             = t

以下も参照してください。

于 2014-09-26T10:01:51.780 に答える