Warum ist das Hinzufügen zu einer Liste schlecht?

Question

Ich habe vor kurzem angefangen, scala zu lernen, und ich bin auf die :: (Nachteile) -Funktion gestoßen, die zu einer Liste vorangeht.
In dem Buch „Programming in Scala“ heißt es, dass es keine Append-Funktion auf eine Liste, weil Anhängen ist Leistung o hat (n), während das Voranstellen einer Leistung von o hat (1)

Etwas fällt mir nur als falsch diese Aussage.

Ist die Leistung nicht von der Implementierung abhängig? Ist es nicht möglich, die Liste einfach mit Vorwärts- und Rückwärtsverknüpfungen zu implementieren und das erste und letzte Element im Container zu speichern?

Die zweite Frage, die ich vermute, ist, was ich tun soll, wenn ich eine Liste habe, sagen 1,2,3 und ich möchte 4 an das Ende davon hinzufügen?

Answer 1

Der Schlüssel ist, dass x :: somelist nicht somelist nicht mutieren, sondern schafft stattdessen eine neue Liste, die von allen Elementen der somelist gefolgt x enthält. Dies kann in O (1) Zeit erfolgen, da Sie in der neu erstellten, einfach verketteten Liste nur somelist als Nachfolger von x setzen müssen.

Wenn stattdessen doppelt verknüpfte Listen verwendet würden, müsste x auch als der Vorgänger von somelist 's Kopf festgelegt werden, der somelist ändern würde. Wenn wir also :: in O (1) machen können, ohne die ursprüngliche Liste zu ändern, können wir nur einfach verkettete Listen verwenden.

In Bezug auf die zweite Frage: Sie können ::: verwenden, um eine Liste mit einzelnen Elementen am Ende Ihrer Liste zu verketten. Dies ist eine O (n) -Operation.

List(1,2,3) ::: List(4) 

Answer 2

Voranstellen ist schneller, weil es nur zwei Operationen erfordert:

1. Erstellen Sie die neue Liste Knoten
2. haben, dass neue Knotenpunkt der bestehenden Liste

Anfügen von mehr Operationen erfordert, weil Sie um zum Ende der Liste zu gelangen, da Sie nur einen Zeiger auf den Kopf haben.

habe ich noch nie zuvor in Scala programmiert, aber man konnte eine List Buffer

Answer 3

Die meist funktionalen Sprachen prominent eine einfach verknüpfte Listendatenstruktur Abbildung versuchen, wie es Art eine handliche unveränderliche Sammlung ist. Wenn Sie in einer funktionalen Sprache "liste" sagen, ist das typisch, was Sie meinen (eine einfach verknüpfte Liste, normalerweise unveränderlich). Für solch einen Typ ist append O (n), während cons O (1) ist.

Answer 4

Andere Antworten haben gute Erklärungen für dieses Phänomen gegeben. Wenn Sie viele Elemente an eine Liste in einer Subroutine anhängen oder wenn Sie eine Liste durch Anfügen von Elementen erstellen, besteht ein Funktionsidiom darin, die Liste in umgekehrter Reihenfolge aufzubauen, wobei die Elemente auf der Front der Liste berücksichtigt werden , dann am Ende umkehren. Dies gibt Ihnen O (n) Leistung statt O (n²).

Answer 5

Da die Frage gerade aktualisiert wurde, ist es erwähnenswert, dass sich die Dinge hier geändert haben.

In der heutigen Scala können Sie einfach xs :+ x verwenden, um ein Element am Ende einer sequentiellen Sammlung anzuhängen. (Es gibt auch x +: xs vorangestellt wird. Die Mnemonik für viele 2.8+ Sammlung Operationen der Scala ist, dass die col geht weiter neben dem col lection.)

Dieses O sein (n) mit der Standard verknüpfte Implementierung von List oder Seq, aber wenn Sie Vector oder IndexedSeq verwenden, wird dies effektiv konstante Zeit sein. Scalas Vector ist wahrscheinlich Scalas nützlichste listenähnliche Sammlung - im Gegensatz zu Javas Vector, die heutzutage meistens nutzlos ist. Wenn Sie in Scala 2.8 oder höher arbeiten, ist das collections introduction ein absolutes Muss.