Недостаточная производительность Haskell foldl с (++)

У меня есть этот код:

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 

    Классическое поведение списка.

    Отзыв:

     (:) -- O(1) complexity (++) -- O(n) complexity 

    Итак, вы создаете O (n ^ 2) algo вместо O (n).

    Для этого обычного случая добавления списков поэтапно попробуйте использовать dlist или просто измените его в конце.

    В этой проблеме много путаницы. Обычная причина заключается в том, что «многократное добавление в конце списка требует повторных обходов списка и, следовательно, O(n^2) ». Но это было бы так просто при строгой оценке. При ленивой оценке все должно быть отложено, поэтому он задает вопрос о том, действительно ли есть эти повторные обходы и добавления. Добавление в конце инициируется потреблением спереди, и, поскольку мы потребляем спереди, список становится короче, так что точное время этих действий неясно. Таким образом, реальный ответ более тонкий и касается конкретных шагов по снижению при ленивой оценке.

    Непосредственным виновником является то, что foldl' только 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' fz [] = z foldl' fz (x:xs) = let w=fzx in w `seq` foldl' fw 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) и т. д. – classическое поведение 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 -> fx : 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 -> fx : 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 -> fx : acc) [] [2..10]) -- firstElem doesn't need the tail, so it's never computed! = Just (1*2) 

    Это также означает, что newList основе 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 

    Алгоритм, основанный на firstElem_foldr (newList [1..10]) 4 шага, чтобы вычислить firstElem_foldr (newList [1..10]) , в то время как foldl' помощью 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.

    Давайте будем гением компьютера.