Wann sollte ich in Clojure einen Vektor über einer Liste verwenden und umgekehrt?

147

Ich habe gelesen, dass Vektoren keine Seqs sind, sondern Listen. Ich bin mir nicht sicher, was der Grund dafür ist, einen über den anderen zu verwenden. Es scheint, dass Vektoren am häufigsten verwendet werden, aber gibt es einen Grund dafür?

Rayne
quelle
1
Verwandte stackoverflow.com/questions/6928327/…
Duncan McGregor

Antworten:

112

Wieder einmal scheint es, als hätte ich meine eigene Frage beantwortet, indem ich ungeduldig wurde und sie in #clojure auf Freenode gestellt habe. Auf Stackoverflow.com wird empfohlen, Ihre eigenen Fragen zu beantworten: D.

Ich hatte eine kurze Diskussion mit Rich Hickey, und hier ist der Kern davon.

[12:21] <Raynes>    Vectors aren't seqs, right?
[12:21] <rhickey>   Raynes: no, but they are sequential
[12:21] <rhickey>   ,(sequential? [1 2 3])
[12:21] <clojurebot>    true
[12:22] <Raynes>    When would you want to use a list over a vector?
[12:22] <rhickey>   when generating code, when generating back-to-front
[12:23] <rhickey>   not too often in Clojure
Rayne
quelle
Während Sie auf Freenode sind, kommen Sie auf die dunkle Seite und treten Sie #stackoverflow bei! :-P
Chris Jester-Young
Ich war dort eigentlich im Leerlauf. Ich habe die IRC-Clients gewechselt und nie daran gedacht, #stackoverflow zu meiner Autojoin-Liste hinzuzufügen.
Rayne
Ich bin ein Lisp-Neuling, aber ich habe mich gefragt, ob Vektoren, Karten und Mengen die Idee, dass der gesamte Code mit Daten austauschbar ist, in irgendeiner Weise zerstören. Oder ist dies nur eines dieser Dinge, die Clojure zu einem praktischen Lisp machen? (ODER können Sie einen Vektor auswerten?)
Rob Grant
23
Dies ist ein völlig wenig hilfreiches Chat-Snippet. "Code generieren" "Back-to-Front generieren" -> bedeutet genau ?? Ich habe wirklich Schwierigkeiten mit dieser Frage, weil in meinem Buch Faulheit + deklarativer Stil = weitaus bessere Leistung und dennoch überall in Clojure Vektoren vorgeschlagen werden, was mich völlig verwirrt.
Jimmy Hoffa
22
@JimmyHoffa So wie ich es verstehe: "Code generieren" = "Innerhalb eines Makros" (da der größte Teil des Codes Funktionsaufrufe sind, also Listen); "Von hinten nach vorne erzeugen" = "Erstellen einer Sequenz durch Voranstellen".
Omiel
87

Wenn Sie viel mit Java programmiert haben und mit dem Java-Sammlungsframework vertraut sind, denken Sie an Listen wie LinkedListund Vektoren wieArrayList . Sie können also Container auf die gleiche Weise auswählen.

Zur weiteren Verdeutlichung: Wenn Sie Elemente einzeln einzeln an der Vorder- oder Rückseite der Sequenz hinzufügen möchten, ist eine verknüpfte Liste viel besser als ein Vektor, da die Elemente nicht jedes Mal gemischt werden müssen. Wenn Sie jedoch häufig auf bestimmte Elemente zugreifen möchten (nicht in der Nähe der Vorder- oder Rückseite der Liste) (z. B. Direktzugriff), sollten Sie den Vektor verwenden.

Vektoren können übrigens leicht in Seqs umgewandelt werden.

user=> (def v (vector 1 2 3))
#'user/v
user=> v
[1 2 3]
user=> (seq v)
(1 2 3)
user=> (rseq v)
(3 2 1)
Chris Jester-Young
quelle
Vektoren sind keine Seqs, aber sie sind sequentiell. (Quelle: Rich selbst auf #clojure auf freenode.) Außerdem kenne ich Java überhaupt nicht wirklich, aber Rich hat nur meine Frage beantwortet.
Rayne
1
Ich werde meinen Beitrag bearbeiten, um zu sagen, dass Vektoren über die Funktion seq zu seqs gemacht werden können. :-)
Chris Jester-Young
2
Wählen Sie Ihre Antwort, weil sie tatsächlich die Frage beantwortet hat, und ich mag es wirklich nicht, meine eigenen Antworten als richtig zu wählen. Scheint nicht richtig. Vielen Dank. :)
Rayne
Eine Deque ist besser als eine verknüpfte Liste, wenn Sie zuerst und zuletzt hinzufügen. LLs sind ziemlich schrecklich: P
Boxed
1
@boxed Sie können keine Deque über einem Vektor ArrayListimplementieren oder ohne sich selbst effektiv neu zu implementieren ArrayDeque.
Chris Jester-Young
43

