|
Динамический массив. Принцип работыКурс по структурам данных: https://stepik.org/a/134212 Мы продолжаем курс по структурам данных. На этом занятии речь пойдет о динамических массивах. Что это такое? На данный момент мы с вами уже хорошо знаем, что из себя представляет и как работает статический массив. Но у него есть один существенный недостаток – неизменяемое число элементов. Поэтому, когда создается статический массив, программист должен как то решить, сколько элементов он должен иметь. Далеко не всегда можно указать разумное значение. Чтобы как то выйти из этой ситуации в мире программирования появилась более гибкая структура данных тоже в виде массива, но с изменяемым (увеличивающимся) числом элементов. Такие массивы получили название динамические. Приведу один простой пример их использования. Предположим, мы просматриваем файловую систему и сохраняем имена файлов в каждом каталоге. Очевидно, число файлов может варьироваться от нескольких десятков до нескольких тысяч. Если воспользоваться статическим массивом, то придется задавать число элементов, скажем, в 10 000. И это приведет к неоправданному расходу памяти. Гораздо лучше взять динамические массивы с начальным размером в 100 элементов. А, затем, по мере необходимости, увеличивать этот размер. Тогда память будет расходоваться куда экономнее.
Структура динамического массиваДавайте теперь посмотрим, как можно организовать массив с изменяемым числом элементов. Для этого воспользуемся обычным массивом с некоторым начальным размером, допустим, в 10 элементов:
Реальный размер массива называют физическим, а число записанных в него данных – логическим. Чтобы программно оперировать этими величинами вводят две вспомогательные переменные, например: currentLength = 7 maxCapacity = 10 Переменная currentLength содержит индекс следующего добавляемого в массив значения, а также определяет число уже записанных данных. Переменная maxCapacity равна максимальному числу элементов, который имеет массив dar. Добавление и вставка элементов в массивТеперь предположим, что мы хотим добавить новое значение в конец этого массива. Так как все элементы в массивах должны следовать строго друг за другом с самого начала без каких-либо пропусков, то новое значение нам следует записать в ячейку с индексом currentLength: dar[currentLength] = 8 и увеличить значение currentLength на единицу: currentLength += 1
С точки зрения О большого скорость этой операции составляет O(1). Но это добавление в конец. А что если нам нужно вставить новое значение, скажем, после пятерки. Как в этом случае будет выглядеть алгоритм? В действительности, так же, как и в обычном статическом массиве. Необходимо сдвинуть значения 6, 7, 8 вправо на один элемент и на прежнее место шестерки записать вставляемое значение. Переменная currentLength увеличивается на единицу:
Вычислительная сложность этой операции с точки зрения О большого составляет O(n), где n – физический размер динамического массива. Изменение физического размера динамического массиваЯ думаю эти простые операции добавления и вставки новых значений в массив, пока есть свободное место, вы себе хорошо представляете. Но что делать, когда все элементы заняты, а мы хотим добавить еще один?
Было бы неплохо выделить следующие несколько байт под новый элемент массива и записать туда требуемое значение.
При этом вся выделенная под массив область памяти должна быть непрерывной. К сожалению, в общем случае, такую операцию выполнить не получится, т.к. следующие ячейки памяти могут быть заняты другими процессами. Поэтому приходится идти несколько более сложным, но более надежным путем. Выделяется память под новый статический массив длиной в два, три раза больший первоначального (чаще всего удваивают физический размер). В этот новый массив копируют все значения из прежнего массива, записывают новое значение и увеличивают переменную currentLength:
Вычислительная сложность этой операции с позиции О большого составляет O(n), где n – физический размер динамического массива. Далее, если все новые элементы также будут заполнены, то операция удвоения физического размера массива повторяется. Это принцип работы динамического массива. Здесь у вас может возникнуть вопрос, зачем под новый массив выделять в несколько раз больше элементов, чем в прежнем? Почему бы не увеличить его просто на один элемент (или требуемое число элементов)? Зачем удваивать? Ответ прост. Если нам не хватило физического размера прошлого массива, то скорее всего не хватит и для нового массива с одним дополнительным элементов. А, значит, операцию выделения памяти и копирования всех прежних значений в новый массив снова придется повторять. Это приводит к неоправданному расходу процессорного времени. Логичнее сделать размер массива сразу в два раза больше и минимизировать вероятность создания новых массивов с большими размерами. Удаление элементов в динамическом массивеИтак, с добавлением новых значений и изменением физического размера динамического массива мы с вами разобрались. Осталось сказать пару слов про удаление значений. Здесь все намного проще, т.к. физический размер массива при этом не меняется. Поэтому здесь все абсолютно так же, как и в случае со статическими массивами. Предположим, нам нужно исключить последнее значение. Нет ничего проще. Достаточно уменьшить значение currentLength на единицу и все. Последнего значения теперь как бы нет. Вычислительная сложность этой операции составляет O(1).
Немного сложнее выполняется удаление остальных значений (не последнего). В этом случае нам нужно сдвинуть все элементы правее удаляемого влево на одну позицию и не забыть уменьшить значение currentLength на единицу:
Сложность этой операции составляет O(n). Еще раз отмечу, что при удалении значений физический размер массива не меняется, даже если ранее он увеличивался. ЗаключениеДавайте подведем итог этого занятия. Динамический массив – это массив, который может менять число своих элементов в процессе работы программы. Динамические массивы реализуются на основе обычных статических массивов и хранят данные в непрерывной области памяти. Благодаря этому доступ к произвольному элементу выполняется за фиксированное время с вычислительной сложностью O(1). Если начального физического размера динамического массива недостаточно, то создается новый массив размером в несколько раз больше предыдущего с копированием всех прежних значений. Часто делают удвоение размеров. Операции добавления и удаления значений элементов в динамическом массиве выполняются почти так же, как и в статических массивах. Разница только в том, что при добавлении новых значений может дополнительно происходить увеличение физического размера массива. При этом вычислительная сложность операций вставки/удаления составляет O(n), где n – общий размер динамического массива. На следующем занятии мы продолжим эту тему и увидим, как реализуются динамические массивы на языках Python и С++. Курс по структурам данных: https://stepik.org/a/134212 Видео по теме |
