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

Question

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

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

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

Answer 1

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

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

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

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

Answer 2

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

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

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

1. Решение с List, занимает около 13,01 сек
2. Решение с Data.Sequence, занимает около 15,13 с