Algorytm sterty w Clojure (czy można go efektywnie wdrożyć?)

Question

Algorytm sterty wylicza permutacje tablicy. Wikipedia's article on the algorithm mówi, że Robert Sedgewick stwierdził, że algorytm był "w tamtym czasie najskuteczniejszym algorytmem generowania permutacji przez komputer", więc naturalnie byłoby fajnie próbować zaimplementować.

Algorytm polega na dokonywaniu kolejnych zamiany w tablicy zmiennych, więc szukałem implementacji tego w Clojure, którego sekwencje są niezmienne. I umieścić następujące razem, unikając zmienność całkowicie:

(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)))))) 

Dla ciągu wejściowego 11-znakowy, biegnie algorytm (na moim komputerze) w 7,3 sekundy (średnia ponad 10 tras).

Równoważny program Java, wykorzystujący tablice znaków, działa w 0,24 sekundy.

Chciałbym więc przyspieszyć kod Clojure. Użyłem tablicy Java z podpowiedziami typu. To, co starałem:

(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)))))) 

Cóż, to wolniejszy. Teraz uśrednia 9,1 sekundy dla 11-znakowej tablicy (nawet z podpowiedziami typu).

Rozumiem, że zmienne tablice nie są sposobem Clojure, ale czy jest jakiś sposób podejścia do wydajności Javy dla tego algorytmu?

Answer 1

Nie chodzi o to, że Clojure całkowicie polega na uniknięciu stanu zmienności. Chodzi o to, że Clojure ma bardzo mocne opinie na temat tego, kiedy należy go używać.

W tym przypadku, bardzo polecam znalezienie sposobu, aby przepisać algorytm za pomocą nieustalone, ponieważ są one specjalnie zaprojektowane, aby zaoszczędzić czas unikając realokacji pamięci i pozwala na zmienny zbiór lokalnie tak długo, jak odniesienie do kolekcji nigdy nie opuszcza funkcji, w której zostało utworzone. Niedawno udało mi się wyciąć intensywnie wykorzystujący pamięć czas operacji o prawie 10x, korzystając z nich.

Ten artykuł wyjaśnia dość dobrze transjenty!

http://hypirion.com/musings/understanding-clojure-transients

Można również zajrzeć do poprawiania struktury pętli w sposób, który pozwala na korzystanie powtarzać rekursywnie wywołać generatePermutations zamiast używać całą nazwę. Prawdopodobnie zwiększysz wydajność i znacznie mniej obciążysz stertę.

Mam nadzieję, że to pomoże.