Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty

Определение

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

 

   

      @font-face {

        font-family: "Virgil";

        src: url("https://excalidraw.com/Virgil.woff2");

      }

      @font-face {

        font-family: "Cascadia";

        src: url("https://excalidraw.com/Cascadia.woff2");

      }

   

 

  4  8  15  16  23  3  41 8  9объёмразмербуферная зона

У динамического массива есть 3 параметра: размер, объём и буферная зона. При добавлении элементов в конец массива, они будут записываться в буферную зону. Увеличение размера происходит, пока размер массива меньше объёма, если размера не будет хватать, необходимо создать новый массив с большим объёмом.

Объём - состоит из массива и дополнительной буферной зоны.

Объём в динамическом массиве нужен, чтобы:

1. Быстро выполнять операции добавления в конец массива и удаления в конце массива;

2. Динамически изменять размер массива

Плюсы динамического массива

1. Быстрее работают операции добавления элемента в конец массива и удаления из массива.

Минусы динамического массива

1. Так как нужно хранить массив и буферную зону, это может потребовать больше памяти.

Пример кода

Реализация на C++

vector<int> - динамический массив. Чтобы он работал, нужно написать #include<vector>. В треугольные скобки ставится тип элементов в данном массиве.

Аннотация:
dynamic_array - динамический массив
data - указатель на память для элементов массива
size - количество элементов в массиве
capacity - вместимость массива
da_build - построение массива
base_capacity - исходная вместимость массива

struct dynamic_array {
    int *data;
    size_t size, capacity;  
};

dynamic_array da_build(size_t base_capacity = 8) {
    dynamic_array da;
    da.data = new int[base_capacity];
    da.capacity = base_capacity;
    da.size = 0;
    return da;
    
}

Реализация на Python

A = [] # пустой динамический массив
В = [1, 2, 3] # динамический массив размера 3, элементы 1 2 3

---

Добавление элемента в конец массива

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

 

   

      @font-face {

        font-family: "Virgil";

        src: url("https://excalidraw.com/Virgil.woff2");

      }

      @font-face {

        font-family: "Cascadia";

        src: url("https://excalidraw.com/Cascadia.woff2");

      }

   

 

  4  8  15  16  23  3  41 8  9объёмразмербуферная зона12

Таким образом, можно добавлять элементы в массив, пока есть буферная зона.

 

   

      @font-face {

        font-family: "Virgil";

        src: url("https://excalidraw.com/Virgil.woff2");

      }

      @font-face {

        font-family: "Cascadia";

        src: url("https://excalidraw.com/Cascadia.woff2");

      }

   

 

  4  8  15  16  23  3  41 8  912  13  14  19

Когда буферная зона закончилась, необходимо расширить объём массива, чтобы появилась новая буферная зона. Для этого нужно создать новый массив с большим объёмом, переписать из старого массива элементы в новый. Эта операция выполняется за $O(n)$.

Чем больше увеличим объём, тем меньше придётся пересчитывать объём, тем меньше ситуаций, когда скорость операции добавления в конец массива $O(n)$. Поэтому необходимо найти баланс увеличения размера и потребления памяти. Этот параметр называют фактор роста (Growth factor).

Чем больше фактор роста, тем меньше придётся пересчитывать размер динамического массива, тем быстрее он будет работать. Однако большой фактор роста приведёт к избыточной трате памяти.

 

   

      @font-face {

        font-family: "Virgil";

        src: url("https://excalidraw.com/Virgil.woff2");

      }

      @font-face {

        font-family: "Cascadia";

        src: url("https://excalidraw.com/Cascadia.woff2");

      }

   

 

  4  8  15  16  23  3  41 8  912  13  14  19объёмразмербуферная зона

У разных реализаций разный фактор роста, например у C++ он равен 2, у Python он $1.125 (n + (n >> 3))$, где $n$ - размер динамического массива.

Пример кода

Реализация на C++

Аннотация:
da_push_back - метод добавления элемента в конец массива
element - добавляемый элемент
capacity - вместимость массива
size - количество элементов в массиве
__da_resize - метод увелечения вместимости массива
da.data - указатель на память для элементов массива
new_capacity - новая вместимость массива
new_data - новый указатель на память для перезаписывания элементов старого массива

void da_push_back(DynamicArray &da, int element) {
    if (da.capacity == da.size)
        __da_resize(da, da.capacity * 2);
    da.data[da.size++] = element;
}

void __da_resize(DynamicArray &da, size_t new_capacity) {
    auto new_data = new int[new_capacity];
    for (int i = 0; i < da.size; ++i) {
        new_data[i] = da.data[i];
    }

    delete[] da.data;
    da.data = new_data;
    da.capacity = new_capacity;
}

Реализация на Python

В = [1, 2, 3]
B.append(99) # B = 1 2 3 99

---

Удаление элемента из конца массива

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

Например, удалим последний элемент из динамического массива.

 

   

      @font-face {

        font-family: "Virgil";

        src: url("https://excalidraw.com/Virgil.woff2");

      }

      @font-face {

        font-family: "Cascadia";

        src: url("https://excalidraw.com/Cascadia.woff2");

      }

   

 

  4  8  15  16  23  3  41 8  9объёмразмербуферная зона

После того, как удалится 9, динамический массив примет вид:

 

   

      @font-face {

        font-family: "Virgil";

        src: url("https://excalidraw.com/Virgil.woff2");

      }

      @font-face {

        font-family: "Cascadia";

        src: url("https://excalidraw.com/Cascadia.woff2");

      }

   

 

  4  8  15  16  23  3  41 8объёмразмербуферная зона

Если буферная зона станет слишком большой, то можно уменьшить буферную зону. Для этого нужно создать новый массив с меньшим объёмом, переписать из старого массива элементы в новый. Эта операция выполняется за $O(n)$.

Здесь также влияет фактор роста на работу динамического массива. Чем больше фактор роста, тем меньше придётся пересчитывать размер динамического массива, тем быстрее он будет работать. Однако большой фактор роста приведёт к избыточной трате памяти.

Пример кода

Реализация на C++

Аннотация:
da_pop_back - метод удаления элемента с конца массива
size - количетсво элементов массива

bool da_pop_back(DynamicArray &da) {
    if (da.size == 0)
        return false;
    --da.size;
    return true;
}

Реализация на Python

В = [1, 2, 3]
B.pop() # B = 1 2

---

Сложность операций в динамическом массиве:

1. Добавить элемент в конец - примерно $O(1)$

2. Удалить элемент из конца - примерно $O(1)$

3. Добавить элемент в начало или середину - $О(n)$

4. Удалить элемент из начала или середины - $O(n)$

Все операции, которые доступны со статическим массивом, работают и с динамическим массивом.

---

Фактор роста

В итоге, фактор роста - это коэффициент, определяющий насколько увеличивается (уменьшается) объём динамического массива при операции пересчитования памяти.

Чем он больше, тем меньше операций пересчитования памяти, тем быстрее динамический массив, тем ближе сложность добавления в конец / удаления из конца массива к $O(1)$. Такую сложность называют амортизированной.