Warum hat std :: list :: reverse O (n) Komplexität?

192

Warum hat die Umkehrfunktion für die std::listKlasse in der C ++ - Standardbibliothek eine lineare Laufzeit? Ich würde denken, dass für doppelt verknüpfte Listen die Umkehrfunktion O (1) gewesen sein sollte.

Das Umkehren einer doppelt verknüpften Liste sollte nur das Umschalten der Kopf- und Endzeiger beinhalten.

Neugierig
quelle
18
Ich verstehe nicht, warum die Leute diese Frage ablehnen. Es ist eine völlig vernünftige Frage. Das Umkehren einer doppelt verknüpften Liste sollte O (1) Zeit in Anspruch nehmen.
Neugierig
46
Leider verwechseln einige Leute die Konzepte "die Frage ist gut" mit "die Frage hat eine gute Idee". Ich liebe Fragen wie diese, bei denen im Grunde genommen "mein Verständnis anders zu sein scheint als eine allgemein akzeptierte Praxis, bitte helfen Sie, diesen Konflikt zu lösen", weil die Erweiterung Ihrer Denkweise Ihnen hilft, viel mehr Probleme in der Zukunft zu lösen! Es scheint, dass andere den Ansatz verfolgen, "das ist in 99,9999% der Fälle eine Verschwendung von Verarbeitung, denken Sie nicht einmal darüber nach". Wenn es ein Trost ist, wurde ich für viel, viel weniger herabgestimmt!
CorsiKa
4
Ja, diese Frage hat eine übermäßige Anzahl von Abstimmungen für ihre Qualität erhalten. Wahrscheinlich ist es dasselbe, wer Blindys Antwort positiv bewertet hat. Fairerweise gilt "das Umkehren einer doppelt verknüpften Liste sollte nur das Umschalten der Kopf- und Endzeiger beinhalten" im Allgemeinen nicht für die standardmäßige verknüpfte Liste, die jeder in der Schule lernt, oder für viele Implementierungen, die von Menschen verwendet werden. Viele Male in der unmittelbaren Bauchreaktion von SO-Leuten auf die Frage oder Antwort führt dies zu einer Entscheidung über Upvote / Downvote. Wenn Sie in diesem Satz klarer gewesen wären oder ihn weggelassen hätten, hätten Sie wahrscheinlich weniger Abstimmungen erhalten.
Chris Beck
3
Oder lassen Sie mich die Beweislast bei Ihnen tragen, @Curious: Ich habe hier eine doppelt verknüpfte Listenimplementierung erstellt : ideone.com/c1HebO . Können Sie angeben, wie Sie erwarten würden, dass die ReverseFunktion in O (1) implementiert wird?
CompuChip
2
@CompuChip: Abhängig von der Implementierung ist dies möglicherweise nicht der Fall. Sie benötigen keinen zusätzlichen Booleschen Wert, um zu wissen, welcher Zeiger verwendet werden soll: Verwenden Sie einfach den Zeiger, der nicht auf Sie zurückweist. Dies könnte übrigens automatisch mit einer XOR-verknüpften Liste erfolgen. Ja, es hängt davon ab, wie die Liste implementiert wird, und die OP-Anweisung könnte geklärt werden.
Matthieu M.

Antworten:

187

Hypothetisch reversekönnte O (1) gewesen sein . Es könnte (wieder hypothetisch) ein boolesches Listenmitglied gegeben haben, das angibt, ob die Richtung der verknüpften Liste derzeit dieselbe oder entgegengesetzt zu der ursprünglichen ist, in der die Liste erstellt wurde.

Leider würde dies die Leistung grundsätzlich jeder anderen Operation verringern (allerdings ohne die asymptotische Laufzeit zu ändern). Bei jeder Operation müsste ein Boolescher Wert herangezogen werden, um zu prüfen, ob einem "nächsten" oder "vorherigen" Zeiger eines Links gefolgt werden soll.

