Foldl - это рекурсивный хвост, так как Foldr работает быстрее, чем Foldl?
https://stackoverflow.com/questions/3429634
-
26-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я хотел проверить Foldl VS Foldr. Из того, что я видел, вы должны использовать Foldl Over Foldr, когда вы когда-либо сможете из-за оптимизации reccurkionsion Caster.
Это имеет смысл. Однако после запуска этого теста я запутался:
Foldr (принимает 0,057, при использовании команды времени):
a::a -> [a] -> [a]
a x = ([x] ++ )
main = putStrLn(show ( sum (foldr a [] [0.. 100000])))
Foldl (принимает 0,089, при использовании команды времени):
b::[b] -> b -> [b]
b xs = ( ++ xs). (\y->[y])
main = putStrLn(show ( sum (foldl b [] [0.. 100000])))
Понятно, что этот пример тривиален, но я смущен, почему Foldr бьет папку. Разве это не будет четким случаем, когда пады выигрывают?
Решение
Добро пожаловать в мир ленивой оценки.
Когда вы думаете об этом с точки зрения строгой оценки, Foldl выглядит «Хорошо» и Foldr выглядит «плохо», потому что Foldl - это рекурсивный хвост, но Foldr должен был бы построить башню в стеке, поэтому он может обработать последний пункт первым.
Однако ленивая оценка превращает таблицы. Возьмите, например, определение функции карты:
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
Это было бы не слишком хорошо, если бы Haskell использовал строгую оценку, поскольку он должен был бы сначала вычислить хвост, а затем подготовить товар (для всех предметов в списке). Единственный способ сделать это эффективно бы построить элементы в обратном направлении, похоже.
Однако благодаря ленивой оценке HASKELL эта функция карты на самом деле эффективна. Списки в Haskell можно продумать как генераторы, и эта функция карты генерирует свой первый элемент, применяя F к первому элементу списка ввода. Когда ему нужен второй элемент, он просто делает то же самое снова (без использования дополнительного пространства).
Оказывается, что map можно описать с точки зрения foldr:
map f xs = foldr (\x ys -> f x : ys) [] xs
Трудно сказать, глядя на него, но ленивые оценки пинают, потому что Foldr может дать f свой первый аргумент сразу:
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
Поскольку f определяется map Может вернуть первый элемент списка результатов с использованием исключительно первого параметра, складка может работать лениво в постоянном пространстве.
Теперь ленивая оценка укусила. Например, попробуйте запустить сумму [1..1000000]. Это дает переполнение стека. Почему это должно? Это должно просто оценить слева направо, верно?
Давайте посмотрим, как Haskell оценивает это:
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
sum = foldl (+) 0
sum [1..1000000] = foldl (+) 0 [1..1000000]
= foldl (+) ((+) 0 1) [2..1000000]
= foldl (+) ((+) ((+) 0 1) 2) [3..1000000]
= foldl (+) ((+) ((+) ((+) 0 1) 2) 3) [4..1000000]
...
= (+) ((+) ((+) (...) 999999) 1000000)
Haskell слишком лень, чтобы выполнить дополнения, как идет. Вместо этого он в конечном итоге с башней нерехие Thunks, которые должны быть вынуждены получить номер. Переполнение стека происходит во время этой оценки, поскольку он должен глубоко резать, чтобы оценить все Thunks.
К счастью, в Data.list называется специальная функция. foldl' это действует строго. foldl' (+) 0 [1..1000000] не будет сложить переполнение. (Примечание: я пытался заменить foldl с foldl' В вашем тесте, но он на самом деле заставил его запустить медленнее.)
Другие советы
Редактировать: При взгляде на эту проблему снова, я думаю, что все текущие объяснения несколько недостаточны, поэтому я написал более длительное объяснение.
Разница в том, как foldl и foldr применить их функцию восстановления. Глядя на то foldr случай, мы можем расширить это как
foldr (\x -> [x] ++ ) [] [0..10000]
[0] ++ foldr a [] [1..10000]
[0] ++ ([1] ++ foldr a [] [2..10000])
...
Этот список обрабатывается sum, который потребляет это следующим образом:
sum = foldl' (+) 0
foldl' (+) 0 ([0] ++ ([1] ++ ... ++ [10000]))
foldl' (+) 0 (0 : [1] ++ ... ++ [10000]) -- get head of list from '++' definition
foldl' (+) 0 ([1] ++ [2] ++ ... ++ [10000]) -- add accumulator and head of list
foldl' (+) 0 (1 : [2] ++ ... ++ [10000])
foldl' (+) 1 ([2] ++ ... ++ [10000])
...
Я оставил детали конкатенации списка, но именно так продолжается снижение. Важная часть состоит в том, что все обработано, чтобы минимизировать перечисленные обходы. То foldr Только один раз пересекает список, объединения не требуют проходов непрерывного списка, а также sum Наконец потребляет список в одном проходе. Критически, глава списка доступен от foldr сразу sum, так sum Может начать работу немедленно, и ценности могут быть GC'd, поскольку они генерируются. С фейзами Fusion, таких как vector, даже промежуточные списки, скорее всего, будут слиты.
Контрастировать это к foldl Функция:
b xs = ( ++xs) . (\y->[y])
foldl b [] [0..10000]
foldl b ( [0] ++ [] ) [1..10000]
foldl b ( [1] ++ ([0] ++ []) ) [2..10000]
foldl b ( [2] ++ ([1] ++ ([0] ++ [])) ) [3..10000]
...
Обратите внимание, что теперь глава списка недоступен до foldl закончил. Это означает, что весь список должен быть построен в памяти до sum может начать работать. Это намного менее эффективно в целом. Запуск двух версий с +RTS -s Показывает несчастную производительность сбора мусора из версии Foldl.
Это также случай, когда foldl' не поможет. Добавленная строгость foldl' Не изменяет способ создания промежуточного списка. Глава списка остается недоступным до конца Foldl ', поэтому результат все еще будет медленнее, чем с foldr.
Я использую следующее правило, чтобы определить лучший выбор fold
- Для складок, которые являются снижение, использовать
foldl'(например, это будет единственное / окончательное обход) - В противном случае используйте
foldr. - Не используйте
foldl.
В большинстве случаев foldr Это лучшая функция сгиба, поскольку направление обхода оптимально для ленивых оценок списков. Это также единственная способная обработка бесконечных списков. Дополнительная строгость foldl' Может сделать его быстрее в некоторых случаях, но это зависит от того, как вы будете использовать эту структуру и насколько это лениво.
Я не думаю, что кто-то на самом деле сказал реальный ответ на этом еще, если я не пропустил что-то (который вполне может быть правдой и приветствовать с Downvotes).
Я думаю, что самые большие в этом случае это то, что foldr Создает список, как это:
[0] ++ ([1] ++ ([2] ++ (... ++ [1000000])))
Тогда как foldl Создает список, как это:
((([0] ++ [1]) ++ [2]) ++ ... ) ++ [999888]) ++ [999999]) ++ [1000000]
Разница в тонком, но обратите внимание, что в foldr версия ++ Всегда имеет только один элемент списка в качестве левого аргумента. С foldl Версия, там до 999999 элементов в ++левый аргумент (в среднем около 500000), но только один элемент в правильном аргументе.
Однако, ++ Требуется пропорциональна размеру левого аргумента, так как он должен посмотреть, хотя весь список левых аргументов до конца, а затем осматривать этот последний элемент к первому элементу правильного аргумента (в лучшем случае, возможно, это действительно нужно сделать Копировать). Список правильного аргумента не изменится, поэтому не имеет значения, насколько это большой.
Вот почему foldl Версия намного медленнее. Это не имеет ничего общего с ленью на мой взгляд.
Проблема в том, что оптимизация рекурсионного хвоста является оптимизацией памяти, а не оптимизация времени выполнения!
Оптимизация рекурсии хвоста позволяет избежать необходимости запоминания ценностей для каждого рекурсивного вызова.
Итак, Foldl на самом деле «хорошо» и Foldr «плохо».
Например, учитывая определения Foldr и Foldl:
foldl f z [] = z
foldl f z (x:xs) = foldl f (z `f` x) xs
foldr f z [] = z
foldr f z (x:xs) = x `f` (foldr f z xs)
Вот как выражение «Foldl (+) 0 [1,2,3] оценивается:
foldl (+) 0 [1, 2, 3]
foldl (+) (0+1) [2, 3]
foldl (+) ((0+1)+2) [3]
foldl (+) (((0+1)+2)+3) [ ]
(((0+1)+2)+3)
((1+2)+3)
(3+3)
6
Обратите внимание, что Foldl не помнит значения 0, 1, 2 ..., но проходят все выражение (((((0 + 1) +2) +3) в качестве аргумента лениво и не оценивает его до последней оценки Foldl, где он достигает базового корпуса и возвращает значение, передаваемое в качестве второго параметра (z), который еще не оценивается.
С другой стороны, вот как работает Foldr:
foldr (+) 0 [1, 2, 3]
1 + (foldr (+) 0 [2, 3])
1 + (2 + (foldr (+) 0 [3]))
1 + (2 + (3 + (foldr (+) 0 [])))
1 + (2 + (3 + 0)))
1 + (2 + 3)
1 + 5
6
Важным отличием вот в том, что где Foldl оценивает все выражение в последнем вызове, избегая необходимости возвращаться, чтобы добраться до запоминающих значений, Foldr No. Foldr запомнить одно целое число для каждого вызова и выполняет дополнение в каждом вызове.
Важно иметь в виду, что Foldr и Foldl не всегда эквивалены. Например, попробуйте вычислить это выражение в объятиях:
foldr (&&) True (False:(repeat True))
foldl (&&) True (False:(repeat True))
Foldr и Foldl эквивалентны только при определенных описанных условиях здесь
(Извините за мой плохой английский)
Для А, [0.. 100000] Список должен быть немедленно расширен, так что Foldr может начать с последнего элемента. Тогда как это складывает вещи вместе, промежуточные результаты
[100000]
[99999, 100000]
[99998, 99999, 100000]
...
[0.. 100000] -- i.e., the original list
Поскольку никто не разрешается изменить значение этого списка (Haskell - это чистый функциональный язык), компилятор может бесплатно повторно использовать значение. Промежуточные значения, как [99999, 100000] Может даже быть просто указателями в расширенные [0.. 100000] список вместо отдельных списков.
Для B посмотрите на промежуточные значения:
[0]
[0, 1]
[0, 1, 2]
...
[0, 1, ..., 99999]
[0.. 100000]
Каждый из этих промежуточных списков не может быть повторно использован, потому что если вы измените конец списка, вы изменили все другие значения, которые указывают на него. Таким образом, вы создаете кучу дополнительных списков, которые требуют времени, чтобы построить в памяти. Таким образом, в этом случае вы проводите намного больше времени выделения и заполнению этих списков, которые являются промежуточными значениями.
Поскольку вы просто делаете копию списка, работает быстрее, потому что он начинается с расширения полного списка, а затем просто продолжает перемещать указатель сзади списка к передней части.
Ни один foldl ни foldr это хвост оптимизирован. Это только foldl'.
Но в вашем случае используя ++ с foldl' не хорошая идея, потому что последовательная оценка ++ Приведет к пересечению растущего аккумулятора снова и снова.
Ну, позвольте мне переписать ваши функции таким образом, что разница должна быть очевидна -
a :: a -> [a] -> [a]
a = (:)
b :: [b] -> b -> [b]
b = flip (:)
Вы видите, что B сложнее, чем. Если вы хотите быть точным a нуждается в одном этапе снижения для значения, который будет рассчитан, но b нужно два. Это делает разницу времени, которую вы измеряете, во втором примере в два раза больше необходимо выполнить все сокращения.
// редактировать: но сложность времени такая же, поэтому я не буду много беспокоить.
