Хорошая коллекция для реализации Undo / Redo?

Question

Я читал о методах отмены / повторения, я понимаю, как это должно быть реализовано (я нашел это интуитивно понятным).

Однако я думаю о коллекции, которую следует использовать как историю,

Многие люди используют стек, но стек C # реализован в виде массива, и это проблема: Если я использую «ограниченную» историю (например, для 2000 команд), когда предел достигнут, у меня нет способа удалить элементы из конца стека, и если я найду способ сделать это, я необходимо переместить все элементы массива (и это при каждом выполнении команды).

LinkedList выглядит хорошо, но тратит много памяти.

Мой последний вариант - пользовательская реализация связанного списка, SingleLinkedList. Узел этого списка состоит из свойства Value и свойства указателя NextNode, поэтому я использую двойную память для каждого элемента (но не более того, кроме случаев, когда я использую вещи меньше, чем "sizeof (void *)").

Я также храню указатель на первый элемент и указатель на последний элемент в коллекции.

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

Итак, мой вопрос: Должен ли я использовать LinkedList или мой собственный SingleLinkedList?

Обновление 1:

Спасибо за ответы на данный момент, в моей ситуации у меня нет проблем с памятью, ну, я не знаю, на кого я нацеливаюсь, я создаю служебную программу и по своему собственному представлению о "служебной программе ", они должны тратить как можно меньше ресурсов процессора / памяти (очевидно, не говорите мне" напишите это на c ++ так ", потому что есть большая разница).

На мой взгляд, односвязный список работает хорошо, я не очень люблю ограничивать историю, я думаю о Photoshop, где ваша история "безгранична".

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

Как сказал кто-то другой, если я ограничу связанный список большим размером, около 60000 команд (я думаю, их должно быть достаточно), я трачу только небольшое количество памяти (4 байта * 60000) по сравнению с singlelinkedlist.

Тем не менее, я думаю, что я буду использовать LinkedList, однако просто чтобы быть уверенным, было бы хорошо, если бы я использовал историю без ограничений?

Обновление 2:

@ Akash Kava Ну, то, что вы говорите, важно, но вы неправильно поняли, ПОЧЕМУ я хочу использовать LinkedList и почему я не хочу использовать стек. Основная проблема со стеком состоит в том, что необходимо ограничить его размер, и при достижении этого предела нет быстрого способа удаления старых команд (это массив и удваивающий размер каждый раз, когда мы этого не хотим).

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

В этом случае довольно просто подумать о LinkedList, где у вас есть предыдущий указатель. Однако мы используем 2 дополнительных указателя для каждого элемента нашего «стека» (который на этот раз создается через список ссылок), что похоже на использование в 3 раза больше памяти, чем необходимо для хранения команды (с массивом у нас нормальная память Использование: singlelinkedlist использует в 2 раза больше памяти, а связанный список использует в 3 раза больше памяти).

Итак, в основном я спрашивал, какая коллекция является «лучшей» для реализации стека для шаблона отмены-повтора.

Ваш ответ заставил меня подумать, что даже если я создаю команду 60000 в 1 программе, она составляет около 5 МБ памяти в программе, что не так уж и много.

В основном, если вы хотите ограничить историю отмен / повтороввам нужен LinkedList, иначе лучше использовать SingleLinkedList.

Answer 1

Пока используйте LinkedList или любое стандартное решение, но будьте осторожны при его реализации.Поместите все свои действия по отмене / восстановлению позади хорошо разработанной абстракции.Затем, если дополнительная память, которую использует LinkedList, действительно оказывается проблемой (маловероятно), вы можете заменить ее собственной реализацией.

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

Answer 2

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

Stack<Action> undoStack;
Stack<Action> redoStack;

Можно отменить / Повторить условия просты

undoStack.Count > 0 (We can undo)
redoStack.Count > 0 (We can redo)

Во время изменения мы должны очистить redoStack, когда мы изменяем что-либо в активном документе, вы можете четко это заметить в VS, когда вы редактируете что-либо, повтор отключается.

redoStack.Clear() <-- important step
undoStack.Push(action);

Во время удаления

Action action = undoStack.Pop();
redoStack.Push(action); <-- necessary...

Во время повторения

Action action = redoStack.Pop();
undoStack.Push(action);

