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

此代码采用一个列表并将所有元素相加以获得所有元素的总和（我也对此效率感兴趣）。测试集的输出是：

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

我想找到这些列表的并集（使其成为一个集合），但我觉得：

whatIWant = foldl1 union testSet

性能会很差（真正的列表会有数千个元素）。

这是正确的解决方案还是我遗漏了一些明显的东西？

4

3 回答 3

5

你可能想试试

nub $ concat theListOfLists

在使用 的版本中union，删除重复的代码将运行多次。在这里它只运行一次。

它只会执行一次提取唯一值的代码。

还有一个 Data.Set 库，您也可以使用

import Data.Set
S.fromList $ concat theListOfLists

重要的一点是，提取重复项的代码（此处和上方）仅在完整列表上运行一次，而不是一遍又一遍地运行。

编辑- Rein 在下面提到 nub 是 O(n^2)，所以你应该避免上面的第一个解决方案，而支持 O(n log n)，因为 Data.Set.fromList 应该是。正如其他人在评论中提到的那样，您需要强制执行Ord a以获得适当的复杂性O(n log n)，而 Data.Set 可以， nub 没有。

我将保留这两种解决方案（性能差和性能好），因为我认为由此产生的讨论很有用。

于 2014-09-25T17:49:11.077 回答
5

如果您使用的是类型类成员的元素Ord，如您的示例中所示，您可以使用Data.Set：

import qualified Data.Set as Set

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

这样做的好处是占用的空间与最大子列表的大小成正比，而不是像Set.fromList . concat解决方案那样与整个串联列表的大小成正比。strictfoldl'还可以防止未评估的 thunk 的累积，从而防止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的输出——一个线性的ordNub :: (Ord a) => [a] -> [a]，具有明显的实现。

总体而言，使用 left-preferential(\(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 回答