Singly resizable array

Тема сегодняшнего поста - динамические массивы. Динамический массив, это одна из наиболее часто используемых структур данных. Рассмотрим простой динамический массив, имеющий две операции - добавление элемента в конец массива и поиск элемента массива по индексу. Наивный алгоритм, последовательно добавляющий множество элементов в массив, каждый раз полностью копируя его содержимое, будет иметь квадратичную сложность.

Естественно, операцию push_back в реальной жизни реализуют с помощью метода удвоения. Алгоритм, последовательно добавляющий множество элементов в массив методом удвоения, будет иметь линейную, амортизированую сложность. По памяти все тоже неплохо, в любой момент времени, наш динамический массив будет иметь capacity <= N*2, где N - количество элементов массива, а capacity - его вместительность.

К сожалению, в реальности, все несколько хуже. Во первых, во время удвоения нам нужно выделить память под новый массив и скопировать в него содержимое старого, следовательно, расходы по памяти составят 3*N. Во вторых, постоянное пересоздание массива приводит к фрагментации памяти, так как для выделения памяти под массив при очередном удвоении размера, менеджер памяти не может использовать память, освобожденную динамическим массивом ранее. Именно по этому, во многих реализациях, массив увеличивают не в два раза, а в меньшее число раз, например в полтора. В третьих, данный алгоритм, даже имея сложность O(N), имеет достаточно большую коснтанту, так как периодически перезаписывает большие участки памяти.

Существует множество способов решения этих проблем. Один из этих способов очень похож на метод удвоения: вместо того, чтобы хранить элеметы в одном большом массиве, можно хранить их в последовательности массивов меньшего размера, при этом первый подмассив должен хранить один элемент, а каждый следующий - в два раза больше чем предыдущий. Для поиска i-го элемента массива нам нужно выполнить две операции: определить позицию старшего бита индекса - k и вычислить значение b, равное значению индекса без старшего бита. При этом значение k будет номером подмассива, а b - индексом элемента в этом подмассиве. Алгоритм добавления элемента в такой динамический массив достаточно очевиден, поэтому я его не буду описывать. Данный подход решает две проблемы из трех. Он не переписывает кучу памяти и не вызывает фрагментацию, но он по прежнему приводит к потерям памяти порядка O(N). В простыне кода в конце поста, данный алгоритм реализован в классе ResizableArray.

Существует еще один алгоритм, позволяющий решить все три проблемы, он хорошо описан в этой статье - http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf. Это по сути дальнейшее развитие предыдущего алгоритма, подмассивы(суперблоки) мы делим на множество блоков, каждый из которых имеет размер Sqrt(N), где N - размер суперблока, причем в каждом суперблоке у нас будет Squrt(N) блоков. Подобная схема позволяет сократить потери памяти до O(Sqrt(N)), при этом операции добавления и поиска элемента по индексу, будут иметь сложность O(1), как и прежде. Данный алгоритм реализован в классе ResizableArrayV2.

Класс ResizableArray примерно в 2.5 раза быстрее нежели std::vector при добавлении большого количества элементов, в 3.5 раза медленнее вектора при чтении и имеет ровно такие же потери памяти. Класс ResizableArrayV2 примерно в полтора раза быстрее вектора при добавлении элементов, в 4.5 раза медленнее при чтении, но зато он обеспечивает очень низкий, по сравнению с вектором, уровень потерь памяти. Нужно также добавить, что код практически не оптимизирован (я только цикл для вычисления индекса старшего бита равзернул), так-что ситуация может быть несколько лучше.

Вот собственно сам код (ни разу не production качества, имейте ввиду):