Я часто использую Python, но меня действительно не волнует, как Python работает внутри. Итак, сегодня я сосредоточусь на списке Python и объясню его реализацию. List.append и list.pop в Python динамически изменяют размер списка, что позволяет им работать быстрее за O (1) раз. Обратите внимание, что list.pop для последнего элемента занимает только постоянное время. В этом посте я расскажу, почему это стало возможным.
Мы называем структуру данных, подобную списку Python, динамическим массивом, а обычный массив называем статическим массивом. Этот пост имеет следующую структуру.
- Что такое динамический массив?
- Как динамический массив добавляет или выталкивает элемент
- Как сбалансировать добавление и поп
Я объясняю это на основе лекции Массачусетского технологического института Удвоение стола, Карп-Рабин.
1. Что такое динамический массив?
Динамический массив изменяет свой размер, когда мы добавляем или выталкиваем элемент. Конечно, изменение размера бывает не всегда. Динамический массив регулирует баланс добавления и расширения, выталкивания и сжатия для эффективного изменения размера.
Динамический массив создает новый массив и копирует элементы из старого массива, когда элемент заполняет старый массив. На рисунке ниже показан пример расширения массива. Я разделяю добавление и копирование для удобства понимания. Однако и добавление элемента, и копирование элемента имеют одинаковый эффект.
При увеличении размера массива эффективность ухудшается, если вы увеличиваете немного или сильно. Как показано на рисунке выше, когда вы увеличиваете размер только на один, это пустая трата операций. Это связано с тем, что каждый раз, когда вы добавляете элемент в старый полный массив, все элементы в этом массиве необходимо копировать в новый массив. С другой стороны, если вы сильно увеличите размер, это будет пустой тратой места, которое пусто, потому что ни один элемент не хранится.
В динамическом массиве, когда вы выталкиваете элемент из состояния ниже, динамический массив сжимается в размере.
На рисунке выше видно, что пространство потрачено впустую. При уменьшении размера эффективность ухудшается, если вы уменьшите немного или сильно. Если вы немного уменьшите размер, потраченное впустую пространство увеличится. С другой стороны, если вы сильно уменьшились, вам нужно увеличить размер, когда вы добавляете новый элемент.
В следующем разделе я объясню, как динамический массив позволяет избежать этой расточительности.
2. Как динамический массив добавляет или извлекает элемент.
2.1 Добавление элемента
Во-первых, давайте рассмотрим ситуацию, когда добавляется элемент или увеличивается размер в динамическом массиве. Динамический массив увеличивает свой размер, когда ему не хватает места для добавления нового элемента. Динамический массив использует коэффициент роста для определения размера нового массива. Здесь коэффициент роста означает, во сколько раз размер нового массива по сравнению с размером старого массива. У каждого языка программирования свой фактор роста. Эта статья Википедии говорит, что фактор роста равен 2 в C или Golang и 1,125 в Python. Я использую 2 в качестве фактора роста в этом посте для простоты.
Обратите внимание на временную сложность добавления n элементов в динамический массив с коэффициентом роста 2. Я опишу временную сложность добавления элемента позже. Размер массива изменяется ниже каждый раз, когда вы добавляете элемент, при условии, что начальный размер массива равен 2. Я показываю время добавления и копирования слева от массива.
Сложность добавления n элементов выглядит следующим образом.
Первая половина приведенного выше уравнения представляет собой стоимость добавления n элементов, а другая половина - стоимость копирования. Стоимость копирования равна стоимости увеличения размера массива. Сложность по времени становится общим числом операций, поскольку добавление элемента или копирование выполняется за O (1) раз.
Уравнение ниже представляет собой геометрическую последовательность, поэтому мы можем его деформировать, а временная сложность будет следующей. Я игнорирую постоянные условия при деформировании.
Наконец, мы получаем временную сложность добавления n элементов в динамический массив как O (n) времени. Это означает, что добавление элементов в динамический массив выполняется за линейное время, одновременно увеличивая его размер.
Мы можем думать, что добавление элемента выполняется в среднем за линейное время, поскольку временная сложность добавления n элементов составляет O (n ). Такой вид временной сложности называется временем амортизированной сложности. Кроме того, способ анализа всей операции, а не каждой операции, называется амортизированным анализом. По амортизированному анализу list.append в Python в среднем занимает линейное время.
В общем, нас волнует только время на выполнение всей задачи, а не время нескольких операций. По этой причине мы используем амортизированный анализ. Например, в задаче по сохранению каждой строки из CSV-файла в массив важнее сохранить все строки, чем одну строку.
2.2 Добавление элемента
Динамический массив уменьшает размер массива на 1 / (коэффициент роста) вместе с выталкиванием элемента. Потраченное впустую пространство увеличится, если количество элементов намного меньше размера массива. Эта операция соответствует list.pop в Python. Следуя фактору роста при добавлении элемента, мы предполагаем, что динамический массив уменьшает размер массива вдвое при извлечении элемента. Извлечение элемента из динамического массива ведет себя, как показано ниже, при условии, что начальный размер массива равен 16.
Если мы рассуждаем так же, как добавление элемента, временная сложность выталкивания n элементов становится O (n) временем. Таким образом, амортизированная временная сложность составляет O (1) раз, а извлечение элемента из динамического массива выполняется за линейное время с одновременным уменьшением размера массива.
3. Как сбалансировать добавление и всплывающее окно
В разделе 2 я объясняю поведение добавления и извлечения по отдельности, мы должны принять во внимание эффективность выполнения обеих операций. Повторное добавление и выталкивание элемента в приведенном ниже случае увеличит количество потраченных впустую операций.
Мы можем справиться с этой проблемой, настроив время расширения и сжатия. Например, мы уменьшаем размер массива вдвое, когда количество элементов равно четверти размера массива. Расширение остается прежним.
Даже если вы добавляете или выталкиваете элемент несколько раз, это не увеличит время операции. Это потому, что время расширения и сжатия различается.
Это все для объяснения. В этом посте я объяснил, как работает динамический массив реализации в Python. Согласно амортизированному анализу, списки Python list.append и list.pop выполняются за линейное время. Если вас интересуют другие операции в списке или другие структуры данных в Python, я рекомендую вам посетить TimeComplexity в вики Python. Спасибо за чтение.
