Структуры данных: containers и vector

Список это первое, что приходит в голову в Haskell, и часто это ошибка. Он прекрасен для последовательного прохода и ленивых потоков, но беспомощен на случайном доступе, поиске по ключу и склейке. Сегодня разберём рабочий набор структур из стандартных библиотек: Map, Set, IntMap, Seq из containers, HashMap из unordered-containers и плотный массив vector. И не просто перечислим API, а заглянем внутрь: из чего собрано сбалансированное дерево, что такое PATRICIA-trie на битах ключа, почему персистентная вставка стоит O(log n), а не O(n), и как stream fusion схлопывает конвейер в один цикл без промежуточных массивов. Цель та же, что в уроке 31: научиться выбирать структуру по цене операций и уметь эту цену обосновать.

Идея

В уроке 03 список был главным носителем данных, и для обучения это правильно: на нём удобно показывать рекурсию, паттерн-матчинг и свёртки. Но [a] это не универсальная коллекция, а односвязный список cons-ячеек. У такой формы ровно одна дешёвая операция: добавить элемент в голову за O(1). Всё остальное (взять i-й элемент, узнать длину, дописать в конец, склеить два) стоит O(n), потому что приходится пройти по ссылкам от начала.

Профессиональный Haskell не борется со списком, а выбирает структуру под задачу. Под поиск по ключу есть дерево и хеш-таблица. Под последовательность с двумя концами есть finger tree. Под плотный числовой массив со случайным доступом есть vector. У каждой свой профиль сложности, и работа инженера это сопоставить профиль операции профилю структуры.

Сквозная нить всего урока одна, и она объясняет почти все компромиссы: эти структуры персистентны. Раз значения в Haskell неизменяемы, вставка не правит структуру на месте, а возвращает новую версию, а старая остаётся жить. Звучит дорого, но дёшево: за счёт разделения структуры новая версия копирует только то, что лежит на пути изменения, и переиспользует всё остальное. Этот приём мы разберём руками на виджете, и он же объяснит, почему у дерева вставка O(log n), а не O(n).

Начнём с инструмента выбора. Покрути виджет: задай задачу и посмотри, какая структура её закрывает и почему, а потом разберём каждую по отдельности и заглянем внутрь.

Дальше идём сверху вниз по этой таблице: сначала ассоциативные структуры (Map, IntMap, HashMap), потом последовательности (Seq, vector), а в конце соберём чек-лист “когда список это ошибка”. И в каждой остановимся на том, из чего она физически собрана.

Чем платит список

Прежде чем хвалить альтернативы, честно посчитаем цену списка, чтобы было с чем сравнивать. Тип [a] это рекурсивный ADT из урока 06:

data [] a = [] | a : [a]    -- условно: пустой либо голова и хвост

Каждый : это cons-ячейка в куче: два указателя, на голову и на хвост. Отсюда два следствия. Первое, алгоритмическое: чтобы добраться до i-го элемента, надо пройти i ссылок, поэтому xs !! i, length, last это O(n). Второе, более коварное, про железо: cons-ячейки разбросаны по куче и связаны указателями, поэтому проход по списку это прыжки по случайным адресам, мимо кэша процессора. Плотный массив лежит подряд и читается на порядок быстрее даже при той же асимптотике.

И есть отдельная ловушка склейки, о которой стоит помнить со времён урока про строки. (++) копирует левый аргумент целиком:

xs ++ ys    -- O(длина xs), правый аргумент не трогается

Поэтому накопление списка через повторный acc ++ [x] в цикле это квадрат: на каждом шаге копируется весь растущий acc. Та же болезнь, что у наивной склейки String из урока 31, и лечится так же, накоплением в голову с разворотом в конце, либо структурой, у которой добавление в конец дёшево (Seq, Builder). Запомни диагноз: повторный ++ справа это всегда красный флаг.

Где список при этом по-прежнему лучший выбор, разберём в конце. А пока посмотрим, чем его заменяют, когда профиль операций не совпал.

Map и Set: сбалансированное дерево

Data.Map это ассоциативный массив, отображение ключей в значения, а Data.Set это то же дерево без значений, просто множество ключей. Обе живут в пакете containers и устроены как сбалансированное дерево поиска.

Заглянем внутрь. Узел Map в containers это:

