Warum ist Data.Sequence.Reverse O (n)?

Question

Die Dokumente sagen Data.Sequence.reverse ist O (n). Könnte ein endlicher Sequenztyp nicht durch das Setzen eines Flags "umgekehrt" werden? (Effektiv, das Ende der „beginnen zu zählen“ aus.)

Answer 1

Wenn Sie nur eine Flagge haben, werden Sie Probleme haben. Angenommen, ich möchte

xs <> reverse xs 

Wie könnte ich das berechnen? Mit nur einer Flagge müsste ich vor dem Anfügen eine teure Umkehrung durchführen. Um dies zu tun rechts, brauchen Sie mehr Fahnen, verteilt um den Baum. Alle um den Baum herum. Jeder Knoten im Baum muss Umkehrinformationen enthalten. Dies ist definitiv möglich, aber es ist etwas teuer. Schlimmer noch, jeder Schritt jeder Operation muss die Umkehrflags entsprechend verwalten, was für jeden, der den Code schreiben und pflegen muss, ein Albtraum ist. Diese Idee wurde irgendwo in einer Zeitung ausgearbeitet (ich erinnere mich nicht daran), aber es macht keinen Spaß in der Praxis.

Wenn Sie einen Algorithmus haben, der im Wesentlichen auf Umkehrung beruht, sollten Sie einen benutzerdefinierten Sequenztyp mit vielen Flags verwenden und nur die benötigten Operationen einschließen (wenn Sie Ihren Typ auf Data.Sequence basieren, sollten Sie wahrscheinlich stehlen ein Bit von jedem Größenfeld). Aber ich denke nicht, dass solche Algorithmen sehr verbreitet sind.

Answer 2

Nun, Sie

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

definieren könnten und implementieren dann alle Operationen mit den Invarianten, dass

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

Dadurch verdoppeln ich die Kosten für jeden , gibt aber konstante Zeit reverse.

Answer 3

Ja, könnte es.

Allerdings fügt dies einen kleinen Preis zu jeder Suche hinzu (man muss zuerst die Flagge überprüfen!), Und die Auszahlung kommt nur zu Benutzern, die reverse viel verwenden. Diese letztere Gruppe wurde wahrscheinlich als klein beurteilt. Da die entsprechende Flagge auf den Typ geworfen werden kann, macht es Sinn nicht diesen Preis in der Bibliothek für jede Verwendung jeder Funktion zu bezahlen. Stattdessen ist der Programmierer, der beabsichtigt, reverse viel anzurufen, gezwungen, diese Leistung Kompromisswahl zu treffen, wenn sie es wollen, was für mich vollkommen vernünftig scheint.

Answer 4

ich denken konnte, in O(1) erfolgen, wenn die >< Verkettung verketten zugeben xs >< reversed ys ohne penalization (etwas Hack erforderlich in fingerBaumStruktur).

Mit Blick auf Data.Sequence alle Operationen haben ein Reverse-Gegenstück (zB takeWhileL ~ takeWhileR.) Oder nehmen O(n) (oder schlimmsten Fall,. ZB zipO(min(n1,n2)) nehmen dann umkehren, wenn seq1n1<n2 und so) außer >< Betrieb.

In jedem Fall wird xs >< ysO(min(|xs|,|ys|)) als schlimmsten Fall (zwei von vier möglichen Fällen) nehmen. Dies ist in der Praxis ein wenig besser als O(n) (Normalisieren in eine eindeutige Richtung und Rückwärtsfahren wird immer benötigt).

Dann ist die Frage:

Kann xs >< reversed ys besser als O(min(|xs|,|ys|)) getan werden?

(idealerweise O(log(min(|xs|,|ys|))))

Natürlich, wenn Sie nicht >< Betrieb nicht verwenden, der umgekehrte Vorgang nimmt O(1) (zB. Eine Flagge mit zu überprüfen, wenn links oder rechts Verwendung Gegenstück).

Auf der anderen Seite, wenn verkettete umgekehrte Sequenzen Leistung ist kritisch, existiert wahrscheinlich eine andere optimale Struktur oder Sie können @d8d0d65b3f7cf42 strategy verwenden.