Насколько быстро Data.Sequence.Seq по сравнению с []?

Ясно, что Seq асимптотически выполняет то же самое или лучше, чем [] для всех возможных операций. Но поскольку его структура сложнее, чем списки, для небольших размеров его постоянные накладные расходы, вероятно, будут замедляться. Я хотел бы узнать, в частности:

  • Насколько медленнее <| по сравнению с :?
  • Насколько медленнее складывается/перемещается Seq по сравнению с откидыванием/перемещением [] (исключая стоимость функции сгибания/перемещения)?
  • Каков размер (приблизительно), для которого \xs x -> xs ++ [x] становится медленнее, чем |>?
  • Каков размер (приблизительно), для которого ++ становится медленнее, чем ><?
  • Какова стоимость вызова viewl и соответствия шаблонов по результату по сравнению с сопоставлением шаблонов в списке?
  • Сколько памяти занимает n -элемент Seq по сравнению с списком n -element? (Не считая памяти, занимаемой элементами, только структура.)

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

Ответы

Ответ 1

Это должно быть начало - http://www.haskell.org/haskellwiki/Performance#Data.Sequence_vs._lists

Последовательность использует от 5/6 до 4/3 раз больше места, чем эквивалентный список (при условии накладных расходов на одно слово на node, как в GHC). Если используются только операции deque, использование пространства будет близко к нижнему концу диапазона, потому что все внутренние узлы будут тройными. Тяжелое использование split и append приведет к последовательностям, использующим примерно то же пространство, что и списки. Подробнее:

  • список длины n состоит из n минус-узлов, каждый из которых занимает 3 слова.
  • последовательность длины n имеет приблизительно n/(k-1) узлы, где k - средняя арность внутренних узлов (каждая 2 или 3). Для каждого node есть указатель, размер и накладные расходы, а также указатель для каждого элемента, т.е. N (3/(k-1) + 1) слов.

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

Ответ 2

У меня есть еще один конкретный результат, чтобы добавить к вышеприведенному ответу. Я решаю уравнение Ланжевена. Я использовал List и Data.Sequence. В этом решении происходит множество вставок в конце списка/последовательности.

Подводя итог, я не видел никакого улучшения скорости, на самом деле производительность ухудшилась с помощью последовательностей. Более того, с Data.Sequence мне нужно увеличить память, доступную для Haskell RTS.

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