data Map k a
  = Bin {-# UNPACK #-} !Size !k a !(Map k a) !(Map k a)
  | Tip

type Size = Int

Bin хранит размер поддерева, ключ, значение и две ветки, Tip это пустое дерево. Два момента уже многое объясняют. Размер Size лежит прямо в узле и распакован через {-# UNPACK #-} (это та самая распаковка из урока 32: не указатель на боксированный Int, а честное машинное слово в узле). Поэтому Map.size это O(1), просто читаем поле корня. Запомни эту деталь, у IntMap ниже будет иначе.

Балансировка здесь это дерево с балансировкой по весу (bounded balance, схема Адамса). Инвариант простой: вес одного поддерева не может быть больше чем в delta = 3 раза тяжелее другого. Как только вставка или удаление нарушает это правило, дерево делает вращение, а параметр ratio = 2 решает, хватит ли одинарного вращения или нужно двойное. Размер в каждом узле нужен ровно для этой проверки, его сравнивают на каждом шаге вверх по дереву. Итог: высота держится около log n, и базовые операции стоят логарифм:

import qualified Data.Map.Strict as Map

m :: Map.Map String Int
m = Map.fromList [("a", 1), ("b", 2), ("c", 3)]

Map.lookup "b" m          -- O(log n)
Map.insert "d" 4 m        -- O(log n), возвращает новую карту
Map.delete "a" m          -- O(log n)
Map.size m                -- O(1), размер лежит в корне

Ключи сравниваются через Ord, поэтому при поиске они форсируются до WHNF (иначе нечего сравнивать). А вот значения это снова развилка строгости из урока 32, и это самая частая ошибка с Map:

• Data.Map.Lazy кладёт в значение thunk и не считает его при вставке.
• Data.Map.Strict форсирует значение до WHNF при вставке.

Для счётчиков и накопителей бери Data.Map.Strict, иначе insertWith (+) накопит башню отложенных сложений в значении, как мы видели в уроке 32. Структура дерева у обоих вариантов одна, разница только в строгости по значению.

Чем Map бьёт хеш-таблицу, так это упорядоченностью. Ключи лежат в дереве по порядку, поэтому почти бесплатны операции, которых у HashMap нет вовсе:

Map.lookupMin m              -- наименьший ключ, O(log n)
Map.lookupGE "b" m           -- первый ключ >= "b", O(log n)
Map.foldrWithKey f z m       -- обход в порядке ключей, O(n)
fst (Map.split "b" m)        -- всё, что меньше "b", O(log n)

Диапазонные запросы, ближайший ключ, упорядоченный обход, разрезание по границе: всё это про Map и Set, и невозможно (или дорого) на хеше. Когда нужен порядок, выбор сделан.

IntMap и IntSet: trie на битах ключа

Если ключ это Int (идентификатор, индекс, хеш), есть структура заметно быстрее общего Map: Data.IntMap. Она не сравнивает ключи через Ord, а смотрит на их биты, и это меняет устройство целиком.

data IntMap a
  = Bin {-# UNPACK #-} !Prefix {-# UNPACK #-} !Mask !(IntMap a) !(IntMap a)
  | Tip {-# UNPACK #-} !Key a
  | Nil

Это big-endian PATRICIA-trie: дерево, где путь к ключу диктуют его биты, а не цепочка сравнений. Узел Bin хранит общий префикс группы ключей (Prefix) и бит, по которому она расщепляется (Mask); лист Tip хранит сам ключ и значение. Поиск спускается по битам ключа от старших к младшим, поэтому глубина ограничена числом бит в слове:

import qualified Data.IntMap.Strict as IntMap

IntMap.lookup 42 im       -- O(min(n, W)), W это разрядность слова (64)
IntMap.insert 7 'x' im    -- O(min(n, W))

Практически это близко к константе: не больше 64 шагов на 64-битной машине. Но настоящая сила IntMap это слияния. Объединить или пересечь две карты можно за один параллельный спуск по обоим деревьям, сравнивая префиксы:

IntMap.union im1 im2          -- очень быстро, идёт по битам префиксов
IntMap.intersectionWith f a b -- то же самое

Если ты часто сливаешь карты с целыми ключами (агрегация по id, объединение индексов), IntMap обгоняет Map в разы.

Две детали, которые легко забыть. Первая: IntMap.size это O(n), размер нигде не хранится, в отличие от Map. Тот самый контраст, ради которого я просил запомнить UNPACK !Size выше. Вторая, про Data.IntSet: его листья хранят не отдельные ключи, а битовую маску над блоком из 64 последовательных чисел. Поэтому плотное множество целых (диапазон id, набор флагов) занимает в IntSet считанные слова: один Word покрывает 64 значения сразу. Для Set Int такой компактности нет и близко.

Правило простое: ключ это Int или то, что в него отображается (enum, маленький constructor), бери IntMap/IntSet, а не общий Map/Set.