Каковы пространственные сложности inits и tails?

TL; DR

После прочтения отрывка о постоянстве в книге Окасаки Purely Functional Data Structures и изучения его иллюстративных примеров односвязных списков (именно так реализованы списки Haskell) я задумался. о космических сложностях inits и tails Data.List...

Мне кажется, что

  • пространственная сложность tails линейна по длине аргумента, и
  • пространственная сложность inits квадратична по длине аргумента,

но простой тест показывает обратное.

Обоснование

С помощью tails можно поделиться исходным списком. Вычисление tails xs состоит просто в обходе списка xs и создании нового указателя на каждый элемент этого списка; нет необходимости воссоздавать часть xs в памяти.

Напротив, поскольку каждый элемент inits xs "заканчивается по-разному", такого совместного использования быть не может, и все возможные префиксы xs должны воссоздаваться в памяти с нуля.

Ориентир

Простой тест ниже показывает, что между двумя функциями нет большой разницы в распределении памяти:

-- Main.hs

import Data.List (inits, tails)

main = do
    let intRange = [1 .. 10 ^ 4] :: [Int]
    print $ sum intRange
    print $ fInits intRange
    print $ fTails intRange

fInits :: [Int] -> Int
fInits = sum . map sum . inits

fTails :: [Int] -> Int
fTails = sum . map sum . tails

После компиляции моего файла Main.hs с помощью

ghc -prof -fprof-auto -O2 -rtsopts Main.hs

и работает

./Main +RTS -p

файл Main.prof сообщает следующее:

COST CENTRE MODULE  %time %alloc

fInits      Main     60.1   64.9
fTails      Main     39.9   35.0

Память, выделенная для fInits, и память, выделенная для fTails, имеют одинаковый порядок величины... Гм...

Что здесь происходит?

  • Верны ли мои выводы о пространственной сложности tails (линейной) и inits (квадратичной)?
  • Если да, то почему GHC выделяет примерно одинаковое количество памяти для fInits и fTails? Имеет ли к этому какое-то отношение слияние списков?
  • Или мой тест некорректен?

profiling haskell space-complexity singly-linked-list
person jub0bs    schedule 01.04.2015    source источник
comment
Мое единственное предположение: промежуточные Int не оптимизируются, поэтому fTails также выделяет для них O(n^2). Чтобы проверить это, нужно было бы посмотреть на ядро ​​​​(у меня нет ghc под рукой).   -  person    schedule 01.04.2015
comment
Вероятно, вам следует форсировать список (print $ sum intRange) перед запуском fInits или fTails.   -  person Cirdec    schedule 01.04.2015
comment
@delnan Спасибо. Я еще не привык проверять ядро, но я посмотрю на это.   -  person jub0bs    schedule 01.04.2015
comment
@Cirdec Готово. Без изменений.   -  person jub0bs    schedule 01.04.2015
comment
Для меня inits выделяет в 2500 раз больше памяти, чем хвосты.   -  person András Kovács    schedule 01.04.2015
comment
@AndrásKovács (ಠ_ರ) ? Используете ли вы тот же тест, что и я? Какую версию GHC вы используете? У меня GHC 7.10.1.   -  person jub0bs    schedule 01.04.2015
comment
@Jubobs GHC 7.10.1 здесь, но я использовал +RTS -s вместо профайлера.   -  person András Kovács    schedule 01.04.2015
comment
С Windows GHC 7.8.3 у меня есть 100.0% распределение в fInits и 91.7% времени, проведенного в fInits (+RTS -p, те же параметры компилятора).   -  person Cirdec    schedule 01.04.2015
comment
Игнорируйте мои результаты GHC 7.8.3 (и все остальные). В GHC 7.8.3 есть ошибка, из-за которой запуск выполняется очень медленно. Это было исправлено в 7.8.4.   -  person Cirdec    schedule 01.04.2015
comment
@ AndrásKovács Где вы видите разбивку по функциям в выводе ./Main +RTS -s? Что вы получите, если воспользуетесь +RTS -p?   -  person jub0bs    schedule 01.04.2015
comment
@Jubobs Я просто комментирую одно или другое при использовании +RTS -s. С RTS -p я получил результаты, похожие на ваши.   -  person András Kovács    schedule 01.04.2015
comment
@ AndrásKovács Спасибо за разъяснение. У вас есть объяснение?   -  person jub0bs    schedule 01.04.2015
comment
Ничего, кроме профилировщика, не барахлит. Я посмотрел на Ядро, и там не происходит ничего смешного; он просто вызывает inits и tails и суммирует.   -  person András Kovács    schedule 01.04.2015
comment
@ AndrásKovács Спасибо. Я просто хотел подтверждения, что что-то происходит и что я не совсем сумасшедший.   -  person jub0bs    schedule 01.04.2015

Ответы (1)


arrow_upward
2
arrow_downward

Реализация inits в Haskell Report, которая идентична или почти идентична реализациям, используемым до базовой версии 4.7.0.1 (GHC 7.8.3), ужасно медленная. В частности, приложения fmap складываются рекурсивно, поэтому форсирование последовательных элементов результата становится все медленнее и медленнее.

inits [1,2,3,4] = [] : fmap (1:) (inits [2,3,4])
 = [] : fmap (1:) ([] : fmap (2:) (inits [3,4]))
 = [] : [1] : fmap (1:) (fmap (2:) ([] : fmap (3:) (inits [4])))
....

Простейшая асимптотически оптимальная реализация, исследованная Бертрамом Фельгенгауэром, основана на применении take с последовательно увеличивающимися аргументами:

inits xs = [] : go (1 :: Int) xs where
  go !l (_:ls) = take l xs : go (l+1) ls
  go _  []     = []

Фельгенгауэр смог добиться от этого дополнительной производительности, используя приватную версию take без слияния, но это все равно было не так быстро, как могло бы быть.

Следующая очень простая реализация в большинстве случаев значительно быстрее:

inits = map reverse . scanl (flip (:)) []

В некоторых странных угловых случаях (например, map head . inits) эта простая реализация асимптотически неоптимальна. Поэтому я написал версию, используя ту же технику, но основанную на очередях банкира Криса Окасаки, которая является асимптотически оптимальной и почти такой же быстрой. Йоахим Брайтнер еще больше оптимизировал ее, в первую очередь, используя строгую scanl' вместо обычной scanl, и эта реализация попала в GHC 7.8.4. inits теперь может создать корень результата за время O(n); для форсирования всего результата требуется время O (n ^ 2), потому что ни один из минусов не может быть разделен между различными начальными сегментами. Если вам нужны действительно абсурдно быстрые inits и tails, лучше всего использовать Data.Sequence; Реализация Луи Вассермана волшебна. Другой возможностью было бы использовать Data.Vectorон предположительно использует нарезку для таких вещей.

person dfeuer    schedule 15.04.2015
comment
Очень исчерпывающий ответ. Спасибо. - person jub0bs; 15.04.2015