c# - Undo / Redoを実装するための良いコレクションですか？

Question

私は元に戻る/やり直しのテクニックを読んでいましたが、それをどのように実装すべきかを理解しています（直感的だと思いました）。

しかし、私は歴史として使われるべきコレクションについて考えています、

多くの人がスタックを使用しますが、C＃スタックは配列として実装されており、これは問題です。「制限された」履歴を使用する場合（たとえば、2000コマンドの場合）、制限に達したときに、スタックの最後からアイテムを削除する方法。それを行う方法を見つけた場合は、配列のすべての要素を移動する必要があります（コマンドが実行されるたびにこれを移動します）。

LinkedListは見栄えがしますが、多くのメモリを浪費します。

私の最後のオプションは、リンクリスト、SingleLinkedListのカスタム実装です。このリストのノードはValueプロパティとNextNodeポインタプロパティで構成されているため、各アイテムにダブルメモリを使用しています（ただし、「sizeof（void *）」よりも小さいものを使用している場合を除いて、それ以上は使用しません）。

コレクションの最初の要素へのポインターと最後の要素へのポインターも格納しています。

この方法でコマンドを履歴に簡単に追加してREDO履歴に移動できますが、RemoveLastが許可されていないため、「制限付き」履歴を作成できません（最後のアイテムを削除するには、コレクション全体を調べる必要があります）。

だから私の質問は：LinkedListまたはカスタムSingleLinkedListを使用する必要がありますか？

アップデート1：

現時点で回答をありがとうございます。私の状況では、メモリの問題はありません。誰をターゲットにしているのかわかりません。ユーティリティプログラムを作成しています。私自身の「ユーティリティプログラム」のアイデアでは、可能な限り最小限のCPU/メモリを浪費する必要があります（大きな違いがあるので、明らかに「c ++で書く」とは言わないでください）。

私の意見では、singlelinkedlistはうまく機能します。履歴を制限するのは好きではありません。あなたの履歴が「無制限」である、Photoshopについて考えています。

私は、8時間の使用のように、元に戻す履歴が本当に大きくなったときに何が起こるかを恐れているだけです。そのため、LinkedListを使用して制限することを考えていました。

ただし、他の誰かが述べたように、リンクリストを大きなサイズ、約60000コマンド（十分なはずだと思います）に制限すると、シングルリンクリストと比較して、わずかなメモリ（4バイト* 60000）しか無駄になりません。

そうは言っても、私はLinkedListを使用すると思いますが、念のために言っておきますが、無制限に履歴を使用していれば大丈夫でしたか？

アップデート2：

@Akash Kavaええと、あなたが言うことは重要ですが、なぜLinkedListを使用したいのか、なぜスタックを使用したくないのかを誤解していました。Stackの主な問題は、サイズを制限する必要があることです。この制限に達したときに古いコマンドをすばやく削除する方法はありません（これは配列であり、必要なものではないたびに次元が2倍になります）。

単一のリンクリスト（どのように構築されるかを考えてください）はスタックとして高速であり（すべてのスタック操作はO（1）です）、制限はありません。ただし、この場合、制限を設ける必要はありません。そうしないと、スタックと同じ問題が発生します。わからないため、singlelinkedlistの最後の要素（スタックのように動作します）をすばやく削除する方法がありません。最後のノードからの前のノード要素。

この場合、非常に簡単なので、PreviousポインターがあるLinkedListについて考えることができます。ただし、「スタック」（今回はリンクリストを介して構築されます）の各要素に2つの追加のポインターを使用しています。これは、コマンドを格納するために必要なメモリの3倍のメモリを使用するようなものです（通常のメモリを備えた配列を使用）。使用量、singlelinkedlistのメモリ使用量は2倍、linkedlistのメモリ使用量は3倍です）。

だから私が基本的に求めていたのは、元に戻るパターンのスタックを実装するための「最良の」コレクションはどれかということです。

あなたの答えは、私が1つのプログラムで60000のコマ​​ンドを作成したとしても、それはプログラムの約5MBのメモリであり、それほど多くはないと思いました。

基本的に、元に戻す/やり直しの履歴を制限したい場合は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で明確に確認できます。何かを編集すると、REDOは無効になります。

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

元に戻している間

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

やり直し中

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

リンクリストでも同じように実装できますが、ヘッドとテールの管理と現在のポインタの維持が複雑になります。

ポイントを読んだ後、必要な方向ポインターは1つだけなので、単一のリンクリストを使用してundoおよびredoスタックを実装できると思います。使用するメモリが少なく、状態に関連する問題がないスタック（単一のリンクリスト）を使用してこれを解決する方法を確認する別の方法を紹介しました。

