Heaps Algorithmus zählt die Permutationen eines Arrays auf. Wikipedia's article on the algorithm sagt, dass Robert Sedgewick festgestellt hat, dass der Algorithmus damals "der effektivste Algorithmus zum Generieren von Permutationen durch Computer war", also würde es natürlich Spaß machen zu versuchen, ihn zu implementieren.Heaps Algorithmus in Clojure (kann es effizient implementiert werden?)
Der Algorithmus ist über eine Aufeinanderfolge von Swaps innerhalb eines änderbaren Array machen, so dass ich betrachtete dies in Clojure Implementierung der Sequenzen unveränderlich sind. Ich habe zusammen die folgend, Veränderlichkeit vermeiden vollständig:
(defn swap [a i j]
(assoc a j (a i) i (a j)))
(defn generate-permutations [v n]
(if (zero? n)
();(println (apply str a));Comment out to time just the code, not the print
(loop [i 0 a v]
(if (<= i n)
(do
(generate-permutations a (dec n))
(recur (inc i) (swap a (if (even? n) i 0) n)))))))
(if (not= (count *command-line-args*) 1)
(do (println "Exactly one argument is required") (System/exit 1))
(let [word (-> *command-line-args* first vec)]
(time (generate-permutations word (dec (count word))))))
Für ein 11-Zeichen-Eingabestring, der Algorithmus läuft (auf meinem Computer) in 7,3 Sekunden (gemittelt über 10 Durchläufe).
Das äquivalente Java-Programm, Zeichen-Arrays verwendet wird, läuft in 0,24 Sekunden.
So würde Ich mag den Clojure Code schneller machen. Ich habe ein Java-Array mit Typhinweis verwendet. Das ist, was ich versucht:
(defn generate-permutations [^chars a n]
(if (zero? n)
();(println (apply str a))
(doseq [i (range 0 (inc n))]
(generate-permutations a (dec n))
(let [j (if (even? n) i 0) oldn (aget a n) oldj (aget a j)]
(aset-char a n oldj) (aset-char a j oldn)))))
(if (not= (count *command-line-args*) 1)
(do
(println "Exactly one argument is required")
(System/exit 1))
(let [word (-> *command-line-args* first vec char-array)]
(time (generate-permutations word (dec (count word))))))
Nun, es ist langsamer. Jetzt beträgt es durchschnittlich 9,1 Sekunden für das 11-stellige Array (sogar mit dem Typhinweis).
Ich verstehe änderbare Arrays sind nicht die Clojure Art und Weise, aber ist es eine Möglichkeit, die Leistung von Java für diesen Algorithmus zu nähern?
Haben Sie JVM Warmup/JIT in Ihren Vergleichen überhaupt berücksichtigt? Für mich bedeutet das Ausführen des ersten Codes über ["criterium/bench"] (https://github.com/hugoduncan/criterium/) eine Ausführungszeit von etwa 80-82 μs für eine 11-stellige Zeichenfolge. Die Array-Version rasiert diese auf 59-60 μs. – Magos
Das ist natürlich ein großartiger Ratschlag und danke, obwohl es hier mehr Warmup gibt, als ich erwartet hätte, da der Unterschied zwischen den einfachen Taktzeitmessungen mit Javas System.currentTimeMillis und Clojures Zeitmakro noch viel mehr ist weit mehr als ich erwartet hätte. Toller Tipp über "Kriterium", ich werde es untersuchen. –
Meine Augen brennen, wenn Sie CamelBack verwenden, wenn Sie dies tun sollten. – fernandohur