CODEWITHSUNDEEP
haskellcode-complexity
anujuhi01
anujuhi01

Reputation: 71

Complexity Analysis in Haskell

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

This code is to find out positions of a given element in the given list.

To find out the complexity of it, I thought of filter taking a function that is g and a list [0..length-1].

Now, I can't figure out what complexity of positions2 would be (n) or would there be any loop going on due to filter function.

Please suggest if there is any other method to write a more compact code for lower complexity than this.

Upvotes: 3

Views: 2150

Answers (3)

Will Ness
Will Ness

Reputation: 71065

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).

Upvotes: 1

Don Stewart
Don Stewart

Reputation: 137947

  • filter has O(n) complexity.
  • [0..x] has O(n) complexity.
  • (!!) has O(n) complexity.

Your naive implementation is quadratic due to the nested (!!)

Lists are lazy here, so the filter and list generator have combined O(n) complexity plus some constant per element (with laziness, generation of the list and filtering happen in one pass, effectively).

I.e work on generation and filtering is (O(n+n*k)) on lazy lists, rather than O(2*n) in a strict list, where k is cost of generating a single cons cell.

However, your use of linear indexing makes this quadratic anyway. I note that on strict vectors with fusion this would be O(n+n*j) (linear) due to constant j lookup complexity, or with a log structured lookup, O(n+n*log n).

Upvotes: 9

josejuan
josejuan

Reputation: 9566

Linear complexity

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]

(I suggest to you read and understand how exactly works)

(your code take quadratic time since (!!) take linear time)

Upvotes: 5

Related Questions