Анализ сложности в Haskell

Question

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, используя функцию g и список [0..length-1].

Теперь, я не могу понять, какая сложность positions2 будет (n) или будет какая-либо петля в связи с функцией filter.

Просьба предложить, если есть какой-либо другой способ написать более компактный код для более низкой сложности, чем этот.

Answer 1

Линейная сложность

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] 

(я предлагаю вам прочитать и понять, как именно работает)

(код взять квадратичное время, так как (!!) взять линейное время)

Answer 2

• фильтр имеет O (n) сложность.
• [0..x] имеет O (n) сложность.
• (!!) имеет O (n) сложность.

Ваша наивная реализация является квадратной благодаря вложенному (!!)

Списков ленивы здесь, поэтому генератор фильтров и списка совместил О (п) сложности плюс некоторой константы для каждого элемента (с лень, генерация списка и фильтрация происходят за один проход, эффективно).

Т.е. работа по генерации и фильтрации является (О (п + п * к)) на ленивых списков, а не О (2 * N) в строгом списке, где к является стоимость генерации единственная ячейка cons.

Однако использование линейной индексации в любом случае делает это квадратичным. Я отмечаю, что на строгих векторах слиянием это будет O (n + n * j) (линейный) из-за постоянной j сложность поиска или с помощью структурированного поиска в журналах, O (n + n * log n).

Answer 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 
-- == 
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 
-} 

Теперь вы можете ясно видеть, что для данного it обхода списка aas повторяется заново , с самого своего начала, по (!!). Это классическое квадратичное поведение, вы выполняете 1 + 2 + 3 + 4 + ... + n = O (n) шагов к тому времени, когда результаты positions2 aa aas будут изучены полностью (возвращенный список пройден до самого конца).

Но вы исследуете постепенно увеличивая показатели, так что вы могли бы также начать с предыдущей точки по списку (и не с начала его), и только вперед на 1 позицию каждый раз, когда (а не полным it показателей, а (!!) делает):

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

Здесь вы можете увидеть, как инкрементацию индекса на 1 (i --> i+1) соткана вместе с продвижением по списку на одну позицию ((a:as) --> as).

С списковых снова, ткачество (или на самом деле, больше как сжать) достигается за счет использования 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 
-} 

Это явно и заметно (п) раствор вывода Теперь. И потому, что списки в Haskell ленивые и zip останавливается, когда самый короткий список заканчивается,

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

(который эквивалентен коду в this answer here).