Ausführungszeit des Clojure-Programms

Question

Dies ist ein Clojure-Programm zum Lesen von ganzen Zahlen aus einer Datei und Zählen der Anzahl von Inversionen, d. H. Wie oft eine größere Zahl vor einer kleineren Zahl in einer Sequenz auftritt. Es implementiert einen O (n^2) -Algorithmus und dauert ungefähr 30 Minuten, um auf einer Eingabe der Größe 100.000 zu laufen.

(defn count-inversions 
    [file] 
    (let [int-list (vec (map #(Integer/parseInt %) 
          (clojure.string/split (slurp file) #"\r\n")))] 
    (loop [c 0 
      t-list int-list] 
     (let [size (count t-list)] 
     (if (empty? t-list) 
     c 
     (recur (reduce #(if (< %2 (first t-list)) (inc %1) %1) c (subvec t-list 1 (dec size))) 
       (subvec t-list 1 (dec size)))))))) 

Dieser Algorithmus benötigt bei Implementierung in Java nur wenige Sekunden. Warum so ein großer Unterschied?

Answer 1

Dinge, die mir möglicherweise langsam aussehen (obwohl Sie Benchmarks sicher zu sein, werde ....)

• Alle sind Ihre Zahlen eingerahmt. Dies macht alles, was Sie tun, viel langsamer als die Verwendung von Primitiven. Es ist nicht sehr idiomatisch, aber Sie können primitive Arrays in Clojure verwenden, wenn Sie diese Beschleunigung erhalten möchten.
• Beim Reduzieren eines Subvecs werden derzeit viele temporäre Objekte erstellt. Es gibt einen Patch in der Arbeit, um dies zu beheben (http://dev.clojure.org/jira/browse/CLJ-894), aber Sie müssen möglicherweise auf Clojure 1.4 oder 1.5 warten.
• Es hilft (set! *unchecked-math* true) zu tun Leistung von Integer-Operationen zu verbessern (natürlich, müssen Sie ein wenig vorsichtiger sein, wenn Überlauf passieren könnte)

Wenn ich dies zu laufen sehr schnell in Clojure ich haben wollte‘ d wahrscheinlich zu primitiven Arrays greifen und Looping mit primitiven Indizes:

(set! *unchecked-math* true) 

(defn count-inversions [coll] 
    (let [^ints integers (int-array coll) 
      size (long (count integers))] 
     (loop [c (long 0) 
       i (long 0)] 
     (if (>= i size) 
      c 
      (recur 
      (loop [c (long c) 
        v (aget integers i) 
        j (inc i)] 
       (if (>= j size) 
       c 
       (recur (long (if (> v (aget integers j)) (inc c) c)) v (inc j)))) 
      (inc i)))))) 

(time (count-inversions (for [i (range 100000)] (rand-int 100)))) 
"Elapsed time: 16036.651863 msecs" 

dh dieses Code in etwa 16 Sekunden auf meinem Rechner alle Umkehrungen in 100.000 Zahlen zählt (mit Clojure 1.3)