No Image

Структура данных динамический массив

СОДЕРЖАНИЕ
0 просмотров
22 января 2020

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

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

Содержание

Поддержка в языках программирования [ править | править код ]

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

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

Реализация [ править | править код ]

Для массивов с возможностью динамического изменения размера при реализации приходится находить «золотую середину» между несколькими противоречивыми требованиями.

  1. Эффективность по памяти — реализация не должна приводить к существенному перерасходу памяти.
  2. Эффективность по производительности, которая включает в себя:
    • минимальные накладные расходы на изменение размера массива;
    • сохранение, по возможности, константного времени доступа на чтение/запись к элементам массива.
    • Совместимость с обычными статическими массивами на низком уровне. Например, необходимым условием для применения динамического массива в вызовах функций API операционной системы может быть обязательное размещение элементов массива в непрерывном блоке физической оперативной памяти в порядке, соответствующем индексации массива. Если такое требование не выполняется, динамические массивы окажется невозможно использовать в сочетании с низкоуровневым кодом.

    В зависимости от приоритета тех или иных требований выбирается отвечающий им способ реализации.

    Массивы переменной длины [ править | править код ]

    Реализация массивов переменной длины мало отличается от реализации обычных статических массивов. Массив элементов типа T переменной длины обычно хранится в непрерывном блоке оперативной памяти размером s i z e o f ( T ) ⋅ N <displaystyle sizeof(T)cdot N> , где N — число элементов, указываемое при описании (создании) массива. То есть описание массива переменной длины, фактически, просто маскирует динамическое выделение памяти. Разница может состоять в том, что (например, как в Си стандарта C99 и позже) массиву переменной длины выделяется память на стеке, как другим автоматическим переменным, в то время как типовой способ динамического выделения памяти (в Си — функция malloc ) выделяет память в куче. Кроме того, для массива переменной длины компилятор, как правило, автоматически генерирует код освобождения памяти при выходе объявленного массива из области видимости.

    Перемещение массива в памяти [ править | править код ]

    Наиболее распространённой для типичных процедурных компилируемых языков является реализация изменения размера массива путём перемещения его в динамической памяти.

    • Под массив выделяется фрагмент ОЗУ, размер которого больше требуемого т. н. логического размера (size или length). Количество элементов, которое фактически может быть размещено в этой памяти, называется ёмкостью (capacity) динамического массива. Текущая длина массива хранится в отдельном счётчике. Она может использоваться для определения текущего размера, а также для контроля выхода за границы массива, если язык поддерживает такой контроль. Таким образом, в действительности динамический массив — это массив фиксированного размера, в котором занята только часть ячеек.
    • Команда увеличения размера массива, если новый размер не превышает ёмкости, просто изменяет счётчик длины массива до нужного размера. С самим массивом никаких изменений при этом не происходит.
    • Команда увеличения размера, в которой новый размер превышает ёмкость, приводит к перемещению массива в памяти:
    1. выделяется новый фрагмент ОЗУ, размер которого превышает размер массива;
    2. содержимое массива копируется во вновь выделенную память;
    3. размер и ёмкость массива актуализируются;
    4. в служебной структуре, хранящей параметры массива, значение указателя на данные меняется на новое;
    5. запускается команда освобождения ранее выделенного под массив фрагмент ОЗУ; если язык поддерживает автоматическое управление памятью, то освобождение ранее выделенной под массив памяти остаётся за сборщиком мусора.
    • Команда уменьшения размера массива может приводить к перемещению его в памяти, если в результате её выполнения процент занятых ячеек в массиве падает ниже определённого значения. Перемещение при этом проводится по той же схеме, что и в случае команды увеличения массива.

    Данная реализация является наиболее эффективной по скорости доступа к уже выделенным ячейкам массива. Кроме того, она обеспечивает константное время доступа к любому элементу, независимо от его индекса. Однако дополнительные накладные расходы на операции изменения размера могут оказаться значительными. Величина этих расходов зависит от параметров алгоритма перемещения массива.

    • Начальная ёмкость и приращение ёмкости при увеличении размера. Может задаваться либо относительной величиной (определённая доля от логической длины массива), либо абсолютным приращением сверх требуемой длины массива. Чем больше эти параметры, тем позже, при том же режиме заполнения массива, потребуется следующее перемещение, но и тем больше памяти потенциально останется неиспользуемой. Расширение массива на любой постоянный коэффициент гарантирует, что вставка n-элементов займет O(n) времени, это означает, что каждая вставка занимает конкретное, определённое время. Численное значение этого коэффициента приводит к разным показателям: среднее время вставки операции составляет a/(a-1), в то время как число потраченных впустую ячеек составляет (a-1)n. Значение этой константы в различных приложениях и библиотеках может быть разным: во многих учебниках используют значение 2, но в реализации ArrayList языка Java используется коэффициент 3/2, в некоторых других случаях используют a=9/8.
    • Минимальная ёмкость. Обычно задаётся из соображений эффективности, чтобы не терять производительность при частых изменениях размеров небольших массивов. Практически её установка означает, что все динамические массивы размером менее минимальной ёмкости в действительности будут терять память.
    • Процент минимального заполнения массива. Определяет, когда будет происходить перемещение после сокращения размера массива. Чем больше эта величина, тем чаще при уменьшении размера массива будет происходить перемещение. Чем она меньше, тем больше памяти при уменьшении размера массива будет оставаться занятой, но не используемой.
    Читайте также:  Усилитель беспроводного сигнала asus rp n12

    Существуют различные оценки оптимальных величин для параметров алгоритма перемещения, но из общих соображений ясно, что ни один из способов их определения не гарантирует максимальной эффективности во всех случаях и для любого можно подобрать алгоритм работы с массивом, при котором перемещение будет неэффективным. Для компенсации негативных эффектов многие языки, поддерживающие динамические массивы, в командах увеличения/уменьшения массива имеют дополнительные параметры, позволяющие прямо управлять ёмкостью массива. Если программист заведомо знает, до каких размеров увеличится/уменьшится массив в результате той или иной операции, и как в дальнейшем будет происходить работа с массивом, он имеет возможность прямо указать требуемую конечную ёмкость в команде изменения размера, избежав таким образом большого количества бессмысленных перемещений.

    Другие динамические алгоритмы размещения [ править | править код ]

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

    Использование [ править | править код ]

    Динамические массивы используются для обработки наборов однородных данных, размер которых неизвестен точно на момент написания программы, но которые потенциально могут разместиться в доступной памяти. Без использования динамических массивов решение таких задач сводится к одной из стратегий:

    • выделение статического массива большого размера, заведомо достаточного для полного размещения данных;
    • использование статического массива в качестве буфера, в который данные загружаются частями;
    • применение иных динамических структур данных (например, списков).

    Первый вариант применим только когда размер набора данных меняется в небольшом, жёстко ограниченном диапазоне (например, в текстовой обработке ограничение в 1000 знаков на строку вполне приемлемо). В противном случае выбор маленького массива будет ограничивать функциональность программы, а большого (так, чтобы заведомо хватило для любых входных данных) приведёт к неэффективному расходованию памяти. Буферизация обработки усложняет алгоритм, а другие динамические структуры в задачах обработки больших последовательностей простых данных по эффективности не могут сравниться с массивом.

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

    • снижение скорости работы из-за накладных расходов на изменение размера динамического массива;
    • потенциальное снижение надёжности: при экстремально большом объёме входных данных попытка увеличить массив до соответствующих размеров может привести к внезапному существенному замедлению или даже отказу программы из-за недостатка свободной памяти.

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

    Примеры [ править | править код ]

    Паскаль [ править | править код ]

    Динамические массивы поддерживаются Delphi, FreePascal, но не Turbo Pascal.

    Си [ править | править код ]

    В самом языке Си нет динамических массивов, но функции стандартной библиотеки malloc , free и realloc позволяют реализовать массив переменного размера:

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

    Многомерный динамический массив может быть создан как массив указателей на массивы:

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

    Некоторые компиляторы Си предоставляют нестандартную библиотечную функцию void *alloca(size_t size) , несколько упрощающую работу с динамическими массивами. Эта функция выделяет память не в куче, как malloc , а на стеке, и эта память автоматически освобождается при достижении оператора return . То есть при выделении памяти динамического массива этой функцией его не нужно удалять вручную, но такой массив невозможно вернуть из функции в точку вызова.

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

    Массив переменной длины может получить любой необходимый размер в момент создания. Память под него выделяется на стеке. Массив переменной длины существует до выхода из области видимости, в которой он был объявлен, после чего его память автоматически освобождается. Как и в предыдущем случае, массив переменной длины невозможно вернуть из функции в точку вызова.

    С++ [ править | править код ]

    В C++ поддерживаются функции работы с памятью из стандартной библиотеки Си, но их использование не рекомендуется. Массив переменной длины здесь также можно выделить с помощью стандартных команд работы с динамической памятью new и delete :

    Читайте также:  Стоит ли брать телефон на алиэкспресс

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

    Библиотечным решением является шаблонный класс std::vector :

    std::vector имеет множество методов и переопределённых операторов, часть из которых показана выше на примере. Они позволяют обращаться по индексу, изменять в любую сторону размер массива, использовать его как стек. Управляемым является не только актуальный размер, но и ёмкость вектора, что позволяет оптимизировать процесс выделения памяти. Стандарт C++ требует от реализации обязательного выполнения условий:

    • все элементы вектора должны храниться подряд в порядке увеличения индекса в целостном блоке оперативной памяти;
    • должно быть гарантировано константное время доступа к элементу вектора.
      Переводы, 12 августа 2015 в 15:42

    Иногда от коллекции требуется неограниченная вместимость и простота использования списка, но при этом константное время доступа к произвольному элементу, как в массиве. В этом случае используется список на основе массива — динамический массив (Array List).

    Класс ArrayList

    ArrayList — это коллекция, которая реализует интерфейс IList и использует массив для хранения элементов. Как и связный список, ArrayList может хранить произвольное число элементов (ограниченное только объемом доступной памяти), но в остальном ведет себя как массив.

    Интерфейс IList предоставляет все методы ICollection и дополнительно — методы для чтения, вставки и удаления элементов по индексу. Код ниже сгенерирован с помощью команды «Implement Interface» в Visual Studio 2010 и, кроме автоматически сгенерированных заглушек для методов, содержит также:

    • Массив из T ( _items ) для хранения элементов.
    • Конструктор по умолчанию, который создает пустой список.
    • Конструктор, принимающий целое число, который создает список с заданной вместимостью. Заметьте, что вместимость списка и его длина — это не одно и то же. На практике может встретиться ситуация, когда такой конструктор позволит пользователю избежать большого количества расширений внутреннего массива.

    Вставка элементов

    Вставка элементов в динамический массив отличается от вставки в связный список. На то есть две причины. Первая: динамический массив поддерживает вставку в середину массива, тогда как в связный список можно вставлять только в конец или начало. Вторая: вставка элемента в связный список всегда выполняется за константное время. Вставка в динамический массив может занимать как O(1), так и O(n) времени.

    Расширение массива

    По мере добавления элементов внутренний массив может переполниться. В этом случае необходимо сделать следующее:

    1. Создать массив большего размера.
    2. Скопировать элементы в новый массив.
    3. Обновить ссылку на внутренний массив списка так, чтобы она указывала на новый.

    Теперь осталось ответить на вопрос, какого размера должен быть новый массив. Это определяется стратегией роста динамического массива. Мы рассмотрим две стратегии и для обеих посмотрим, насколько быстро растет массив и насколько его рост снижает производительность.

    Увеличение вдвое (подход Mono и Rotor)

    Существуют две реализации ArrayList , код которых можно найти в сети: Mono и Rotor. Обе используют простой алгоритм увеличения размера массива, увеличивая его вдвое при необходимости. Если изначальный размер массива равен нулю, то новый будет вмещать 16 элементов:

    Этот алгоритм делает меньше выделений памяти, но тратит больше места, чем вариант, принятый в Java. Другими словами, он обеспечивает более частые случаи вставки за константное время ценой использования большего количества памяти. Процесс создания нового массива и копирования в него элементов будет происходить реже.

    Медленный рост (подход Java)

    В Java используется похожий подход, но массив растет медленнее. Размер нового массива определяется следующим образом:

    При использовании этого алгоритма используется меньше памяти.

    Давайте посмотрим на кривые роста массивов до 200 000 элементов при использовании этих двух стратегий:

    Как видно из графика, для того, чтобы перейти границу в 200 000 элементов, варианту с удвоением массива понадобилось 19 операций выделений памяти и копирования, тогда как вариант Java потребовал 30 операций.

    19 ноября 2019 – 10 января 2020, Гусев и онлайн, беcплатно

    Какая стратегия лучше? Не существует правильного и неправильного ответа на этот вопрос. При использовании удвоения у нас будет меньше операций вставки за O(n), но больше расход памяти. При более медленном росте будет использовано меньше памяти. В общем случае допустимы оба варианта. Если ваше приложение имеет специфические требования, возможно, вам потребуется реализовать ту или иную стратегию расширения. В любом случае, внешнее поведение динамического массива не изменится.

    Наша реализация будет использовать увеличение вдвое (подход Mono/Rotor)

    Метод Insert

    • Поведение: добавляет элемент по указанному индексу. Если индекс равен количеству элементов или больше него, кидает исключение.
    • Сложность: O(n).

    Вставка по определенному индексу требует сдвига всех элементов, начиная с этого индекса, на одну позицию вправо. Если внутренний массив заполнен, вставка потребует увеличения его размера.

    В следующем примере дается массив с пятью позициями, четыре из которых заполнены. Значение «3» вставляется на третью позицию (с индексом 2):

    Массив до сдвига элементов

    Массив после сдвига элементов

    Массив после вставки элемента на свободную позицию

    Метод Add

    • Поведение: добавляет элемент в конец списка.
    • Сложность: O(1), если осталось более одного свободного места; O(n), если необходимо расширение массива.

    Удаление элементов

    Метод RemoveAt

    • Поведение: удаляет элемент, расположенный по заданному индексу.
    • Сложность: O(n).

    Удаление элемента по индексу — операция, обратная вставке. Указанный элемент удаляется, а остальные сдвигаются на одну позиуию влево.

    Массив до удаления элемента

    Массив после удаления элемента

    Массив после сдвига элементов

    Метод Remove

    • Поведение: удаляет первый элемент, значение которого равно предоставленному. Возвращает true , если элемент был удален, или false в противном случае.
    • Сложность: O(n).

    Доступ к элементам

    Метод IndexOf

    • Поведение: возвращает индекс первого элемента, значение которого равно предоставленному, или -1, если такого значения нет.
    • Сложность: O(n).

    Метод Item

    • Поведение: позволяет прочитать или изменить значение по индексу.
    • Сложность: O(1).
    Читайте также:  Электроплита панель какую выбрать

    Метод Contains

    • Поведение: возвращает true , если значение есть в списке, и false в противном случае.
    • Сложность: O(n).

    Перебор

    Метод GetEnumerator

    • Поведение: возвращает итератор IEnumerator для прохода по всем элементам списка.
    • Сложность: Получение итератора — O(1), обход списка — O(n).

    Заметьте, что мы не можем просто пройтись по массиву _items , так как он содержит еще не заполненные ячейки, поэтому мы ограничиваем диапазон, по которому будем итерироваться количеством элементов.

    Остальные методы IList

    Метод Clear

    • Поведение: удаляет все элементы из списка.
    • Сложность: O(1).

    Существет два варианта реализации метода Clear . В первом случае создается новый пустой массив, во втором — только обнуляется поле Count . В нашей реализации будет создаваться новый массив нулевой длины.

    Метод CopyTo

    • Поведение: копирует все элементы из внутреннего массива в указанный, начиная с указанного индекса.
    • Сложность: O(n).

    Мы не используем метод CopyTo массива _items , поскольку хотим скопировать только элементы с индексами от 0 до Count , а не весь массив. При использовании Array.Copy мы можем указать количество копируемых элементов.

    Метод Count

    • Поведение: возвращает текущее количество элементов в коллекции. Если список пуст, возвращает 0.
    • Сложность: O(1).

    Count — автоинкрементируемое поле с приватным сеттером и публичным геттером. Пользователь может только прочитать его, а изменять будут методы добавления и удаления элементов.

    Метод IsReadOnly

    • Поведение: всегда возвращает false , так как наша коллекция изменяемая.
    • Сложность: O(1).

    Продолжение следует

    На этом мы заканчиваем разбор динамических массивов. В следующий раз мы перейдем к стекам и очередям.

    Опубликовано Константин Туйков в 19.05.2018 19.05.2018

    Сперва давайте разберемся, что это такое и с чем это следует кушать. Динамические структуры данных — это любая структура данных, занимаемый объем памяти которой не является фиксированным. Иными словами, в подобной структуре может храниться как два, пять, двадцать элементов, так и одно большое ничего. Размер подобной структуры ограничен только объемом оперативной памяти компьютера.

    Существует несколько разновидностей динамических структур: список, дерево.
    Прежде чем переходить к описанию структур, следует запомнить несколько простых определений:

    • Потомок — элемент структуры, идущий после текущего. В зависимости от вида динамической структуры у элемента может быть более одного потомка.
    • Предок — элемент структуры, идущий до текущего.
    • Головной элемент (Head) — первый элемент списка.
    • Хвостовой элемент (Tail) — последний элемент списка.

    Структура данных Список

    Список — это линейная динамическая структура данных, у каждого элемента может быть только один предок и только один потомок. По сути своей это очень похоже на обыкновенный массив, с той лишь разницей, что размер его не имеет ограничений. Списки также подразделяются на несколько
    типов.

    • Односвязный список — элемент имеет указатель только на своего потомка.
    • Двусвязный список — элемент имеет указатели и на потомка, и на родителя.
    • Замкнутый (кольцевой, циклический) список — головной и хвостовой элементы которого указывают друг на друга.

    На базе простого однонаправленного списка могут быть построены такие структуры данных, как очередь (queue) и стек (stack).

    Очередь есть ничто иное, как список, операции чтения и добавления элементов в котором подвержены определенным правилам. При этом, при чтении элемента, он удаляется из очереди. Все операции проводятся по принципу «Первый пришел, первый вышел» (FIFO — first in, first out). Таким образом, для чтения в очереди доступна только голова, в то время как добавление проводится только в хвост.

    Стек во многом похож на очередь, с той лишь разницей, что извлечение и добавление элементов в нем происходит по правилу «Последний пришел, первый вышел» (LIFO — last in, first out). Добавление и извлечение элементов проводится от головы. По принципу похоже на работу обоймы огнестрельного оружия.

    Двусвязный список на языке C++

    Рассмотрим пример реализации простейшего двусвязного списка. Этот и последующие примеры кода будут приведены на языке c++. В примере реализованы операции добавления нового элемента в список и вывод элементов на форму.

    Элемент списка
    Список

    Структура данных Дерево

    Дерево — несколько более интересная структура. В отличие от списка, у одной записи может быть более одного потомка, но только один предок. Кроме того в дереве явно выделяется только головной элемент, называемый корнем (Root). Среди деревьев также существует разбиение на подтипы.

    • Бинарное дерево — у каждой вершины дерева может быть не более двух потомков.
    • Сильно разветвленное дерево — у вершины может быть n-ое число потомков.

    В свою очередь для бинарных деревьев существует разбиение в зависимости от высоты поддеревьев, информационной части вершин и т.д. (АВЛ-деревья, красно-черные деревья, и др.).

    В отличие от списка при обходе дерева может быть применено насколько различных путей:

    Бинарное дерево поиска на языке C++

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

    Бинарное дерево

    Одним из интересных примеров сильно разветвленного дерева является так называемая TRIE-структура или БОР. Подобная структура данных можем быть очень
    полезна при создании алгоритма наподобие Т9, потому как в каждой вершине бора содержится всего один символ алфавита или символ конца слова.

    Префиксное дерево

    При реализации любой динамической структуры средствами языка c++ следует очень внимательно следить за памятью. Наиболее частые ошибки в данном случае регистрируются как «access violation», то есть обращение к не размеченной области памяти. Обычно лечится внимательным изучением трассировки и поиском, где поезд пошел не в тот тоннель.

    Ну и на сладкое: рассмотрим пример интерактивного ввода дерева. По клику на мышку. Для этого незначительно расширим реализацию простого бинарного дерева. Единственное, что нам понадобится на форме — Image.

    Динамические структуры данных С++. Заключение

    Удачных вам экспериментов с динамическими структурами, коллеги.

    Кроме того, рекомендую прочитать статью Set C# | Структура данных Множество C#. А также подписывайтесь на группу ВКонтакте, Telegram и YouTube-канал. Там еще больше полезного и интересного для программистов.

    Комментировать
    0 просмотров
    Комментариев нет, будьте первым кто его оставит

    Это интересно
    Adblock detector