5

我正在阅读有关撤消/重做技术的信息，我了解应该如何实现它（我发现它很直观）。

但是我在考虑应该作为历史的收藏，

很多人使用堆栈，但 C# 堆栈是作为数组实现的，这是一个问题：如果我使用“有限”历史记录（例如，对于 2000 条命令），当达到限制时我没有从堆栈末尾删除项目的方法，如果我找到了一种方法，我必须移动数组的所有元素（每次命令完成时都会移动）。

LinkedList 看起来不错，但会浪费大量内存。

我的最后一个选择是一个链表的自定义实现，一个 SingleLinkedList。该列表的一个节点由 Value 属性和 NextNode 指针属性组成，因此我为每个项目使用双内存（但仅此而已，除非我使用的东西小于“sizeof(void*)”）。

我还存储了指向集合中第一个元素的指针和指向最后一个元素的指针。

我可以轻松地将命令添加到历史记录并以这种方式将它们移动到重做历史记录，但是我无法创建“有限”历史记录，因为不允许 RemoveLast （我必须遍历整个集合才能删除最后一项）。

所以我的问题是：我应该使用 LinkedList 还是我的自定义 SingleLinkedList？

更新1：

感谢您目前的回答，在我的情况下，我没有记忆问题，好吧，我不知道我的目标是谁，我正在创建一个实用程序，并且按照我自己的“实用程序”理念，他们应该尽可能少地浪费 cpu/内存（显然不要告诉我“用 c++ 编写它”，因为有很大的不同）。

在我看来，单链表效果很好，我真的不喜欢限制历史，我正在考虑你的历史是“无限”的 Photoshop。

我只担心撤消历史变得非常大时会发生什么，比如使用 8 小时。这就是为什么我正在考虑通过 LinkedList 来限制它。

然而，正如其他人所说，如果我将链表限制为较大的大小，大约 60000 个命令（我认为它们应该足够了），与单链表相比，我只会浪费少量内存（4 字节 * 60000）。

就是说，我想我会使用 LinkedList，但是可以肯定的是，如果我无限制地使用历史记录会好吗？

更新 2：

@Akash Kava好吧，你说的很重要，但你误解了我为什么要使用 LinkedList 以及为什么我不想使用堆栈。Stack 的主要问题是有必要限制它的大小，并且当达到这个限制时，没有一种快速的方法来删除旧命令（它是一个数组，每次它不是我们想要的东西时都会加倍它的维度）。

单个链表（想想它是如何构建的）和堆栈一样快（所有堆栈操作都是 O(1)）并且没有限制。但是在这种情况下，它不需要有限制，否则我们会遇到与堆栈相同的问题，我们没有快速的方法来删除单链表的最后一个元素（其行为类似于堆栈），因为我们不知道来自最后一个节点的上一个节点元素。

在这种情况下，很容易考虑一个 LinkedList，其中有 Previous 指针。但是，我们为“堆栈”的每个元素使用了 2 个额外的指针（这次是通过链表构建的），这就像使用存储命令所需的内存的 3 倍（使用数组，我们有正常的内存）使用，singlelinkedlist 的内存使用量是 2 倍，linkedlist 的内存使用量是 3 倍）。

所以我基本上要问的是哪个是实现撤销重做模式堆栈的“最佳”集合。

你的回答让我觉得即使我在 1 个程序中创建 60000 个命令，它在一个程序中也有大约 5MB 的内存，这不是那么多。

基本上，如果你想限制你的撤销/重做历史，你需要一个 LinkedList，否则 SingleLinkedList 更好。

4

6 回答 6

3

LinkedList 是第一次尝试，但是启用/禁用按钮和维护状态变得有点复杂，所以我找到了更好的方法。

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

可以撤消/重做条件很简单

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

修改时，我们必须清除 redoStack，因为我们修改活动文档中的任何内容，您可以在 VS 中清楚地注意到这一点，当您编辑任何内容时，redo 会被禁用。

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

撤消时

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

重做时

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

同样可以用链表实现，但管理头尾和维护当前指针变得复杂。

阅读您的观点后，我认为您可以使用单链表来实现撤消和重做堆栈，因为您只需要一个方向指针。我只是给你一个不同的方法来看看如何使用堆栈（单链表）来解决这个问题，它使用更少的内存并且没有与状态相关的问题。

于 2011-04-24T12:55:03.070 回答
3

现在使用 LinkedList 或任何标准解决方案，但要小心如何实现它。将所有撤消/重做操作放在精心设计的抽象后面。然后，如果 LinkedList 消耗的额外内存确实被证明是一个问题（不太可能），您可以用您自己的实现替换它。

我们一直这样做；将现有功能包装在抽象中，以便我们可以在需要时对其进行修补，因为有时特定于域的条件可能会提供额外效率的机会。这是您的情况；链接列表将起作用，但您的问题域表明效率可能会以实施为代价。

于 2011-04-24T11:59:56.200 回答
2

如果你想要一个链表，你应该使用LinkedList. 为什么要重写已经存在的代码？节省 16MB 的内存？

于 2011-04-24T11:41:42.183 回答
1

正如我所说和其他人所建议的那样，每个节点有 1 个成瘾指针而不是数组并不是一个大问题，也让我们假设我们的值是另一个指针，如果有 60000 个命令，我们每个节点有 8 个字节。480 KB，如果我们考虑一下，这个值真的很低。

也就是说，我认为在这种情况下最好的集合是 SingleLinkedList，允许我们无限制地撤消/重做“堆栈”（围绕 SingleLinkedList 构建）。

如果有必要限制我们的堆栈大小，则需要一个 LinkedList。

于 2011-04-26T13:13:53.673 回答
0

您可以使用具有旋转 startindex 和 endindex 值的数组。抽象同步类方法中的元素检索和添加过程，该方法还维护 startIndex 和 endIndex，该方法只会增加 ao(2) 内存而不是普通数组支持的堆栈。

于 2013-04-19T12:09:44.013 回答
0

我会给出一个奇怪的答案，然后说“随便你”，因为这通常不是性能关键的情况，尤其是在历史有限的情况下，当达到 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%）并提高了引用的局部性。

于 2018-01-18T06:16:38.607 回答