Da dies vermutlich als relativ seltene Operation angesehen wurde, spezifizierte der Standard (der keine Implementierungen vorschreibt, sondern nur die Komplexität), dass die Komplexität linear sein könnte. Dies ermöglicht, dass "nächste" Zeiger immer eindeutig dieselbe Richtung bedeuten, was Operationen im allgemeinen Fall beschleunigt.

Ami Tavory
quelle
29
@ MooseBoys: Ich stimme deiner Analogie nicht zu. Der Unterschied besteht darin , dass im Fall einer Liste, die Umsetzung zur Verfügung stellen könnte reversemit der O(1)Komplexität des Big-os eines anderen Betriebes ohne Beeinträchtigung durch diesen Flag mit dem angegebenen Trick. In der Praxis ist jedoch eine zusätzliche Verzweigung bei jeder Operation kostspielig, selbst wenn es sich technisch um O (1) handelt. Im Gegensatz dazu können Sie keine Listenstruktur erstellen, in der sortO (1) ist und alle anderen Operationen die gleichen Kosten verursachen. Der Punkt der Frage ist, dass Sie anscheinend O(1)kostenlos rückgängig machen können, wenn Sie sich nur für Big O interessieren. Warum haben sie das nicht getan?
Chris Beck
9
Wenn Sie eine XOR-verknüpfte Liste verwenden, wird das Umkehren zu einer konstanten Zeit. Ein Iterator wäre jedoch größer, und das Inkrementieren / Dekrementieren wäre etwas rechenintensiver. Dies könnte jedoch durch die unvermeidbaren Speicherzugriffe für jede Art von verknüpfter Liste in den Schatten gestellt werden.
Deduplikator
3
@IlyaPopov: Braucht das eigentlich jeder Knoten? Der Benutzer stellt niemals Fragen an den Listenknoten selbst, sondern nur an den Hauptlistenkörper. Der Zugriff auf den Booleschen Wert ist daher für jede vom Benutzer aufgerufene Methode einfach. Sie können beispielsweise festlegen, dass die Iteratoren ungültig werden, wenn die Liste umgekehrt wird, und / oder eine Kopie des Booleschen Werts mit dem Iterator speichern. Ich denke also, dass es das große O nicht unbedingt beeinflussen würde. Ich gebe zu, ich habe die Spezifikation nicht Zeile für Zeile durchgearbeitet. :)
Chris Beck
4
@ Kevin: Hm, was? Sie können ohnehin nicht zwei Zeiger direkt xor, Sie müssen sie zuerst in ganze Zahlen konvertieren (offensichtlich vom Typ std::uintptr_t. Dann können Sie sie xor.
Deduplicator
3
@ Kevin, Sie könnten definitiv eine XOR-verknüpfte Liste in C ++ erstellen, es ist praktisch die Sprache für Aushängeschilder für solche Dinge. Nichts sagt, dass Sie verwenden müssen std::uintptr_t, Sie könnten in ein charArray umwandeln und dann die Komponenten XOR. Es wäre langsamer, aber 100% tragbar. Wahrscheinlich können Sie zwischen diesen beiden Implementierungen wählen und die zweite nur dann als Ersatz verwenden, wenn sie uintptr_tfehlt. Einige, wenn es in dieser Antwort beschrieben wird: stackoverflow.com/questions/14243971/…
Chris Beck
61

Es könnte sein , O (1) , wenn die Liste ein Flag speichern würde , die die Bedeutung der „ermöglicht Swapping prev“ und „ next“ Zeiger jeder Knoten. Wenn das Umkehren der Liste eine häufige Operation wäre, könnte eine solche Hinzufügung tatsächlich nützlich sein, und ich kenne keinen Grund, warum die Implementierung nach dem aktuellen Standard verboten wäre . Ein solches Flag würde jedoch das gewöhnliche Durchlaufen der Liste verteuern (wenn auch nur um einen konstanten Faktor), weil statt

current = current->next;

im der operator++Liste Iterator würden Sie bekommen

if (reversed)
  current = current->prev;
else
  current = current->next;

Das ist nicht etwas, das Sie einfach hinzufügen möchten. Angesichts der Tatsache, dass Listen normalerweise viel häufiger durchlaufen werden als umgekehrt, wäre es für den Standard sehr unklug, dies zu tun beauftragen , diese Technik. Daher darf die umgekehrte Operation eine lineare Komplexität aufweisen. Beachten Sie jedoch, dass tO (1) ⇒ tO ( n ) ist, sodass, wie bereits erwähnt, die technische Implementierung Ihrer „Optimierung“ zulässig ist.

Wenn Sie aus Java oder einem ähnlichen Hintergrund stammen, fragen Sie sich möglicherweise, warum der Iterator das Flag jedes Mal überprüfen muss. Könnten wir nicht stattdessen zwei unterschiedliche Iteratortypen haben, die beide von einem gemeinsamen Basistyp abgeleitet sind std::list::beginund std::list::rbeginden entsprechenden Iterator haben und polymorph zurückgeben? Während dies möglich wäre, würde dies das Ganze noch schlimmer machen, da das Vorrücken des Iterators jetzt ein indirekter (schwer zu inline) Funktionsaufruf wäre. In Java zahlen Sie diesen Preis ohnehin routinemäßig, aber dies ist einer der Gründe, warum viele Menschen nach C ++ greifen, wenn die Leistung kritisch ist.

Wie Benjamin Lindley in den Kommentaren reversehervorhob, scheint der einzige Ansatz, der vom Standard zugelassen wird, darin zu bestehen, einen Zeiger zurück auf die Liste im Iterator zu speichern, was einen doppelt indirekten Speicherzugriff verursacht.

5gon12eder
quelle
7
@galinette: std::list::reversemacht Iteratoren nicht ungültig.
Benjamin Lindley
1
@galinette Entschuldigung, ich habe Ihren früheren Kommentar als "Flag pro Iterator " falsch gelesen, im Gegensatz zu "Flag pro Knoten ", wie Sie ihn geschrieben haben. Natürlich wäre ein Flag pro Knoten kontraproduktiv, da Sie wiederum eine lineare Durchquerung durchführen müssten, um sie alle umzudrehen.
5gon12eder
2
@ 5gon12eder: Sie können die Verzweigung zu sehr verlorenen Kosten beseitigen: Speichern Sie die Zeiger nextund previn einem Array und die Richtung als 0oder 1. Um vorwärts zu iterieren, folgen Sie pointers[direction]und iterieren rückwärts pointers[1-direction](oder umgekehrt). Dies würde immer noch ein wenig Overhead hinzufügen, aber wahrscheinlich weniger als ein Zweig.
Jerry Coffin
4
Sie können wahrscheinlich keinen Zeiger auf die Liste in den Iteratoren speichern. swap()wird als konstante Zeit angegeben und macht keine Iteratoren ungültig.
Tavian Barnes
1
@TavianBarnes Verdammt! Nun, dreifache Indirektion dann ... (Ich meine, nicht wirklich dreifach. Sie müssten das Flag in einem dynamisch zugewiesenen Objekt speichern, aber der Zeiger im Iterator kann natürlich direkt auf dieses Objekt zeigen, anstatt indirekt über die Liste zu indirekt.)
5gon12eder
37

Da alle Container, die bidirektionale Iteratoren unterstützen, das Konzept von rbegin () und rend () haben, ist diese Frage sicherlich umstritten.

Es ist trivial, einen Proxy zu erstellen, der die Iteratoren umkehrt und über diesen auf den Container zugreift.

Diese Nichtoperation ist in der Tat O (1).

sowie:

#include <iostream>
#include <list>
#include <string>
#include <iterator>

template<class Container>
struct reverse_proxy
{
    reverse_proxy(Container& c)
    : _c(c)
    {}

    auto begin() { return std::make_reverse_iterator(std::end(_c)); }
    auto end() { return std::make_reverse_iterator(std::begin(_c)); }

    auto begin() const { return std::make_reverse_iterator(std::end(_c)); }
    auto end() const { return std::make_reverse_iterator(std::begin(_c)); }

    Container& _c;
};

template<class Container>
auto reversed(Container& c)
{
    return reverse_proxy<Container>(c);
}

int main()
{
    using namespace std;
    list<string> l { "the", "cat", "sat", "on", "the", "mat" };

    auto r = reversed(l);
    copy(begin(r), end(r), ostream_iterator<string>(cout, "\n"));

    return 0;
}

erwartete Ausgabe:

mat
the
on
sat
cat
the

In Anbetracht dessen scheint es mir, dass sich das Normungskomitee keine Zeit genommen hat, um O (1) die umgekehrte Reihenfolge des Containers zu bestimmen, da dies nicht erforderlich ist, und die Standardbibliothek basiert weitgehend auf dem Prinzip, nur das zu beauftragen, was währenddessen unbedingt erforderlich ist Vermeidung von Doppelarbeit.

Nur mein 2c.

Richard Hodges
quelle
18

Weil es jeden Knoten ( ninsgesamt) durchlaufen und seine Daten aktualisieren muss (der Aktualisierungsschritt ist in der Tat O(1)). Dies macht den gesamten Vorgang O(n*1) = O(n).

Blind
quelle
27
Weil Sie auch die Links zwischen den einzelnen Elementen aktualisieren müssen. Nehmen Sie ein Stück Papier heraus und ziehen Sie es heraus, anstatt es abzustimmen.
Blindy
11
Warum fragen Sie, ob Sie sich dann so sicher sind? Sie verschwenden unsere Zeit.
Blindy
28
@Curious Die Knoten der doppelt verknüpften Liste haben einen Orientierungssinn. Grund von dort.
Schuh
11
@Blindy Eine gute Antwort sollte vollständig sein. "Nehmen Sie ein Stück Papier heraus und ziehen Sie es heraus" sollte daher kein notwendiger Bestandteil einer guten Antwort sein. Antworten, die keine guten Antworten sind, werden abgelehnt.
RM
7
@ Schuh: Müssen sie? Bitte recherchieren Sie die XOR-verknüpfte Liste und dergleichen.
Deduplikator
2

Außerdem werden der vorherige und der nächste Zeiger für jeden Knoten ausgetauscht. Deshalb braucht es Linear. Obwohl dies in O (1) möglich ist, wenn die Funktion, die dieses LL verwendet, auch Informationen über LL als Eingabe verwendet, z. B. ob sie normal oder umgekehrt zugreift.

techcomp
quelle
1

Nur eine Algorithmuserklärung. Stellen Sie sich vor, Sie haben ein Array mit Elementen und müssen es dann invertieren. Die Grundidee besteht darin, bei jedem Element zu iterieren und das Element an der ersten Position in die letzte Position, das Element an der zweiten Position in die vorletzte Position usw. zu ändern. Wenn Sie in die Mitte des Arrays gelangen, werden alle Elemente geändert, also in (n / 2) Iterationen, die als O (n) betrachtet werden.

Danilobraga
quelle
1

Es ist O (n), einfach weil es die Liste in umgekehrter Reihenfolge kopieren muss. Jede einzelne Elementoperation ist O (1), aber es gibt n davon in der gesamten Liste.

Natürlich sind einige Operationen mit konstanter Zeit erforderlich, um den Platz für die neue Liste einzurichten und anschließend die Zeiger zu ändern usw. Die O-Notation berücksichtigt keine einzelnen Konstanten, sobald Sie einen n-Faktor erster Ordnung einschließen.

SDsolar
quelle