Unterschied zwischen Array und Liste in Scala

In welchen Fällen sollte ich Array (Puffer) und Liste (Puffer) verwenden. Ich weiß nur, dass Arrays nicht variabel und Listen kovariant sind. Aber was ist mit der Leistung und einigen anderen Eigenschaften?

Unveränderliche Strukturen

Die Scala Listist eine unveränderliche rekursive Datenstruktur, die in Scala eine so grundlegende Struktur darstellt, dass Sie sie (wahrscheinlich) viel häufiger verwenden sollten als eine Array(die tatsächlich veränderlich ist - das unveränderliche Analogon von Arrayist IndexedSeq).

Wenn Sie von einem Java - Hintergrund kommen, dann ist die offensichtliche Parallele ist zu verwenden , wenn LinkedListüber ArrayList. Ersteres wird im Allgemeinen für Listen verwendet, die immer nur durchlaufen werden (und deren Größe im Voraus nicht bekannt ist), während letzteres für Listen verwendet werden sollte, die entweder eine bekannte Größe (oder maximale Größe) haben oder für die ein schneller Direktzugriff wichtig ist.

Mutable Strukturen

ListBufferbietet eine zeitkonstante Konvertierung zu a, Listwas allein Grund zur Verwendung ist, ListBufferwenn eine solche spätere Konvertierung erforderlich ist.

Eine Scala Arraysollte in der JVM von einem Java-Array implementiert werden, und daher Array[Int]kann eine Scala (als int[]) viel leistungsfähiger sein als eine List[Int](die ihren Inhalt verpackt, es sei denn, Sie verwenden die neuesten Versionen von Scala mit der neuen @specializedFunktion). .

Ich denke jedoch, dass die Verwendung von Arrays in Scala auf ein Minimum beschränkt werden sollte, da Sie wirklich wissen müssen, was unter der Haube vor sich geht, um zu entscheiden, ob Ihr Array wirklich durch den erforderlichen primitiven Typ unterstützt wird oder möglicherweise als Wrapper-Typ verpackt sein.

Zusätzlich zu den bereits veröffentlichten Antworten finden Sie hier einige Besonderheiten.

Während a Array[A]buchstäblich ein Java-Array ist, List[A]ist a eine unveränderliche Datenstruktur, die entweder Nil(die leere Liste) ist oder aus einem Paar besteht (A, List[A]).

Leistungsunterschiede

                          Array  List
Access the ith element    θ(1)   θ(i)
Delete the ith element    θ(n)   θ(i)
Insert an element at i    θ(n)   θ(i)
Reverse                   θ(n)   θ(n)
Concatenate (length m,n)  θ(n+m) θ(n)
Count the elements        θ(1)   θ(n)

Speicherunterschiede

                          Array  List
Get the first i elements  θ(i)   θ(i)
Drop the first i elements θ(n-i) θ(1)
Insert an element at i    θ(n)   θ(i)
Reverse                   θ(n)   θ(n)
Concatenate (length m,n)  θ(n+m) θ(n)

Wenn Sie also keinen schnellen Direktzugriff benötigen, keine Elemente zählen müssen oder aus irgendeinem Grund destruktive Aktualisierungen benötigen, Listist a besser als a Array.

Ein Array ist veränderbar, dh Sie können die Werte jedes Index ändern, während eine Liste (standardmäßig) unveränderlich ist. Dies bedeutet, dass bei jeder Änderung eine neue Liste erstellt wird. In den meisten Fällen ist es ein „funktional“ Stil der Arbeit mit unveränderlichen Datentypen und Sie sollten wahrscheinlich versuchen, eine Liste mit Konstrukten wie verwenden yield, foreach, matchund so weiter.

Bei Leistungsmerkmalen ist ein Array mit wahlfreiem Zugriff auf Elemente schneller, während eine Liste schneller ist, wenn neue Elemente vorangestellt (hinzugefügt) werden. Über sie zu iterieren ist vergleichbar.