2010-12-16 8 views
6

Ich habe in Practical Clojure (Kapitel 5) gelesen, dass die rseq Funktionsoperation in konstanter Zeit ausgeführt wird. Es scheint mir, dass es eine lineare Zeitoperation sein sollte. Kann mir das jemand etwas näher bringen?Clojure rseq in konstanter Zeit?

Antwort

12

Versuchen Sie folgendes:

(class [1 2 3 4])

Sie werden sehen:

clojure.lang.PersistentVector

Nun ist diese versuchen:

(class (rseq [1 2 3 4]))

und die Sequenz imp lementation unterscheidet:

clojure.lang.APersistentVector$RSeq

Roman Wie gesagt, es ist eine geänderte Schnittstelle zu einer Sequenz ist. Alle Elemente sind dort, wo sie waren, Sie greifen nur in umgekehrter Reihenfolge auf sie zu.

können Sie RSeq-Klasse zu sehen, wie es hier umgesetzt hat: https://github.com/clojure/clojure/blob/b578c69d7480f621841ebcafdfa98e33fcb765f6/src/jvm/clojure/lang/APersistentVector.java

+0

Vielen Dank! Das macht Sinn. –

3

Ich weiß nicht, wie es implementiert ist, aber ich würde denken, dass es nur ein Objekt zurückgibt, das Sequenzschnittstelle implementiert und weiß, wie man die Struktur (Vektor oder sortierte Karte) in umgekehrter Reihenfolge durchläuft. Die Ergebnissequenz ist faul, sodass sie nicht sofort die gesamte Struktur durchlaufen muss.

0

Es gibt die neue Schnittstelle in konstanter Zeit wie Goran Jovic sagte aber aus linear Druck. Die Darstellung in der REPL ist also linear, aber es ist konstant.

Verwandte Themen