Я читал, что стек кэша забыл, может быть реализован с использованием массива удвоения.Сложность кеш-забытых стеков и очередей
Может ли кто-нибудь объяснить, как анализ делает каждый толчок и поп, имеет сложность ввода-вывода 1/B?
Я думаю, что стандартные стеки не обращают внимания на кеш. Вы ошибаетесь только на 1/B доступа, потому что любая последовательность push/pop должна быть смежными адресами, так что вы можете ударить новую строку кэша только один раз каждые операции B. (Примечание: аргумент, требует, по меньшей мере, 2 строки кэша, чтобы предотвратить пробуксовку.)
Спасибо за ответы. По стандартным стекам я предполагаю, что это означает, что элементы являются заразными, и это то, что я согласен, точно достигается методом удвоения массива. Ключевым моментом является то, что для предотвращения опрокидывания требуется 2 строки кэша.Так это достигается путем принятия оптимальной стратегии замены страниц? – Meghana
@Meghana: Это то, что принято считать для анализа, не учитывающего кеш. Но для этой проблемы, предполагая, что LRU работает нормально. –
Стек поддерживает следующие операции:
В то время как эти две операции могут быть выполнены используя односвязный список с O (1) push и O (1) pop, он страдает от проблем кеширования, поскольку сохраненные элементы распределяются по памяти. Для этого подхода мы выдвигаемся на передний план списка и выпадаем из списка.
В качестве нашей структуры данных мы можем использовать 210, а также нажать и поместить в конец массива. (Мы будем отслеживать последнюю заполненную позицию в массиве как наш индекс и модифицировать ее, когда мы нажимаем и поп-элементы).
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) или линейно по числу элементов.
Таким образом, при нажатии одного элемента может потребоваться больше времени, чем постоянная операция, толкание большого количества элементов требует линейного объема работы.
Динамический массив с точки зрения кэширования, поскольку все элементы близки друг к другу, так что несколько элементов должны находиться в одних и тех же строках кэша.
Что означает «1/B»? – Gabe
@Gabe B представляет собой Х-байтовый блок памяти, который может быть прочитан в одной операции ввода-вывода. Подумайте о кеш-линии. Таким образом, для каждой из операций N требуется только O (1/B) чтение/запись, амортизируемая по всем N операциям. Кроме того, это домашнее задание? –