Я столкнулся с этим вопросом и подумал о том, чтобы спросить, что является наилучшим способом достижения этого.Печать любой старой версии очереди
Учитывая очередь FIFO. вы можете предположить, что очередь содержит целые числа. Каждый раз, когда происходит вставка или удаление, создается новая версия очереди. В любое время вам нужно распечатать (все содержимое очереди) любую более старую версию очереди с минимальной сложностью времени и пространства.
Предполагается, что вы имели в виду очередь FIFO, а не какую-либо другую очередь, как очередь приоритетов.
Храните его в массиве и сохраняйте две переменные указателя, одну на голову и другую на хвост.
Например:
insert 3 2 5 9 - version 1
q = [3 2 5 9]
^ ^
delete, delete - version 2
q = [3 2 5 9]
^^
insert 6 3 4 - version 3
q = [3 2 5 9 6 3 4]
^ ^
Чтобы напечатать версию, вам просто нужно хранить два значения для каждой версии: где указатели были. Затем печать становится линейной по размеру очереди в этой версии.
Вектор может стать большим, но вы должны хранить каждый элемент, который когда-либо был в нем, если вы хотите иметь возможность печатать любую версию.
Вы также можете использовать связанный список, чтобы избежать изменения размера массива, если вы считаете, что проблема. Просто удаляйте узел из памяти при удалении.
Это лучшее решение для средней амортизированной производительности. Возможно, это не подходит для кода реального времени, так как случайные операции изменения размера массива могут быть «O (n)». – btilly
@btilly - связанный список все еще можно использовать, если вам не нужен полный произвольный доступ и на самом деле не удаляйте голову при удалении. Тогда нет изменения размера, просто некоторые издержки памяти. – IVlad
Да, ваше решение можно было бы разумно сделать со связанным списком. Однако «найти старую версию» должно быть чем-то более эффективным, чем «поиск связанного списка». – btilly
Существует множество возможных решений. Здесь один со всеми гарантированными операциями O(log(n)) и нормальные операции амортизируются O(log(log(n)).
Держите счетчик операций. Храните элементы в списке пропуска (см. http://en.wikipedia.org/wiki/Skip_list для определения этого) в зависимости от порядка операции вставки. Когда элемент удален, заполните идентификатор операции удаления. Для обеспечения эффективности доступа держите пару указателей на текущую головку и текущий хвост.
Чтобы вставить элемент, добавьте его в текущий хвост. Чтобы вернуть элемент, верните его в текущую головку. Чтобы вернуть прошлое состояние, выполните поиск в списке пропусков для тогдашнего заголовка, затем начните идти по списку, пока не прочитаете хвостик.
Операции log(n) здесь ищут прошлую голову и (очень редко) вставляют новую головку, которая является высокоуровневым в списке пропуска.
Ваша проблема заключается в том, чтобы сделать очередь частично стойкой структурой данных.
Частично постоянный означает, что вы можете запросить любую версию, но вы можете делать обновления только в последней версии.
Пару лет назад я произнес речь о постоянстве структуры данных указателя. Он был основан на "Making data structures persistent" Дрисколлом, Сарнаком, Слейтором и Тарьяном.
Очевидно, что любая очередь может быть реализована как связанная структура данных. Если вам нужна простейшая практическая версия, вас может заинтересовать метод «Метод жирного узла», который описан на стр. 91 в вышеприведенном PDF-документе.
Идея состоит в том, чтобы хранить в каждом узле несколько указателей на следующие элементы, соответствующие различным версиям очереди. Каждому указателю присваивается номер версии, называемый timestamp.
Для каждой операции вставки или удаления вы обновляете указатели только в узлах, затронутых операцией обновления.
Для операции поиска в версии очереди i-th вы просто следуете указателям с наибольшей меткой времени, не превышающей i. Вы можете найти указатель, чтобы следовать, используя двоичный поиск.
В данном PDF-документе также существует более сложный, но еще более эффективный метод, называемый «Метод копирования узлов».
Теперь давайте предположим, что в очереди FIFO указатель на голову находится в начале массива, а затем указатель хвоста находится в конце текущей вставки. Затем, сохраняя текущее значение указателя положения хвоста в переменной, которая используется в качестве положения указателя головы во время будущей установки вставки и хвоста, завершает эту вставку. Таким образом, используя только одну переменную и только с вставкой, предыдущие версии могут быть напечатаны с начала массива на указатель хвоста.
insert 3 2 1 4
a=[3 2 1 4] --version 1
^ ^
b e
p = e;
insert 5 7 8
a=[3 2 1 4 5 7 8] --version 2
^^
b e
here version 1 = position 0 to position p = [3 2 1 4]
p = e;
delete 3
a=[2 1 4 5 7 8] --version 3
^^
b e
here version 2 = position 0 to position p =[2 1 4 7 8]
where
b = beginning
e = end
Таким образом, используя одну переменные для хранения предыдущей версии хвостового положения и предполагая, что начальное положение, чтобы быть всегда 0, предыдущие версии могут быть легко распечатаны.
Ваш вопрос слишком открытый. Какую информацию вам нужно отслеживать? Вас просто интересует длина очереди с течением времени или вы хотите сохранить информацию о конкретном наборе сущностей в очереди в любой момент времени? Если последний, у кого есть привилегии выделения/удаления для этих объектов, т. Е. Вы можете просто поддерживать набор ссылок или вам нужно клонировать их, чтобы убедиться, что вы все еще можете восстановить очередь, если они были освобождены в другом месте? Наконец, в соответствии с ожиданиями stackoverflow, что вы пробовали? – pjs
@pjs Вопрос очень точный. Это не его вина, что вы не можете прочитать четкое описание и настаивать на создании новых требований, которых там нет. – btilly
@btilly Вопрос не является точным, если мне нужно делать предположения, когда я рассматриваю возможные реализации. Я постоянно работаю с моделями очередей, и в некоторых сценариях вас интересует только то, сколько объектов присутствует, а в других случаях вам нужно знать их индивидуальные особенности. – pjs