Друзья, продолжаем говорить о типе данных
Перед тем, как приступать к прочтению, советую ознакомиться с предыдущим постом.
Амортизационный анализ — метод подсчета времени, требуемого для выполнения последовательности операций над структурой данных. При этом время усредняется по всем выполняемым операциям и анализируется средняя производительность операций в худшем случае. Такой анализ чаще всего используется, чтобы показать, что даже если некоторые из операций последовательности являются дорогостоящими, то при усреднении по всем операциям средняя их стоимость будет небольшой за счет низкой частоты встречаемости.
Пожалуй, одной из самых частых операций, выполняемых на списках, является операция добавления в конец новых элементов (методы
Мы уже выяснили, что под капотом списков (тип
1.
2.
Пусть мы хотим добавить в список
Пример. Пусть в списке было
Несложно заметить, что по мере того, как длина списка увеличивается, время, затраченное на создание нового массива, также увеличивается. Увеличение длины массива примерно в
Python использует еще и ряд оптимизаций для эффективной работы с памятью. Более подробно ознакомиться с ними можно, рассмотрев исходный код соответствующей функции тут.
#полезныйматериал #list #python
list.Перед тем, как приступать к прочтению, советую ознакомиться с предыдущим постом.
Амортизационный анализ — метод подсчета времени, требуемого для выполнения последовательности операций над структурой данных. При этом время усредняется по всем выполняемым операциям и анализируется средняя производительность операций в худшем случае. Такой анализ чаще всего используется, чтобы показать, что даже если некоторые из операций последовательности являются дорогостоящими, то при усреднении по всем операциям средняя их стоимость будет небольшой за счет низкой частоты встречаемости.
Пожалуй, одной из самых частых операций, выполняемых на списках, является операция добавления в конец новых элементов (методы
append() и extend()).Мы уже выяснили, что под капотом списков (тип
list) лежат массивы фиксированной длины. Для каждого списка (list) определяются две характеристики:1.
size — фактическая длина списка, т.е. количество элементов, которое реально лежит в списке,2.
capacity — длина выделенного массива, лежащего в основе списка, т.е. количество элементов, которые могут поместиться в массив.Пусть мы хотим добавить в список
k новых элементов. Тогда new_size = size + k — новая фактическая длина нашего списка. Когда выделенной длины массива (capacity) недостаточно, чтобы добавить в список новые элементы, Python для нашего списка создает новый массив, capacity которого будет примерно в 1.125 раз больше, чем new_size, затем копирует в новый массив старые элементы и добавляет новые.Пример. Пусть в списке было
100 элементов (size = 100), а в массиве было выделено памяти для 105 элементов (capacity = 105). Теперь мы хотим добавить 10 элементов в список, но в массиве не хватает места. Тогда Python выделит новый массив с количеством элементов, равным 110 * 1.125 = 124 (capacity = 124). В результате длина нашего списка будет равна size = 110, а длина соответствующего массива capacity = 124.Несложно заметить, что по мере того, как длина списка увеличивается, время, затраченное на создание нового массива, также увеличивается. Увеличение длины массива примерно в
1.125 раз позволяет амортизировать среднее время добавления элементов в список. Оно равно O(1), то есть является константным, несмотря на то, что некоторые отдельные увеличения длины массива (capacity) могут быть дольше. Python использует еще и ряд оптимизаций для эффективной работы с памятью. Более подробно ознакомиться с ними можно, рассмотрев исходный код соответствующей функции тут.
#полезныйматериал #list #python