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 - он, вероятно, не стоит.
