|
Реализация динамического массива на PythonКурс по структурам данных: https://stepik.org/a/134212 Мы продолжаем курс по структурам данных. Пришло время посмотреть, как реализуется динамический массив в языках Python и С++. И начнем с языка Python. Динамический массив в PythonВсем питонистам известна коллекция типа list, которая позволяет создавать список из разных объектов. Например, так: marks = [2, 2, 3, 4] или так: lst = [True, "Истина", 1, 1.0] Можно ли считать такие списки динамическими массивами? Строго говоря, лишь с некоторым приближением, так как в массивах все элементы должны иметь единый тип данных. А во втором списке мы видим и булево значение и строку и целое число, то есть, разные типы. Но если мы посмотрим внутрь этой структуры, то увидим, что на самом деле списки в Python реализованы как динамические массивы ссылок. И эти ссылки могут быть связаны с любым объектом, любого типа.
Отсюда и получается эффект, словно список содержит разные типы. На самом деле в нем хранятся только ссылки, ведущие на те или иные объекты и не более того. То есть, сам динамический массив содержит данные одного типа – ссылки на объекты. Число хранимых элементов в списке можно определить командой: n = len(lst) Если требуется добавить новый элемент в этот список, то используется команда: lst.append(5) В результате в конец списка будет добавлена новая ссылка, связанная с целым значением 5. Скорость этой операции с точки зрения О большого составляет O(1). То есть, добавление нового значения в конец списка – это относительно быстрая операция. Если же мы хотим вставить новое промежуточное значение, например, в середину или начало списка, то это делается с помощью команды: lst.insert(0, 'First') Здесь первое значение – это индекс вставляемого элемента, а второй аргумент – значение вставляемого элемента. В итоге получаем список из шести элементов со скоростью выполнения операции O(n), где n – общее число элементов в списке. Как видите, скорость выполнения операции вставки элементов в список существенно выше, чем операция добавления последнего элемента. Поэтому вставок лучше избегать при использовании списков. Далее, для доступа к отдельным элементам списков используется оператор квадратные скобки: el_1 = marks[2] # чтение значения 3-го элемента marks[1] = 3 # запись значения во 2-й элемент Так как динамический массив в своей основе использует обычный статический массив, то доступ к произвольному его элементу осуществляется мгновенно (за константное время) O(1). Я напомню, что имя самого массива хранит адрес первой ячейки. Зная этот начальный адрес и размер одного элемента в байтах: k – число байт для одного элемента мы легко можем вычислить адрес любого j-го элемента по формуле: p = marks + (j-1) ∙ k Поэтому операции чтения/записи отдельного элемента выполняются за время O(1). Таким образом, если нам нужен список разумной длины, к элементам которого предполагается частое обращение, то динамический массив (список языка Python) будет хорошим выбором. Также мы вполне можем использовать операции добавления последнего элемента в список, увеличивая общее число элементов. Но операций вставки новых элементов и удаления промежуточных лучше избегать, т.к. они требуют линейного времени выполнения. Вот общие рекомендации по использованию списков языка Python. Объединение списков и срезыДовольно часто в Python используется операция объединения списков. Например, мы можем соединить два списка в нашем примере следующим образом: lj = marks + lstЧто происходит в этот момент, какие действия? И какова вычислительная сложность такой операции с точки зрения О большого? Начнем с первого вопроса, что происходит в момент объединения двух динамических массивов. Создается новый массив, размером достаточным для хранения всех объединяемых элементов, а затем, в него копируется информация из первого и второго массивов:
Если принять число элементов первого массива за n, а во втором – за m, то вычислительная сложность такой операции с точки зрения О большого составляет: O(n + m) Другая распространенная операция со списками – это взятие срезов. Давайте предположим, что у нас имеется список: lst = [1, 2, 3, 4, 5, 6, 7, 8] и мы берем от него срез: lst2 = lst[1:6] Что происходит с динамическим массивом в этом случае? Как мы знаем, срез в списках создает новый список с соответствующим набором элементов. В данном случае список lst2 будет состоять из значений: lst2 = [2, 3, 4, 5, 6] То есть, при взятии среза создается новый динамический массив и в него копируются данные из первого массива. Сложность этой операции составляет O(n). Курс по структурам данных: https://stepik.org/a/134212 Видео по теме |