Vektoren haben O (1) zufällige Zugriffszeiten, müssen jedoch vorab zugeordnet werden. Listen können dynamisch erweitert werden, aber der Zugriff auf ein zufälliges Element ist O (n).

Svante
quelle
3
Technisch gesehen haben verknüpfte Listen O (1) Zugriffszeiten ... wenn Sie nur auf das vordere oder hintere Element zugreifen. :-P Vektoren haben jedoch O (1) Direktzugriff. :-)
Chris Jester-Young
4
("Verknüpfte Liste", wie oben beschrieben, bezieht sich auf doppelt verknüpfte Listen. Einfach verknüpfte Listen haben nur O (1) Zugriff auf das vordere Element .:-P)
Chris Jester-Young
1
Als jemand, der gerade in Clojure eintaucht, ist dies eine viel bessere Antwort als die beiden anderen mit mehr Stimmen. Die anderen beiden sagen mir nichts von Nutzen.
Keithjgrant
@ ChrisJester-Young Einzel-verketteten Liste kann O (1) Zugang zur Rückseite unterstützen , wenn es einen Verweis auf das Rückenelement speichert, so .
Gill Bates
30

Wann wird ein Vektor verwendet?

  • Leistung des indizierten Zugriffs - Sie erhalten ~ O (1) Kosten für den indizierten Zugriff im Vergleich zu O (n) für Listen
  • Anhängen - mit konj ist ~ O (1)
  • Praktische Notation - Ich finde es sowohl einfacher, [1 2 3] zu tippen und zu lesen als '(1 2 3) für eine Literalliste, wenn beides funktionieren würde.

Wann man eine Liste verwendet:

  • Wenn Sie als Sequenz darauf zugreifen möchten (da Listen seq direkt unterstützen, ohne neue Objekte zuweisen zu müssen)
  • Voranstellen - Hinzufügen zum Anfang einer Liste mit Nachteilen oder vorzugsweise Konj ist O (1)
mikera
quelle
3
Selbst beim Hinzufügen / Entfernen an beiden Enden ist eine Liste eine ziemlich schreckliche Wahl. Ein Deque ist viel besser (in der CPU und insbesondere im Speicher). Versuchen Sie es mit github.com/pjstadig/deque-clojure
Boxed
2
Betreff: Die ~O(1), für diejenigen, für die diese Kostenerklärung hilfreich sein könnte - stackoverflow.com/questions/200384/constant-amortized-time
Merlyn Morgan-Graham
13

nur eine kurze Randnotiz:

"Ich habe gelesen, dass Vektoren keine Seqs sind, sondern Listen." 

Sequenzen sind allgemeiner als Listen oder Vektoren (oder Karten oder Mengen).
Es ist bedauerlich, dass die REPL Listen und Sequenzen gleich druckt, weil es wirklich so aussieht, als wären Listen Sequenzen, obwohl sie unterschiedlich sind. Die (seq) -Funktion erstellt eine Sequenz aus vielen verschiedenen Dingen, einschließlich Listen, und Sie können diese Sequenz dann jeder der zahlreichen Funktionen zuführen, die mit seqs raffinierte Dinge tun.

user> (class (list 1 2 3))
clojure.lang.PersistentList

user> (class (seq (list 1 2 3)))
clojure.lang.PersistentList

user> (class (seq [1 2 3]))
clojure.lang.PersistentVector$ChunkedSeq

Sec hat eine Verknüpfung, die ihr Argument zurückgibt, wenn es bereits eine Sequenz ist:

user> (let [alist (list 1 2 3)] (identical? alist (seq alist)))
true
user> (identical? (list 1 2 3) (seq (list 1 2 3)))
false

static public ISeq seq(Object coll){
        if(coll instanceof ASeq)
                return (ASeq) coll;
        else if(coll instanceof LazySeq)
                return ((LazySeq) coll).seq();
        else
                return seqFrom(coll);
}

Listen sind Sequenzen, obwohl es auch andere Dinge sind, und nicht alle Sequenzen sind Listen.

Arthur Ulfeldt
quelle
Ich möchte nicht auf einen kleinen Punkt eingehen, es ist nur eine Gelegenheit, auf etwas Nützliches hinzuweisen. viele werden das schon wissen :)
Arthur Ulfeldt
2
Meinst du nicht classstatt class??
Qerub
Ich bin clojure.lang.PersistentListmir nicht sicher, ob sich Ihr Beispiel nach Clojure-Updates geändert hat (ich glaube, ich bin auf 1.5), aber beide Beispiele kehren für mich zurück. Ich gehe davon aus, dass du classnicht schreiben wolltest class?.
Adrian Mouat
Ich habe es tatsächlich getan! Ich werde das beheben
Arthur Ulfeldt
Immer noch ein bisschen verwirrt; Da classfür beide von Ihnen erwähnten Ausdrücke dieselbe PersistentList zurückgegeben wird, bedeutet dies, dass Sequenzen und Listen tatsächlich genau dasselbe sind.
Johnbakers