効率的な挿入/削除を伴う「リスト」

Question

インデックスiにlog（N）挿入/削除を含む「リスト」を探しています。私は実際のHaskellリストではないが、束のオブジェクトを持つ任意の順序付けされたコンテナ（実際には、内部的に何らかの種類のツリーが必要になるだろうから）という言葉を引用符で囲んでいる。私はまだ偉大な解決策を見つけられなかったことに驚いています....

これは私がこれまでに持っていた最高の解決策です。これらの2つの機能でData.Sequenceを使用してください。

doInsert position value seq = before >< (value <| after) 
    where 
    (before, after) = splitAt position seq 

doDelete position seq = before >< (drop 1 after) 
    where 
    (before, after) = splitAt position seq 

これらは技術的にすべてのログ（N）の機能ですが、私は削除/各挿入のための余分なものの束をやっているように、それは感じている....言い換えれば、これはKのようなスケール*ログ（N ）はKよりも大きくなければなりません。さらに、私は自分自身でこのことを定義しなければならないので、私はSequenceを使っていないような気がします。

良い方法がありますか？

これは、関連する質問（それは配列のみを扱うが、私は喜んで何かを使用する）である：Why doesn't Data.Sequence have `insert' or `insertBy', and how do I efficiently implement them?

そして、はい、この質問は、私は数日前に投稿この他の1に関連している：Massive number of XML edits

Answer 1

定義済みのHaskellリストで慎重に作業する場合は、問題はありません。 （たとえば、2つのリストを連結する場合）。

リストの実装を効率的に挿入して削除するには、AVLTreeや任意の種類のバランスのとれたバイナリツリーが有効です。 たとえば、AVLTreeにタプル（Int、a）を格納します。ここで、Intはリストのインデックスであり、elemです。 したがって、平均的な複雑さでは、操作は挿入と削除の対数になります。

これがあなたの質問に答えることを願っています。

Answer 2

O（1）に参加することができるcatenable seqs、catenable queuesなどの構造があります。しかし、私が知っているこのような構造はすべて、あなたにO（i）分割を与えることによってこれを取り除くものです。可能な限り分割して両方を最適にするには、fingerertree（別名Sequence）をお勧めします。 Sequenceの全体的なポイントは、分割や結合などが分割や結合などのときに行うべき漸進的にひどい量のジャグリングを確実にすることです。

場合離れスパース始めと密になった、と物事はがあなたに、より良い性能を与えるかもしれないと、その後、あまりにも密に着いたとき、時折、「再構築」したIntMapで得ることができる - しかし、それは本当にあなたに依存使用のパターン。