computer-science - ランレングスエンコーディングのC#LinkedListとリスト?

Question

これらのうち、バイトの RLE に適しているのはどれですか? リストにデータをかなり迅速に挿入できる必要がありますが、圧縮されていないバイト 3987 の場所をすばやく見つける必要もあります (これはおそらくより重要です。最善の方法は、すべての3987 未満の最も近いものを取得するまでカウントしますか?)。

Answer 1

検索する以上に挿入することになると思いますか? それぞれのアプローチは、他のアプローチよりも優れているからです。

LinkedList ノードは次のようになると思います。

class RleNode { Byte Value; Int32 Length; RleNode Prev; RleNode Next; }

迅速な挿入が必要な場合は、リンクされたリスト構造を使用する必要があります。

計算された位置によるルックアップを高速化するには、リンク リスト構造をマップ インデックスと結合する新しいクラスにカプセル化します。インデックスは、挿入ごとに再構築する必要があります。

編集：

木の方がもっと速いのではないでしょうか。ツリーの DFS トラバーサルを使用して線形 RLE ストリームを再構築します。ツリーを使用すると、各親ノードはその子の RLE の長さの合計を格納できるため、構造全体の RLE の長さを再計算することなく挿入を行うことができ、検索も同様に高速になります。

この質問を C# ではなくコンピューター サイエンスとしてタグ付けし直すことをお勧めします。