Data.Sequence vs. Data.DList для добавления данных в конец списка.

Я пишу код, который нужно часто добавлять в конец списка. Я знаю, что использование "++" неэффективно. Поэтому вместо этого я создаю список назад, добавляя его в голову, а затем меняю его, когда закончите. Я понимаю, что это обычная тактика новичков.

Я хотел бы создать его в правильном порядке для начала, но это означает переход на новую структуру данных. Я рассматриваю использование Data.Sequence или Data.DList для своего контейнера. Мой список состоит из строгих пар int, и мне не нужен случайный доступ к нему. Каковы относительные достоинства Data.Sequence и Data.DList, и есть ли другие контейнеры, которые я должен рассмотреть?

Ответ 1

Использовать ли Data.Sequence или DList зависит от того, как вы собираетесь использовать результирующий список. DList отлично, когда вы создаете последовательность, скажем, в вычислении Writer, чтобы преобразовать в список в конце и использовать его. Однако, если вам нужно использовать промежуточные результаты, например:

f (foo ++ bar)
+ f (foo ++ bar ++ baz)
+ f (foo ++ bar ++ baz ++ quux)

то DList довольно плохо, потому что ему нужно каждый раз перепрограммировать позвоночник. Data.Sequence - лучший выбор в этой ситуации. Data.Sequence также лучше, если вам нужно удалить элементы из последовательности.

Но, возможно, вам даже не нужно принимать это решение. Реверсивные списки в конце вычисления распространены в строгих функциональных языках, таких как ML и Scheme, но не в Haskell. Возьмем, к примеру, эти два способа написания map:

map_i f xs = reverse $ go [] xs
    where
    go accum [] = accum
    go accum (x:xs) = go (f x : accum) xs

map_ii f [] = []
map_ii f (x:xs) = f x : map_ii f xs

В строгом языке map_ii будет ужасным, потому что он использует пространство линейного стека, тогда как map_i является хвостовым рекурсивным. Но поскольку Haskell ленив, map_i является неэффективным. map_ii может потреблять один элемент входа и выводить один элемент вывода, тогда как map_i потребляет весь вход до получения любого выхода.

Рекурсия хвоста не является святым граалем эффективной реализации в Haskell. При создании структуры данных, такой как список, вы действительно хотите быть корекурсивным; то есть сделать рекурсивный вызов под приложением конструктора (например, f x : map_ii f xs выше).

Итак, если вы оказываетесь в обратном порядке после хвостового рекурсивного функционала, посмотрите, можете ли вы включить всю партию в корекурсивную функцию.

Ответ 2

Я сделал простое сравнение критериев:

let mdata = replicate 1000 (replicate 100 (13 :: Int))
let f1 = foldl' (++) []
let fr = foldr (++) []
let f2 = foldl' (\s next -> s Seq.|> next) mempty
let f3 = foldl' (DL.snoc) mempty

defaultMain [
    bgroup "time encode" [ bench "++ - foldl"   $ nf (AE.encode . f1) mdata
                         , bench "++ - foldr"   $ nf (AE.encode . fr) mdata
                         , bench "Seq |>"  $ nf (AE.encode . toList . f2) mdata
                         ,  bench "DList snoc"  $ nf (AE.encode . DL.toList . f3) mdata]
  ]

В результате:

benchmarking time encode/++ - foldl
time                 604.1 ms   (570.0 ms .. 654.6 ms)
                     0.999 R²   (NaN R² .. 1.000 R²)
mean                 619.2 ms   (608.9 ms .. 625.6 ms)
std dev              9.761 ms   (0.0 s .. 11.21 ms)
variance introduced by outliers: 19% (moderately inflated)

benchmarking time encode/++ - foldr
time                 2.554 ms   (2.503 ms .. 2.610 ms)
                     0.995 R²   (0.990 R² .. 0.998 R²)
mean                 2.584 ms   (2.547 ms .. 2.628 ms)
std dev              134.1 μs   (111.7 μs .. 186.6 μs)
variance introduced by outliers: 34% (moderately inflated)

benchmarking time encode/Seq |>
time                 2.020 ms   (1.986 ms .. 2.049 ms)
                     0.997 R²   (0.995 R² .. 0.998 R²)
mean                 2.106 ms   (2.078 ms .. 2.138 ms)
std dev              105.8 μs   (85.60 μs .. 130.5 μs)
variance introduced by outliers: 34% (moderately inflated)

benchmarking time encode/DList snoc
time                 1.992 ms   (1.952 ms .. 2.034 ms)
                     0.996 R²   (0.994 R² .. 0.998 R²)
mean                 2.030 ms   (2.000 ms .. 2.060 ms)
std dev              97.88 μs   (82.60 μs .. 122.3 μs)
variance introduced by outliers: 34% (moderately inflated)

Заключение: используйте Data.Sequence. Он имеет максимальную гибкость, но при этом более низкая производительность, чем DList - он, вероятно, не стоит.