То же самое можно реализовать с помощью связанного списка, но становится сложным управлять головой и хвостом и поддерживать текущий указатель.

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

Answer 3

Если вы хотите связанный список, вы должны использовать LinkedList. Зачем переписывать код, который уже существует? сэкономить 16 МБ оперативной памяти?

Answer 4

Как я уже говорил и кто-то еще предложил, наличие 1 дополнительного указателя на узел вместо массива не является большой проблемой, также давайте предположим, что нашим значением является другой указатель, в случае 60000 команд у нас есть 8 байт на узел.480 КБ, очень низкое значение, если подумать.

Тем не менее, я думаю, что лучшей коллекцией в этом случае является SingleLinkedList, что позволяет нам неограниченное количество стеков отмены / повторения (построенных вокруг SingleLinkedList).

Если необходимо для ограничения размера нашего стека, необходим LinkedList.

Answer 5

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

Хорошо работает список с двумя связями.Двухсторонняя очередь работает нормально.Непрерывная структура типа ArrayList, требующая удаления с фронта за линейное время, может работать нормально, если каждая операция представляет собой сохраненную в ней ссылку на объект.Циклический массив также может хорошо работать, если у вас есть фиксированный лимит на количество операций отмены, которые могут быть записаны (в этом случае вы можете заранее выбрать размер кругового массива, и он автоматически начнет перезаписывать самые старые записи, когда он превышает определенныйемкость).

Поскольку единственное, что вы с этим делаете, это откатывайтесь назад один раз для всей пользовательской операции, откатывайтесь назад один раз для всей операции отмены и, возможно, извлекайте элемент спереди, если пользователь записываетоперация и история начинает заполняться или использует слишком много памяти.Это совсем не критично для производительности.Если у вас нет очень необычного случая, когда пользователь может записывать около десяти тысяч операций в секунду (это было бы довольно впечатляюще, если бы кто-то нажимал так быстро), может случиться не так уж и много, поскольку он сильно связан с пользовательским вводом.

Конечно, то, что вы храните внутри , одна операция отмены может быть весьма критичной для производительности, и там вам может понадобиться очень эффективное представление данных, которое минимизирует использование памяти (в зависимости от того, какое состояние вы храните внутриотменяемая запись).Но внешний стек отмены / история на самом деле не очень критичны по производительности, и я думаю, что в этом случае приемлемы практически все варианты.Это происходит от парня, который любит сокращать использование памяти для повышения производительности, но в этом случае ваша память стека отмены "холодная".Ко многим из них обращаются не часто (например, не получают доступ к каждому отдельному кадру) - просто когда пользователь нажимает кнопку отмены или записывает новую операцию, если только вы не нацелены на очень ограниченное оборудование.

Ноесли вы хотите сжать вещи, которые я не считаю действительно необходимыми, то развернутый связанный список может сработать.Это в основном связанный список, в котором каждый узел хранит более одного элемента.В этом случае использование ссылок в памяти тривиально.Вы можете сделать что-то вроде этого:

struct Node
{
     Command commands[n];
     Node next;
     Node prev;
     int first;
     int last;
}

Когда вы отмените, вы можете уменьшить счетчик last хвостового узла.Если last == first, то вытолкните его, освободите и сделайте предыдущий узел новым хвостом.Когда вы записываете операцию, вы можете увеличить счетчик last.Если last == n, то выделите новый узел и сделайте этот новый хвост.Если вы хотите начать уменьшать размер истории (то есть удалить запись отмены спереди), увеличьте счетчик first головного узла.Если first == last, то освободите узел и установите следующий узел в качестве нового заголовка.Это даст вам постоянные возвраты, всплывающие и всплывающие фронты при использовании очень небольшого объема памяти для каждой отмены, так как вам не нужно хранить данные узла, как ссылки для отмены (только один раз для каждых n отмененных записей, которые вы храните, и вы можете сделать n большим числом, например 512, сократив издержки связанного списка до 1/512 или ~ 1,95%) и улучшив локальность ссылок.

Answer 6

Вы можете использовать массив с вращающимися значениями startindex и endindex.Абстрактный процесс извлечения и добавления элементов в методах синхронизированных классов, которые также поддерживают startIndex и endIndex. Этот метод увеличил бы память только на ao (2) вместо стека с простым массивом.