Answer 3

リンクリストが必要な場合は、を使用する必要がありますLinkedList。なぜすでに存在するコードを書き直すのですか？16MBのRAMを節約するには？

Answer 4

私が述べたように、そして他の誰かが示唆したように、配列の代わりにノードごとに1つの中毒性のあるポインターを持つことは大きな問題ではありません。また、60000コマンドの場合、ノードごとに8バイトがあるので、値が別のポインターであると仮定しましょう。480 KB、考えてみると非常に低い値です。

そうは言っても、この場合の最良のコレクションはSingleLinkedListであり、無制限の元に戻す/やり直しの「スタック」（SingleLinkedListを中心に構築）を可能にします。

スタックサイズを制限する必要がある場合は、LinkedListが必要です。

Answer 5

startindexとendindexの値が回転する配列を使用することをお勧めします。startIndexとendIndexも維持する同期クラスメソッドで要素の取得と追加のプロセスを抽象化します。このメソッドでは、単純な配列でバックアップされたスタックではなく、メモリがao（2）増加します。

Answer 6

私は奇妙な答えを出して、「あなたが望むものは何でも」と言います。これは一般にパフォーマンスが重要なケースではないためです。特に、2000回の取り消し可能な操作に達したときに最も古いエントリが飛び出し始める限られた履歴があるためです。

二重リンクリストは正常に機能します。両端キューは正常に機能します。ArrayList線形時間で前面から削除する必要があるような連続した構造は、各操作がそれに格納されているオブジェクト参照である場合でも、問題なく機能する可能性があります。記録できる元に戻す操作の数に固定の制限がある場合は、循環配列も適切に機能します（この場合、事前に循環配列のサイズを設定でき、特定のエントリを超えると、最も古いエントリの上書きが自動的に開始されます容量）。

これで行うのは、ユーザー操作全体に対して1回プッシュバックすることだけなので、元に戻す操作全体に対して1回ポップバックし、ユーザーが操作を記録して履歴がいっぱいになり始めた場合は、要素を前面からポップするか、あまりにも多くのメモリを使用しています。パフォーマンスはまったく重要ではありません。ユーザーが1秒あたり1万回の操作を記録できるという非常に珍しいケースがない限り（誰かがこれほど速くクリックするのを見るだけでかなり感動します）、ユーザー入力に非常に拘束されるため、発生する可能性はそれほど多くありません。

もちろん、単一の元に戻す操作内に保存するものは、パフォーマンスが非常に重要になる可能性があり、メモリ使用量を最小限に抑える非常に効率的なデータ表現が必要になる場合があります（元にできるエントリ内に保存する状態の量によって異なります）。しかし、外側の元に戻るスタック/履歴は、実際にはパフォーマンスにそれほど重要ではありません。そのような場合は、ほぼすべてのオプションが妥当だと思います。これは、パフォーマンスを向上させるためにメモリ使用量を減らすのが好きな人から来ていますが、この場合、アンドゥスタックメモリは「コールド」です。非常に限られたハードウェアを対象としている場合を除き、ユーザーが元に戻すボタンを押すか、新しい操作を記録したときに、その多くに頻繁にアクセスすることはありません（例：すべてのフレームにアクセスするわけではありません）。

しかし、私が本当に必要とは思わないものを押しつぶしたいのであれば、展開されたリンクリストのようなものは非常にうまくいく可能性があります。これは基本的に、各ノードが複数の要素を内部に格納するリンクリストです。その場合、リンクのメモリ使用は簡単です。あなたはこのようなことをすることができます：

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

last元に戻すと、テールノードのカウンターをデクリメントできます。の場合last == firstは、それをポップして解放し、前のノードを新しいテールにします。last操作を記録するときに、カウンターをインクリメントできます。の場合last == n、新しいノードを割り当て、それを新しいテールにします。履歴のサイズを縮小し始めたい場合（つまり、元に戻るエントリを前面から削除したい場合）、firstヘッドノードのカウンターをインクリメントします。の場合first == last、ノードの割り当てを解除し、次のノードを新しいヘッドとして設定します。これにより、元に戻るごとにリンクのようなノードデータを保存する必要がないため、元に戻るごとにほとんどメモリを使用せずに、一定時間のプッシュバック、ポップバック、およびポップフロントが提供されます（保存するすべての取り消しエントリに対して1回だけn、作成できますn512のような大きな数で、リンクリストのオーバーヘッドを1/512または約1.95％に減らし、参照の局所性を改善します。