3 
positions2              :: (Eq a) => a -> [a] -> [Int]
positions2              = f where
    f aa aas        = filter (g aa aas) [0 .. (length aas - 1)]
    g aa aas it     = aa == aas !! it

此代码用于找出给定列表中给定元素的位置。

为了找出它的复杂性，我想到了filter一个函数 isg和一个 list [0..length-1]。

现在，我不知道positions2会是什么复杂性，(n)或者由于filter功能会发生任何循环。

请建议是否有任何其他方法可以编写更紧凑的代码以降低复杂性。

4

3 回答 3

9
  • 过滤器具有O(n)复杂度。
  • [0..x] 具有O(n)复杂度。
  • (!!)具有O(n)复杂度。

由于嵌套(!!) ，您的幼稚实现是二次的

列表在这里是惰性的，因此过滤器和列表生成器结合了O(n)复杂度加上每个元素的一些常数（由于惰性，列表的生成和过滤一次有效地发生）。

即在惰性列表中生成和过滤的工作是(O(n+n*k)) ，而不是严格列表中的O(2*n) ，其中k是生成单个 cons 单元格的成本。

但是，您对线性索引的使用无论如何都会使这个二次方。我注意到，在具有融合的严格向量上，这将是O(n+n*j)（线性），由于恒定的j查找复杂性，或者使用对数结构化查找O(n+n*log n)。

于 2014-10-06T10:18:14.433 回答
5

线性复杂度

positions2 :: Eq a => a -> [a] -> [Int]
positions2 x = map fst . filter ((x==).snd) . zip [0..]

main = print $ positions2 3 [1,2,3,4,1,3,4]

（我建议您阅读并了解其工作原理）

（您的代码需要二次时间，因为(!!)需要线性时间）

于 2014-10-06T09:35:18.523 回答
1

First, few transformations:

positions2              :: (Eq a) => a -> [a] -> [Int]
positions2              = f where
    f aa aas        = filter (g aa aas) [0 .. (length aas - 1)]
    g aa aas it     = aa == aas !! it
-- ==
positions2 aa aas  = filter (g aa aas) [0 .. (length aas - 1)]
    g aa aas it     = aa == aas !! it
-- ==
positions2 aa aas  = [it | it <- [0 .. (length aas - 1)], aa == (aas !! it)]
{- 
positions2 aa aas = for each it in [0 .. (length aas - 1)]
                      if (aas !! it) == aa
                        emit it
-}

Now you can clearly see that for a given it the traversal of the list aas is repeated anew, from its very start, by (!!). This is a classic quadratic behaviour, you perform 1+2+3+4+...+n = O(n2) steps by the time the results of positions2 aa aas are explored in full (the returned list is traversed to its very end).

But you explore progressively increasing indices, so you could as well start from the previous point along the list (and not from its start), and only advance by 1 position each time (and not by full it indices, as (!!) is doing):

positions2 aa aas = g 0 aas
   where
      g i (a:as) | a == aa = i : g (i+1) as
                 | otherwise =   g (i+1) as
      g _ [] = []

Here you can see how the incrementing of the index by 1 (i --> i+1) is weaved together with the advancement along the list by one position ((a:as) --> as).

With list comprehensions again, the weaving (or actually, more like zipping) is achieved by using zip:

positions2 aa aas = [it | (a,it) <- zip aas [0 .. (length aas - 1)]
                        , a == aa]
{-
    = for each a in aas while incrementing it by 1 from 0 to (length aas - 1),
        if a == aa
          emit it
-}

This is clearly and visibly an O(n) solution now. And because Haskell's lists are lazy and zip stops when the shortest list ends,

positions2 aa aas = [it | (a,it) <- zip aas [0 ..], a == aa]

(which is equivalent to the code in this answer here).

于 2014-10-07T08:11:38.773 回答