なぜData.Sequence.reverse O（n）ですか？

Question

文書ではData.Sequence.reverseはO（n）です。有限シーケンス型をフラグを設定することによって "反転"できないか？ （事実上、から「カウントを開始」するために、エンドいる。）

Answer 1

フラグが1つだけの場合、問題が発生します。私はそれを計算することができる方法

xs <> reverse xs 

たいと？ただ1つのフラグで、追加する前に高価な逆を実行する必要があります。実際にこれを行うには右、より多くの旗が必要です。 すべて木の周り。ツリー内のすべてのノードは、反転情報を運ぶ必要があります。これは間違いなく可能ですが、いくらか高価です。さらに悪いことに、すべての操作のすべてのステップで、反転フラグを適切に管理する必要があります。これは、誰でもコードを記述して維持する必要があります。このアイデアはどこかの紙の中で作られています（私はどちらが覚えていないのですか）が、実際には楽しいことではありません。

本質的に反転に依存するアルゴリズムを使用している場合は、多くのフラグを持つカスタムシーケンスタイプを使用し、必要な操作だけを含める必要があります（タイプをData.Sequenceに設定している場合は、各サイズフィールドから1ビット）。しかし、私はそのようなアルゴリズムはあまり一般的ではないと思う。

Answer 2

さてあなたは

data S a = S { forward :: Seq a , backward :: Seq a } 

を定義し、これはそれぞれのコストを倍増

forall a :: Type, s :: S a : reverse (forward s) == backward s . 

という不変ですべての操作を実装することができ一定時間はreverseとなる。

Answer 3

はい、可能です。

しかし、これにより、すべてのルックアップに小さな値段が追加されます（最初にフラグをチェックする必要があります）。また、reverseを使用するユーザーにのみ支払いが行われます。この後者のグループはおそらく小さいと判断された。タイプに適切なフラグを投げることはクライアント側で行うことができるので、はではなく、すべての関数を使用するたびにライブラリでこの値段を支払うことになります。代わりに、reverseをたくさん呼びたいプログラマーは、望むのであればこのパフォーマンスのトレードオフの選択肢を作ることを余儀なくされます。これは私には完全に賢明です。

Answer 4

><連結がペナルティなしでxs >< reversed ysの連結を認めている場合は、O(1)で完了すると思います（フィンガーツリー構造に何らかのハックが必要です）。すべての操作は逆の対応（例えばtakeWhileL〜takeWhileR）を持っているか、O(n)取るData.Sequenceに探し

; ><操作を除いて（または最悪を。例えばzipはseq1ときn1<n2などを逆にし、O(min(n1,n2))を取ります）。

いずれにしても、xs >< ysは、最悪の場合（4つの可能なケースのうちの2つ）としてO(min(|xs|,|ys|))になります。これは実際にはO(n)より少し優れています（ユニークな方向への正規化と反転が必要です）。

その後、質問は次のとおりです。

はO(min(|xs|,|ys|))より良いxs >< reversed ysを行うことができますか？

（理想的にO(log(min(|xs|,|ys|)))）もちろん

、あなたが><操作を使用しない場合は、逆の操作を取るO(1)（例えば使用が左または右に対応するときチェックするためにフラグを使用）。

一方、逆順シーケンスのパフォーマンスを連結することが重要な場合は、おそらく他の最適な構造が存在するか、または@d8d0d65b3f7cf42 strategyと考えることができます。