Haskell складывает плохую производительность с (++)
У меня есть этот код:
import Data.List
newList_bad lst = foldl' (\acc x -> acc ++ [x*2]) [] lst
newList_good lst = foldl' (\acc x -> x*2 : acc) [] lst
Эти функции возвращают списки с каждым элементом, умноженным на 2:
*Main> newList_bad [1..10]
[2,4,6,8,10,12,14,16,18,20]
*Main> newList_good [1..10]
[20,18,16,14,12,10,8,6,4,2]
В ghci:
*Main> sum $ newList_bad [1..15000]
225015000
(5.24 secs, 4767099960 bytes)
*Main> sum $ newList_good [1..15000]
225015000
(0.03 secs, 3190716 bytes)
Зачем newList_bad функция работает в 200 раз медленнее, чем newList_good? Я понимаю, что это не очень хорошее решение для этой задачи. Но почему этот невинный код работает так медленно?
Что это за "4767099960 байт"?? Для этой простой операции Haskell использовал 4 GiB??
После компиляции:
C:\1>ghc -O --make test.hs
C:\1>test.exe
225015000
Time for sum (newList_bad [1..15000]) is 4.445889s
225015000
Time for sum (newList_good [1..15000]) is 0.0025005s
3 ответа
Классический список поведения.
Отзыв:
(:) -- O(1) complexity
(++) -- O(n) complexity
Таким образом, вы создаете алгоритм O(n^2) вместо O(n).
В этом распространенном случае постепенного добавления к спискам попробуйте использовать список или просто поверните его в конце.
Существует много путаницы по этому вопросу. Обычная причина заключается в том, что "многократное добавление в конец списка требует повторных обходов списка и поэтому O(n^2) ". Но при строгой оценке это было бы так просто. При ленивой оценке все должно быть отложено, поэтому возникает вопрос, действительно ли вообще существуют эти повторные обходы и добавления. Добавление в конце вызывается потреблением впереди и так как мы потребляем вначале, список становится короче, поэтому точные сроки этих действий неясны, поэтому реальный ответ более тонкий и касается конкретных шагов сокращения при ленивой оценке.
Непосредственный виновник в том, что foldl' только заставляет свой аргумент-накопитель обращаться к нормальной форме слабой головы - то есть до тех пор, пока не будет открыт нестрогий конструктор. Здесь задействованы функции
(a:b)++c = a:(b++c) -- does nothing with 'b', only pulls 'a' up
[]++c = c -- so '++' only forces 1st elt from its left arg
foldl' f z [] = z
foldl' f z (x:xs) = let w=f z x in w `seq` foldl' f w xs
sum xs = sum_ xs 0 -- forces elts fom its arg one by one
sum_ [] a = a
sum_ (x:xs) a = sum_ xs (a+x)
и поэтому фактическая последовательность сокращения (с g = foldl' f)
sum $ foldl' (\acc x-> acc++[x^2]) [] [a,b,c,d,e]
sum $ g [] [a,b,c,d,e]
g [a^2] [b,c,d,e]
g (a^2:([]++[b^2])) [c,d,e]
g (a^2:(([]++[b^2])++[c^2])) [d,e]
g (a^2:((([]++[b^2])++[c^2])++[d^2])) [e]
g (a^2:(((([]++[b^2])++[c^2])++[d^2])++[e^2])) []
sum $ (a^2:(((([]++[b^2])++[c^2])++[d^2])++[e^2]))
Обратите внимание, что мы только выполнили O(n) до сих пор. a^2 немедленно доступен здесь для sum Потребление, но b^2 не является. Мы остались здесь с левой вложенной структурой ++ выражения. Остальное лучше всего объяснить в этом ответе Даниэля Фишера. Суть в том, что получить b^2 из, O(n-1) шаги должны быть выполнены - и структура, оставленная в результате этого доступа, все еще останется вложенной, поэтому следующий доступ займет O(n-2) шаги и так далее - классика O(n^2) поведение. Так что настоящая причина в том, что ++ недостаточно форсирует или реорганизует свои аргументы, чтобы быть эффективным.
Это на самом деле нелогично. Мы могли бы ожидать, что ленивая оценка волшебным образом "сделает это" для нас здесь. Ведь мы только выражаем намерение добавить [x^2] до конца списка в будущем, мы на самом деле не делаем это сразу. Таким образом, отсчет времени здесь выключен, но это можно сделать правильно - когда мы получим доступ к списку, новые элементы будут добавлены в него и использованы сразу же, если время было правильным: если c^2 будет добавлен в список после b^2 (в пространстве), скажем, как раз перед (во времени) b^2 будет потребляться, обход / доступ всегда будет O(1),
Это достигается с помощью так называемого метода "списка различий":
newlist_dl lst = foldl' (\z x-> (z . (x^2 :)) ) id lst
который, если вы думаете об этом на мгновение, выглядит точно так же, как ваш ++[x^2] версия. Это выражает то же самое намерение, и оставляет левую вложенную структуру также.
Разница, как объяснено в том же ответе Даниэля Фишера, заключается в том, что (.) при первом включении цепочка перестраивается в гнездо справа ($) структура 1 в O(n) шаги, после которых каждый доступ O(1) и сроки добавления оптимальны в точности так, как описано в предыдущем абзаце, поэтому мы остаемся с общим O(n) поведение.
1, что отчасти волшебно, но это случается.:)
Чтобы дополнить другие ответы немного большей перспективой: с ленивыми списками, используя foldl' в функции, которая возвращает список, обычно плохая идея. foldl' часто полезно, когда вы уменьшаете список до строгого (не ленивого) скалярного значения (например, суммируете список). Но когда вы создаете список в результате, foldr обычно лучше из-за лени; : конструктор ленив, поэтому хвост списка не вычисляется до тех пор, пока он действительно не понадобится.
В твоем случае:
newList_foldr lst = foldr (\x acc -> x*2 : acc) [] lst
Это на самом деле так же, как map (*2):
newList_foldr lst = map (*2) lst
map f lst = foldr (\x acc -> f x : acc) [] lst
Оценка (с использованием первого, mapбез определения)
newList_foldr [1..10]
= foldr (\x acc -> x*2 : acc) [] [1..10]
= foldr (\x acc -> x*2 : acc) [] (1:[2..10])
= 1*2 : foldr (\x rest -> f x : acc) [] [2..10]
Это примерно столько, сколько Haskell оценит, когда newList [1..10] вынужден. Он оценивает дальнейшие результаты только в том случае, если потребитель этого результата требует этого, и только настолько, насколько это необходимо для удовлетворения потребителя. Так, например:
firstElem [] = Nothing
firstElem (x:_) = Just x
firstElem (newList_foldr [1..10])
-- firstElem only needs to evaluate newList [1..10] enough to determine
-- which of its subcases applies—empty list or pair.
= firstElem (foldr (\x acc -> x*2 : acc) [] [1..10])
= firstElem (foldr (\x acc -> x*2 : acc) [] (1:[2..10]))
= firstElem (1*2 : foldr (\x rest -> f x : acc) [] [2..10])
-- firstElem doesn't need the tail, so it's never computed!
= Just (1*2)
Это также означает, что foldr-основан newList также может работать с бесконечными списками:
newList_foldr [1..] = [2,4..]
firstElem (newList_foldr [1..]) = 2
Если вы используете foldl'с другой стороны, вы всегда должны вычислять целые списки, что также означает, что вы не можете работать с бесконечными списками:
firstElem (newList_good [1..]) -- doesn't terminate
firstElem (newList_good [1..10])
= firstElem (foldl' (\acc x -> x*2 : acc) [] [1..10])
= firstElem (foldl' (\acc x -> x*2 : acc) [] (1:[2..10]))
= firstElem (foldl' (\acc x -> x*2 : acc) [2] [2..10])
-- we can't short circuit here because the [2] is "inside" the foldl', so
-- firstElem can't see it
= firstElem (foldl' (\acc x -> x*2 : acc) [2] (2:[3..10]))
= firstElem (foldl' (\acc x -> x*2 : acc) [4,2] [3..10])
...
= firstElem (foldl' (\acc x -> x*2 : acc) [18,16,14,12,10,8,6,4,2] (10:[]))
= firstElem (foldl' (\acc x -> x*2 : acc) [20,18,16,14,12,10,8,6,4,2] [])
= firstElem [20,18,16,14,12,10,8,6,4,2]
= firstElem (20:[18,16,14,12,10,8,6,4,2])
= Just 20
foldrалгоритм вычислил 4 шага firstElem_foldr (newList [1..10])тогда как foldl'На основе взятого порядка 21 шага. Хуже всего то, что 4 шага - это постоянные затраты, тогда как 21 шаг пропорционален длине списка ввода -firstElem (newList_good [1..150000]) занимает 300 001 шагов, а firstElem (newList_foldr [1..150000] занимает 5 шагов, как и firstElem (newList_foldr [1..] в этом отношении.
Обратите внимание, что firstElem (newList_foldr [1.10]) работает в постоянном пространстве, а также в постоянном времени (это необходимо; вам нужно больше, чем постоянное время, чтобы выделить больше, чем постоянное пространство). Про-foldl трюизм от строгих языков…foldl хвост рекурсивен и работает в постоянном пространстве, foldr не является хвостовой рекурсивностью и работает в линейном пространстве или хуже "- это не так в Haskell.