Сложность кеш-стеков и очередей

Question

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

Может кто-нибудь объяснить, как анализ делает каждый толчок и поп 1/B Амортизируемая сложность ввода / вывода?

Answer 1

Стек поддерживает следующие операции:

• От себя
• поп

Хотя эти две операции могут быть выполнены с использованием односвязного списка с O(1) push и O(1) pop, у него есть проблемы с кэшированием, поскольку хранимые элементы рассредоточены по памяти. Для этого подхода мы нажимаем на начало списка и выталкиваем с начала списка.

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

Popping будет O (1), так как нам не нужно изменять размер массива.

Если в конце массива есть дополнительный пробел, нажатие будет O(1).

Проблема в том, когда мы пытаемся нажать на элемент, но для него нет места. В этом случае мы создаем новый массив, который в два раза больше (2n), затем копируем каждый из n элементов, затем нажимаем на элемент.

Предположим, у нас есть массив, который уже имеет размер n, но начинается пустым.

Если я добавлю n+1 элементов в массив, то первые n элементов займут O(1)*n = O(n) время.

Элемент +1 занимает O (n) времени, так как он должен создать новую копию массива.

Таким образом, добавление n+1 элементов в массив - это O( 2n), но мы можем избавиться от константы и просто сказать, что это O (n) или линейно по количеству элементов.

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

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

Answer 2

Я думаю, что стандартные стеки не обращают внимания на кеш. Вы отказываете только в 1/B доступах, потому что любая последовательность push / pop должна быть смежными адресами, поэтому вы можете перейти на новую строку кэша только один раз при каждой B-операции. (Примечание: аргумент требует как минимум 2 строки кэша для предотвращения перебора.)