Разреженные структуры данных02.02.2024 00:15

Разреженное небо над Дианой и Конём Боджеком

Когда-то я писал пост про различные интересные структуры данных. Среди них был т.н. sparse set. Там мы описали его в общих чертах, опустив некоторые детали (которыми позже статья была дополнена). Но кроме sparse set существуют и другие разреженные структуры данных! На них сегодня и посмотрим :)

Sparse Array (Sparse Matrix)

Когда мы говорим про разреженные массивы и матрицы, мы чаще всего имеем в виду нехранение элементов с некоторым значением (например 0 или None/null). Например, давайте глянем на какой-нибудь вектор (в математическом смысле):

$A = \begin{pmatrix} 1 & 0 & 0 & 4 & 0 & 2 & 0 & 0 \end{pmatrix}$

Или на матрицу:

$B = \begin{pmatrix} 1 & 1 & 0 & 0 & 0 \\ 4 & -2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ \end{pmatrix}$

Как в векторе А, так и в блочной матрице В, большинство элементов нулевые. Мы можем сэкономить в таких случаях, если будем хранить только ненулевые значения. Самые понятные и простые решения — это трансформировать в ассоциативный массив:

$f: i -> value, для\ массива \\ f: (i, j) → value, для\ матрицы» src=«https://habrastorage.org/getpro/habr/upload_files/0d1/084/5b8/0d10845b874af9daba4fa0744bbf8ccc.svg» /></p> <p>Или трансформировать в несколько массивов: в случае разреженного массива — один на координату и один на значение;, а в случае разреженной матрицы — два на координаты и один на значение. Например для матрицы выше подобная трансформация может выглядеть так: </p> <p><img alt=$

Или трансформировать в список (одно-/двусвязный), где нода содержит сразу все координаты и значения. Не суть важно. Концепция везде одна и та же.

Подобные подходы помогают экономить время и память при вычислениях с некоторыми типами матриц: например, в случае блочных/иногда треугольных/диагональных. Есть готовые пакеты для python, реализующие эту логику (scipy.sparse).

Тут конечно нет каких-то цепляющих идей. Но дальше интереснее!

Sparse List

Sparse list разрежен в другом смысле. В каком? Я пока не скажу.

