Clojure: Sequenz zurück zum Vektor

Question

Wie kann ich eine Sequenz zurück in den Vektor nach einem Sequenzerstellungsvorgang (wie sortieren)? Ist die Verwendung (vec ..) einer Sequenz, die ein Vektor war, kostspielig?

One (schlecht?) Möglichkeit, einen neuen Vektor in der richtigen Reihenfolge schafft:

(vec (sort [1 2 3 4 5 6])) 

ich frage, weil ich zufällig Zugang benötigen (n ..) zu großen sortierten Vektoren - die nach jetzt riesige Sequenzen sind die Sorte, mit schrecklichen O (n) zufällige Zugriffszeit

Answer 1

Aus meinen eigenen Tests (nichts Wissenschaftliches) können Sie besser mit Arrays arbeiten, wenn Sie viel sortieren. Wenn Sie jedoch selten sortieren und viel zufälligen Zugriff haben, ist die Verwendung eines Vektors möglicherweise die bessere Wahl, da die Zeit für den wahlfreien Zugriff im Durchschnitt um mehr als 40% höher ist. Die Sortierleistung ist jedoch schrecklich, da der Vektor konvertiert wird ein Array und dann zurück zu einem Vektor. Hier ist meine Erkenntnisse:

(def foo (int-array (range 1000))) 

(time 
    (dotimes [_ 10000] 
    (java.util.Arrays/sort foo))) 

; Elapsed time: 652.185436 msecs 

(time 
    (dotimes [_ 10000] 
    (nth foo (rand-int 1000)))) 

; Elapsed time: 7.900073 msecs 

(def bar (vec (range 1000))) 

(time 
    (dotimes [_ 10000] 
    (vec (sort bar)))) 

; Elapsed time: 2810.877103 msecs 

(time 
    (dotimes [_ 10000] 
    (nth bar (rand-int 1000)))) 

; Elapsed time: 5.500802 msecs 

P. S .: Beachten Sie, dass die Vektor-Version nicht wirklich speichert die sortierten Vektor überall, aber das sollte nicht das Ergebnis erheblich ändern, wie Sie einfache Bindungen in einer Schleife für Geschwindigkeit verwenden würden.

Answer 2

Wenn Sie nach dem Zufallsprinzip Zugriff auf das Ergebnis der Sortierung mit riesigen Vektoren benötigen, dann sollte die Zeit durch den Aufruf an Vec durch Zeiteinsparungen weit davon aufgewogen werden, dies zu tun .

Wenn Sie profilieren und feststellen, dass es zu langsam ist, müssen Sie wahrscheinlich Java-Arrays verwenden.

Answer 3

Meikel Brandmeyer hat gerade eine Lösung für die Clojure-Gruppe gepostet.

(defn sorted-vec 
    [coll] 
    (let [arr (into-array coll)] 
    (java.util.Arrays/sort arr) 
    (vec arr))) 

Clojure des sort kehrt a seq über ein sortiertes Array; Dieser Ansatz macht das gleiche, gibt aber einen Vektor zurück, nicht einen Seq.

Wenn Sie möchten, können Sie sogar die Umwandlung zurück in eine Clojure persistente Datenstruktur überspringen:

(defn sorted-arr 
    "Returns a *mutable* array!" 
    [coll] 
    (doto (into-array coll)] 
    (java.util.Arrays/sort)) 

aber die resultierende Java-Array (die Sie als Clojure Sammlung in den meisten Fällen behandeln kann) wandelbar sein . Das ist in Ordnung, wenn Sie es nicht an anderen Code weitergeben, aber seien Sie vorsichtig.

Answer 4

Als neuer Clojure-Entwickler ist es leicht, Sammlungen und Sequenzen zu verwechseln.

Diese sortierten Vektorfunktion:

(sortiert [1 2 3 4 5 6]) => (1 2 3 4 5 6);

gibt eine Sequenz

Aber ich brauche einen Vektor für die nächste Operation, weil das nicht funktioniert ...

(take-while (teilweise> 3) (1 2 3 4 5 6))

=> ClassCastException java.lang.Long kann nicht in clojure.lang umgewandelt werden.IFn Benutzer/eval2251 (NO_SOURCE_FILE: 2136)

Lassen Sie uns versuchen, die Sequenz in einen Vektor zu konvertieren:

(VEC (1 2 3 4 5 6))

=> Classcast java.lang. Long kann nicht in clojure.lang.IFn umgewandelt werden clijure.lang.IFn user/eval2253 (NO_SOURCE_FILE: 2139)

Nein! Aber wenn Sie alles zusammenfügen, funktioniert es gut.

(take-while (teilweise> 3) (sortiert [1 2 3 4 5 6]))

=> (1 2)

Die Lektion: Sie können nicht direkt mit Sequenzen arbeiten! Sie sind ein Zwischenschritt in diesem Prozess. Wenn die REPL versucht (1 2 3 4 5 6) zu bewerten, sieht es aa Funktion und löst eine Ausnahme:

(1 2 3 4 5 6) => Classcast java.lang.Long nicht gegossen werden clojure.lang.IFn user/eval2263 (NO_SOURCE_FILE: 2146)