Почему списки различий более эффективны, чем обычная конкатенация?
В настоящее время я пробираюсь через книгу " Learn you a haskell" в Интернете и пришел к главе, где автор объясняет, что некоторые объединения списков могут быть неэффективными: например,
((((a ++ b) ++ c) ++ d) ++ e) ++ f
Якобы неэффективно. Решение, которое предлагает автор, заключается в использовании "списков различий", определенных как
newtype DiffList a = DiffList {getDiffList :: [a] -> [a] }
instance Monoid (DiffList a) where
mempty = DiffList (\xs -> [] ++ xs)
(DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs))
Я пытаюсь понять, почему DiffList в некоторых случаях эффективнее в вычислительном отношении, чем простая конкатенация. Может ли кто-нибудь объяснить мне простыми словами, почему приведенный выше пример настолько неэффективен и каким образом DiffList решает эту проблему?
2 ответа
Проблема в
((((a ++ b) ++ c) ++ d) ++ e) ++ f
это вложение. Приложения (++) левые, и это плохо; правой вложенности
a ++ (b ++ (c ++ (d ++ (e ++f))))
не будет проблемой. Это потому (++) определяется как
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
поэтому, чтобы найти, какое уравнение использовать, реализация должна погрузиться в дерево выражений
(++)
/ \
(++) f
/ \
(++) e
/ \
(++) d
/ \
(++) c
/ \
a b
пока он не узнает, является ли левый операнд пустым или нет. Если он не пустой, его голова берется и поднимается к вершине, но хвост левого операнда остается нетронутым, поэтому, когда требуется следующий элемент конкатенации, та же самая процедура начинается снова.
Когда конкатенации вложены справа, левый операнд (++) всегда наверху, и проверка на пустоту / пузырение в голове - O(1).
Но когда конкатенации оставлены вложенными, n слои глубоко, чтобы достичь первого элемента, n узлы дерева должны быть пройдены для каждого элемента результата (исходя из первого списка, n-1 для пришедших со второго и т. д.).
Давайте рассмотрим a = "hello" в
hi = ((((a ++ b) ++ c) ++ d) ++ e) ++ f
и мы хотим оценить take 5 hi, Итак, во-первых, необходимо проверить,
(((a ++ b) ++ c) ++ d) ++ e
пустой. Для этого необходимо проверить,
((a ++ b) ++ c) ++ d
пустой. Для этого необходимо проверить,
(a ++ b) ++ c
пустой. Для этого необходимо проверить,
a ++ b
пустой. Для этого необходимо проверить,
a
пустой. Уф. Это не так, поэтому мы можем снова всплыть, собирая
a ++ b = 'h':("ello" ++ b)
(a ++ b) ++ c = 'h':(("ello" ++ b) ++ c)
((a ++ b) ++ c) ++ d = 'h':((("ello" ++ b) ++ c) ++ d)
(((a ++ b) ++ c) ++ d) ++ e = 'h':(((("ello" ++ b) ++ c) ++ d) ++ e)
((((a ++ b) ++ c) ++ d) ++ e) ++ f = 'h':((((("ello" ++ b) ++ c) ++ d) ++ e) ++ f)
и для 'e', мы должны повторить, и для 'l'с тоже...
Рисуя часть дерева, пузырьки выглядят так:
(++)
/ \
(++) c
/ \
'h':"ello" b
становится первым
(++)
/ \
(:) c
/ \
'h' (++)
/ \
"ello" b
а потом
(:)
/ \
'h' (++)
/ \
(++) c
/ \
"ello" b
вплоть до вершины. Структура дерева, которое становится правым потомком верхнего уровня (:) наконец, точно такой же, как структура исходного дерева, если только крайний левый список не пуст, когда
(++)
/ \
[] b
узлы свернуты просто b,
Таким образом, если у вас есть вложенные конкатенации с короткими списками, оставленные вложенными, конкатенация становится квадратичной, потому что получить начало конкатенации - операция O (глубина вложения). В общем, конкатенация левостороннего
(...((a_d ++ a_{d-1}) ++ a_{d-2}) ...) ++ a_2) ++ a_1
является O(sum [i * length a_i | i <- [1 .. d]]) оценить полностью.
С помощью списков различий (без обертки нового типа для простоты описания) не важно, являются ли композиции вложенными
((((a ++) . (b ++)) . (c ++)) . (d ++)) . (e ++)
или право вложенный. Как только вы прошли через гнездо, чтобы достичь (a ++), тот (++) поднимается в верхнюю часть дерева выражений, поэтому получая каждый элемент a снова O(1).
На самом деле, вся композиция связана со списками различий, как только вам потребуется первый элемент,
((((a ++) . (b ++)) . (c ++)) . (d ++)) . (e ++) $ f
становится
((((a ++) . (b ++)) . (c ++)) . (d ++)) $ (e ++) f
(((a ++) . (b ++)) . (c ++)) $ (d ++) ((e ++) f)
((a ++) . (b ++)) $ (c ++) ((d ++) ((e ++) f))
(a ++) $ (b ++) ((c ++) ((d ++) ((e ++) f)))
a ++ (b ++ (c ++ (d ++ (e ++ f))))
и после этого каждый список является непосредственным левым операндом верхнего уровня (++) после того, как предыдущий список был использован.
Важно то, что предваряющая функция (a ++) может начать производить свой результат без проверки своего аргумента, так что реассоциация из
($)
/ \
(.) f
/ \
(.) (e ++)
/ \
(.) (d ++)
/ \
(.) (c ++)
/ \
(a ++) (b ++)
с помощью
($)---------
/ \
(.) ($)
/ \ / \
(.) (d ++) (e ++) f
/ \
(.) (c ++)
/ \
(a ++) (b ++)
в
($)
/ \
(a ++) ($)
/ \
(b ++) ($)
/ \
(c ++) ($)
/ \
(d ++) ($)
/ \
(e ++) f
не нужно ничего знать о составных функциях окончательного списка fтак что это просто O(depth) переписывания. Тогда на высшем уровне
($)
/ \
(a ++) stuff
становится
(++)
/ \
a stuff
и все элементы a можно получить за один шаг. В этом примере, где у нас было чистое левое вложение, необходима только одна перезапись. Если вместо (например) (d ++) функция в этом месте была левой вложенной композицией, (((g ++) . (h ++)) . (i ++)) . (j ++)реассоциация верхнего уровня оставила бы это нетронутым, и это было бы повторно связано, когда оно становится левым операндом верхнего уровня ($) после того, как все предыдущие списки были использованы.
Общая работа, необходимая для всех реассоциаций O(number of lists)Таким образом, общая стоимость объединения O(number of lists + sum (map length lists)), (Это означает, что вы также можете добиться плохой производительности, вставив много глубоко вложенных ([] ++).)
newtype DiffList a = DiffList {getDiffList :: [a] -> [a] }
instance Monoid (DiffList a) where
mempty = DiffList (\xs -> [] ++ xs)
(DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs))
просто оборачивает это так, чтобы с ним было удобнее обращаться абстрактно.
DiffList (a ++) `mappend` DiffList (b ++) ~> DiffList ((a ++) . (b++))
Обратите внимание, что это эффективно только для функций, которым не нужно проверять свой аргумент, чтобы начать производить вывод, если произвольные функции обернуты в DiffLists, у вас нет таких гарантий эффективности. В частности, добавление ((++ a), обернутый или нет) может создавать вложенные деревья (++) когда составлено право вложенным, так что вы можете создать O(n²) поведение сцепления с этим, если DiffList конструктор выставлен.
Это может помочь взглянуть на определение конкатенации:
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
Как вы можете видеть, для объединения двух списков вам нужно пройти по левому списку и создать его "копию", просто чтобы вы могли изменить его конец (это потому, что вы не можете напрямую изменить конец старого список, из-за неизменности).
Если вы делаете свои объединения в правильной ассоциативной форме, проблем нет. После вставки к списку больше никогда не придется прикасаться (обратите внимание, что определение ++ никогда не проверяет список справа), поэтому каждый элемент списка вставляется только "один раз" в течение общего времени O(N).
--This is O(n)
(a ++ (b ++ (c ++ (d ++ (e ++ f)))))
Однако, если вы делаете конкатенацию левым ассоциативным способом, тогда "текущий" список придется "сносить" и "перестраивать" каждый раз, когда вы добавляете в конец другой фрагмент списка. Каждый элемент списка будет повторяться, когда он вставляется и всякий раз, когда добавляются будущие фрагменты! Это похоже на проблему, возникающую в C, если вы наивно вызываете strcat несколько раз подряд.
Что касается списков различий, то хитрость в том, что они как бы держат явную "дыру" в конце. Когда вы преобразуете DList обратно в обычный список, вы передаете его тем, кем хотите быть в дыре, и он будет готов к работе. Нормальные списки, с другой стороны, всегда закрывают отверстие в конце [] поэтому, если вы хотите изменить его (при объединении), вам нужно открыть список, чтобы добраться до этой точки.
Поначалу определение списков различий с функциями может показаться пугающим, но на самом деле все довольно просто. Вы можете просматривать их с точки зрения объектно-ориентированного подхода, считая их непрозрачными объектами. Метод "toList", который получает список, который вы должны вставить в отверстие в конце, возвращает внутренний префикс DL плюс предоставленный хвост. Это эффективно, потому что вы закрываете "дыру" в конце только после того, как закончите конвертацию.