Давайте посмотрим на двусвязный список. Мы можем делать модифицирующие операции (вставка, удаление) за O (1) и не модифицирующие (обход в любую сторону) за O (n). И для всего этого нам нужна одна лишь нода списка (не нужно искать соседнюю, как в случае односвязного спи. С другой стороны, мы вынуждены хранить по два указателя на каждую ноду (в современных реалиях это чаще всего целых 16 байт!). Можно ли как-то не сильно ухудшить скорость работы, при этом уменьшив потребление памяти?

Да! А что, если мы сделаем полторасвязный список? Ну то есть связность у него что-то между единицей и двойкой. Достичь этого мы можем имея в среднем односвязный список, в котором некоторые ноды будут двусвязными.

То есть у нас есть некоторое подмножество нод с двумя указателями, один из которых указывает на предыдущую двусвязную ноду, а другой — на следующую в списке ноду. Т.к. размер односвязного «подсписка» конечен и фиксирован заранее, любая операция всё ещё занимает O (1), прямо как у двусвязного списка (конечно, с сильно выросшей константой). Вдумчивый читатель может заметить, что можно наделать вставок в один односвязный подсписок и все наши асимптотики сломаются! Но никто не мешает нам поддерживать размеры этих самых односвязных подсписков не больше некоторого размера (на картинке 3, если считать двусвязные ноды на концах). То есть, если вы уже вставили односвязную ноду после односвязной, то сделайте её двусвязной и поправьте ссылки у двусвязных соседей.

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

Собственно из-за того, что у вас двусвязные ноды находятся на некотором расстоянии друг от друга, он и называется разреженным.

Как подобрать этот самый «коэффициент разреженности»? Хорошего ответа нет. Эмпирическим путём можно догадаться, что писать подобную структуру сильно проще (да и константа меньше), если ноды просто чередуются. Особенно обходить список в обратном порядке будет сильно дешевле, если двусвязные ноды встречаются чаще.

А как память экономить? С точки зрения написания кода может возникнуть желание использовать что-то вроде union/std::variant, но такие типы будут иметь размер максимального из объектов. То есть в итоге мы всё ещё имеем решение, сравнимое с двусвязным списком.

К сожалению, красиво никак. Вам в любом случае нужно уметь работать с нодами различного размера (тут может помочь type-erasure в каком-то виде). Плюс нужно располагать указатель на предыдущую ноду последним в структуре, чтобы брать указатель на следующую ноду/значение из списка было удобнее. Но зато задача определить, какой тип у ноды, несложная. Т.к. указатели выровнены в памяти, у вас всегда есть несколько нулевых младших битов. Как раз у указателя на следующий элемент и можно забрать один из этих битов и установить в 1, если нода имеет ещё и обратный указатель (важно не забыть установить бит в ноль перед тем, как обращаться по этому указателю к следующей ноде). А ещё начинаются проблемы, когда вы хотите переместить ноду из одного списка в другой: раз она может поменять свой тип, вам необходимо будет заново освободить/выделить память. Можно при желании в двусвязных нодах вообще не хранить значения, но проблемы почти никуда не уходят + непонятно, насколько мы тут вообще что-то экономим.

Вот ссылка на реализацию, если очень интересно повтыкать.

Sparse Deque (sparque)

Sparse deque недавно выложил один из пользователей reddit. Мы пробежимся по некоторым основам, чтобы понять, как же он работает.

Для начала нам нужно понять, что такое B-дерево (почитать можно тут). B-дерево, грубо говоря, — это m-арное дерево поиска. То есть каждая нода может хранить несколько значений и соответственно несколько детей. Это позволяет делать стандартные для бинарных деревьев поиска операции, но с логарифмом по бОльшему основанию. А ещё локальность данных помогает обходить элементы быстрее. Конечно, хотя глубина дерева становится меньше, но не стоит забывать и про возникающую константу, связанную с бОльшим количеством сравнений. Выглядит оно как-то так:

Далее у нас бывают B±деревья. Это такие B-деревья, имитирующие ассоциативный массив. Они хранят значения только в листьях, а в остальных вершинах хранятся только копии ключей (получается что-то вроде ассоциативного массива):

В листьях B±деревьев обычно хранят указатель на следующий лист, что позволяет вам обходить все элементы вашего дерева за линейное время без подъёмов и спусков по дереву.

И последний кусочек, это counted B-дерево — B-дерево, в котором для каждого ребёнка мы храним размер его поддерева:

Вот sparque — это counted B±дерево. С оговорочкой, что если в каноническом B±дереве у нас есть и ключи, и значения, тут мы храним только значения (в листьях). В остальных вершинах у нас остаются только размеры дочерних поддеревьев и собственно сами указатели на эти поддеревья. Так что на нижнем уровне (в листьях) наша структура данных выглядит как список блоков, в каждом из которых хранится несколько значений. Чем не deque! Правда каждый блок в листе это что-то вроде массива, в который можно эффективно вставлять с обоих концов, так что теперь некоторые операции становятся быстрее.

СтОят они у нас так:

обращение по индексу O (log_m (n)) — так как теперь нам, используя размеры поддеревьев, надо спустится от корня дерева до его листа. Это дольше, чем в стандартном std::deque с его O (1), но является в некотором роде трейдофом для ускорения других операций;
автор утверждает, что вставка/удаление в начало/конец — O (1). Звучит сомнительно, т.к., кроме вставки, нужно ещё пересчитать от листа до корня все размеры поддеревьев. Что он и делает в push_back в функции update_counts_plus. Но может я что-то не понял ¯\_(ツ)_/¯
вставка удаление в случайном месте — O (m), где m — количество значений в блоке листа;
итерирование — O (n).

Память O (n).

Почему автор решил назвать эту структуру разреженной, достоверно не известно.

Тут есть бенчмарки от автора в сравнении с другими контейнерами. А тут — реализация.

Sparse Set

Вспомним, что же такое sparse set.

Sparse set позволяет выполнять всё те же операции, что и другой знакомый вам set. Но с точки зрения он всё же ближе к std::vector/std::bitset. Для начала нам нужно два массива и размер:

template 
struct SparseSet {
	int size_ = 0;
	int dense_[R];
	int sparse_[R];
};

dense_ это массив значений. sparse_ же хранит индекс значения в dense_, т.е. если dense_[i] = v, то sparse_[v] = i (вместо индекса можно хранить указатель). Тогда добавление выглядит так:

void Add(int val) {
	dense_[n] = val;
	sparse_[val] = size_;
	++size_;
}

Для пущего понимания посмотрим на пример. Предположим, мы вставили в наш сет следующие значения: 3, 2, 5, 1, 0.

При этом size_ равен 5. В пустых клетках у нас ничего лежит.

Теперь вы можете проверять наличие в своём сете:

bool Contains(int val) {
	return sparse_[val] < size_ && dense_[sparse_[val]] == val;
}

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

sparse_[2] < 5 && dense_[sparse_[2]] == 2

Что эквивалентно

1 < 5 && 2 == 2

Двойка в сете!

Для значений, которые в нашем сете не находятся, мы проверим мусорные ячейки (если ранее тем ничего не лежало) и вряд ли наше условие пройдёт (там всё-таки мусор).

Если мы хотим удалить некоторый элемент, то тут нам нужно сделать маленькое приседание. Предположим, что мы хотим удалить 0. Тут всё просто. Нам достаточно уменьшить размер и этот ноль затрётся при следующей вставке. А если мы хотим удалить элемент, который не находится в конце dense_? Тогда нам нужно поменять соответствующий элемент в dense_ с последний и поддержать инвариант в sparse_. Для примера с удалением двойки:

Теперь можно спокойно уменьшить size_. В коде это будет выглядеть так:

 bool Remove(int i) {
   if (dense_[size_ - 1] != i) {
     int last_element = dense_[size_ - 1];
     dense_[sparse_[i]] = last_element;
     sparse_[last_element] = sparse_[i];
   }
   --size_;
 }

Ну и конечно, если мы хотим очистить всю структуру данных, нам достаточно сделать одно единственное действие:

void Сlear() { size_ = 0; }

Все операции (от создания до удаления) за O(1)!

Сверху ещё и элементы у вас лежат рядом в памяти, что позволяет использовать локальность данных при итерировании по сету.

Конечно, подобная структура имеет ограничения на максимальное значение, которая она может хранить. А ещё, если у вас сложные типы, при удалении вам всё же нужно будет повызывать деструкторы. Но это уже мелочи.

В folly есть довольно примитивная реализация. Они фиксируют размер, из-за чего теряется точка кастомизации. Но может кто-то их убедит, что так не надо?)

Конечно, можно делать массивы не статическими, а динамическими. И можно даже делать не только для числовых типов — с помощью хеширования! Правда, не любого. Т.к. по факту мы знаем всё возможное множество значений для числовых типов, то аналогичным свойством надо воспользоваться и при хешировании для произвольных объектов, дабы не было коллизий. В этом может помочь perfect hashing.

Sparse Map

Ладно. Sparse Map это пранк. Ничего интересного тут нет. Просто вместо значения в dense_ теперь мы храним пару (key, value), а sparse_ работает только с ключами.

Если интересно посмотреть на бенчмарки, можно глянуть тут.

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

Подписывайтесь или не подписывайтесь на мой канал про программирование и C++: t.me/thisnotes.