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

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

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

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

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

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 предоставляют интерфейс, очень похожий на итераторы в императивных языках (из-за лени). Итак, имеет смысл, что они широко используются.

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

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

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

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

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

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

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

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

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

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

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

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 

создаст новую последовательность с newValuefor вместо 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.