Haskell: списки, массивы, векторы, последовательности

Question

Я изучаю Haskell и читаю пару статей, касающихся различий в производительности списков Haskell и (вставьте свой язык) массивов.

Будучи учеником, я, очевидно, просто использую списки, даже не задумываясь о разнице в производительности. Недавно я начал исследовать и нашел множество библиотек структур данных, доступных в Haskell.

Может кто-нибудь объяснить, пожалуйста, разницу между списками, массивами, векторами, последовательностями, не углубляясь в теорию информатики структур данных?

Кроме того, есть ли общие шаблоны, в которых вы бы использовали одну структуру данных вместо другой?

Существуют ли какие-либо другие формы структур данных, которые мне не хватает и которые могут быть полезны?

Answer 1

Lists Rock

Безусловно, самая удобная структура данных для последовательных данных в Haskell - это List

 data [a] = a:[a] | []

Списки дают вам cons (1) минусов и сопоставление с образцом. Стандартная библиотека, и в этом отношении прелюдия, полна полезных функций списка, которые должны засорить ваш код (foldr,map,filter). Списки являются постоянными, то есть чисто функциональными, что очень приятно. Списки на Haskell на самом деле не являются "списками", потому что они являются коиндуктивными (другие языки называют эти потоки), поэтому такие вещи, как

ones :: [Integer]
ones = 1:ones

twos = map (+1) ones

tenTwos = take 10 twos

работать чудесно. Бесконечные структуры данных рок.

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

С другой стороны

Первая проблема со списками состоит в том, чтобы индексировать их (!!) занимает ϴ(к) время, что раздражает. Кроме того, добавления могут быть медленными ++, но ленивая модель оценки Haskell означает, что они могут рассматриваться как полностью амортизированные, если они вообще случаются.

Вторая проблема со списками состоит в том, что они имеют плохую локальность данных. Реальные процессоры получают высокие константы, когда объекты в памяти не расположены рядом друг с другом. Итак, в C++ std::vector имеет более быстрый "snoc" (помещающий объекты в конец), чем любая структура данных связанного чистого списка, о которой я знаю, хотя это не является устойчивой структурой данных, поэтому менее дружественной, чем списки на Haskell.

Третья проблема со списками состоит в том, что они имеют низкую эффективность использования пространства. Связки дополнительных указателей увеличивают ваше хранилище (постоянным фактором).

Последовательности являются функциональными

Data.Sequence внутренне основан на пальцах (я знаю, вы не хотите знать это), что означает, что у них есть некоторые хорошие свойства

1. Чисто функциональный. Data.Sequence это полностью постоянная структура данных.
2. Черт возьми быстрый доступ к началу и концу дерева. ϴ(1) (амортизируется), чтобы получить первый или последний элемент или добавить деревья. В списках вещей быстрее всего, Data.Sequence самое большее постоянно медленнее.
3. ϴ(log n) доступ к середине последовательности. Это включает в себя вставку значений для создания новых последовательностей
4. API высокого качества

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

Массивы не для слабонервных

Массивы являются одной из наиболее важных структур данных в CS, но они не очень хорошо вписываются в ленивый чистый функциональный мир. Массивы обеспечивают ϴ(1) доступ к середине коллекции и исключительно хорошую локальность данных / постоянные факторы. Но, поскольку они не очень хорошо вписываются в Haskell, их неудобно использовать. На самом деле в текущей стандартной библиотеке есть множество различных типов массивов. К ним относятся полностью персистентные массивы, изменяемые массивы для монады ввода-вывода, изменяемые массивы для монады ST и неупакованные версии описанного выше. Для более подробной информации проверьте вики на Haskell

Вектор - "лучший" массив

Data.Vector Пакет обеспечивает все совершенство массива, на более высоком уровне и более чистый API. Если вы действительно не знаете, что делаете, вы должны использовать их, если вам нужна производительность, подобная массиву. Конечно, некоторые предостережения все еще применимы - изменяемый массив, такой как структуры данных, просто не воспроизводится в чистых ленивых языках. Тем не менее, иногда вы хотите, чтобы производительность O(1), и Data.Vector дает вам в удобной упаковке.

У вас есть другие варианты

Если вам просто нужны списки с возможностью эффективной вставки в конце, вы можете использовать список различий. Лучший пример того, как списки портят производительность [Char] который прелюдия псевдоним как String, Char списки удобны, но, как правило, работают в 20 раз медленнее, чем строки C, поэтому не стесняйтесь использовать Data.Text или очень быстро Data.ByteString, Я уверен, что есть другие ориентированные на последовательность библиотеки, о которых я сейчас не думаю.

Заключение

90+% времени, когда мне нужен последовательный сбор в списках Haskell, являются правильной структурой данных. Списки подобны итераторам, функции, которые используют списки, могут легко использоваться с любой из этих других структур данных, используя toList функции они идут с. В лучшем мире прелюдия была бы полностью параметрической относительно того, какой тип контейнера он использует, но в настоящее время [] засоряет стандартную библиотеку. Таким образом, использование списков (почти) везде где угодно.
Вы можете получить полностью параметрические версии большинства функций списка (и использовать их благородно)

Prelude.map                --->  Prelude.fmap (works for every Functor)
Prelude.foldr/foldl/etc    --->  Data.Foldable.foldr/foldl/etc
Prelude.sequence           --->  Data.Traversable.sequence
etc

По факту, Data.Traversable определяет API, который является более или менее универсальным для любой вещи, подобной списку.

Тем не менее, хотя вы можете быть хорошими и писать только полностью параметрический код, большинство из нас не так и используют список повсеместно. Если вы учитесь, я настоятельно рекомендую вам тоже.

---

РЕДАКТИРОВАТЬ: на основе комментариев я понимаю, что я никогда не объяснял, когда использовать Data.Vector против Data.Sequence, Массивы и векторы обеспечивают чрезвычайно быструю индексацию и срезы, но являются принципиально переходными (обязательными) структурами данных. Чистые функциональные структуры данных, такие как Data.Sequence а также [] Позвольте эффективно создавать новые значения из старых значений, как если бы вы изменили старые значения.

  newList oldList = 7 : drop 5 oldList

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

  newSequence newValue oldSequence = Sequence.update 3000 newValue oldSequence 

создаст новую последовательность с newValue на месте его 3000 элемент. Опять же, это не разрушает старую последовательность, она просто создает новую. Но он делает это очень эффективно, принимая O(log(min(k,kn)), где n - длина последовательности, а k - индекс, который вы модифицируете.

Вы не можете легко сделать это с Vectors а также Arrays, Они могут быть изменены, но это действительно обязательное изменение, и поэтому не может быть сделано в обычном коде на Haskell. Это означает, что операции в Vector пакет, который делает модификации как snoc а также cons должен скопировать весь вектор, так что возьмите O(n) время. Единственным исключением является то, что вы можете использовать изменяемую версию (Vector.Mutable) внутри ST монада (или IO) и делайте все свои модификации так же, как на императивном языке. Когда вы закончите, вы "заморозите" свой вектор, чтобы превратиться в неизменную структуру, которую вы хотите использовать с чистым кодом.

Я чувствую, что вы должны по умолчанию использовать Data.Sequence если список не подходит. использование Data.Vector только в том случае, если ваш шаблон использования не предполагает внесения множества изменений или если вам требуется чрезвычайно высокая производительность в монадах ST/IO.

Если все это говорить о ST Монада оставляет вас в замешательстве: все больше причин оставаться чистыми, быстрыми и красивыми Data.Sequence,