Что такое DList?
Я попробовал поискать в Google для этого, но все, что я получил, было рассказами о незначительных знаменитостях. Учитывая отсутствие документации, что такое DList?
4 ответа
Это список различий, аналогичный "списку различий как функциям"
scala> val (l1, l2, l3) = (List(1, 2, 3), List(4, 5, 6), List(7, 8, 9))
l1: List[Int] = List(1, 2, 3)
l2: List[Int] = List(4, 5, 6)
l3: List[Int] = List(7, 8, 9)
Эффективная предоплата:
scala> l1 ::: l2 ::: l3
res8: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)
Неэффективное добавление. Это создает промежуточный список (l1 ++ l2), затем ((l1 ++ l2) ++ l3)
scala> l1 ++ l2 ++ l3 // inefficient
res9: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)
DList хранит добавления, и нужно только создать один полный список, эффективно вызывая:
scala> List(l1, l2, l3) reduceRight ( _ ::: _)
res10: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)
Списки различий представляют собой структуру данных в виде списков, которая поддерживает операции добавления O(1).
Присоединение и другие операции, которые изменяют список, представляются посредством композиции функций функций изменения, а не путем прямого копирования списка.
Пример из библиотеки dlist на Haskell:
-- Lists as functions
newtype DList a = DL { unDL :: [a] -> [a] }
-- The empty list
empty = DL id
-- The append case: composition, a la Hughes
append xs ys = DL (unDL xs . unDL ys)
-- Converting to a regular list, linear time.
toList = ($[]) . unDL
Техника восходит, по крайней мере, к Хьюзу 84. Новое представление списков и его применение к функции "reverse", Р. Джон Хьюз, 1984 г., где он предлагает представлять списки как функции и добавлять их как композицию функций, позволяя, например, обратный ход по линейному времени. Из бумаги:
Это тип данных в неканоническом скалярном пакете, полезный для типизированных списков с постоянным доступом с обеих сторон. (Хитрость заключается в том, чтобы Google для "scala" И "dlist".)
DList, тип данных для представления элементов одного типа с постоянными операциями добавления / добавления.