arrays - Heap's algorithm in Clojure (can it be implemented efficiently?) -

-

heap's algorithm enumerates permutations of array. wikipedia's article on algorithm says robert sedgewick concluded algorithm ``at time effective algorithm generating permutations computer,'' naturally fun try implement.

the algorithm making succession of swaps within mutable array, looking @ implementing in clojure, sequences immutable. put following together, avoiding mutability completely:

(defn swap [a j]   (assoc j (a i) (a j)))  (defn generate-permutations [v n]   (if (zero? n)     ();(println (apply str a));comment out time code, not print     (loop [i 0 v]       (if (<= n)         (do           (generate-permutations (dec n))           (recur (inc i) (swap (if (even? n) 0) n)))))))  (if (not= (count *command-line-args*) 1)   (do (println "exactly 1 argument required") (system/exit 1))   (let [word (-> *command-line-args* first vec)]     (time (generate-permutations word (dec (count word))))))

for 11-character input string, algorithm runs (on computer) in 7.3 seconds (averaged on 10 runs).

the equivalent java program, using character arrays, runs in 0.24 seconds.

so make clojure code faster. used java array type hinting. tried:

(defn generate-permutations [^chars n]   (if (zero? n)     ();(println (apply str a))     (doseq [i (range 0 (inc n))]       (generate-permutations (dec n))       (let [j (if (even? n) 0) oldn (aget n) oldj (aget j)]         (aset-char n oldj) (aset-char j oldn)))))  (if (not= (count *command-line-args*) 1)   (do     (println "exactly 1 argument required")     (system/exit 1))   (let [word (-> *command-line-args* first vec char-array)]     (time (generate-permutations word (dec (count word))))))

well, it's slower. averages 9.1 seconds 11-character array (even type hint).

i understand mutable arrays not clojure way, there way approach performance of java algorithm?

it's not clojure entirely avoiding mutable state. it's clojure has strong opinions on when should used.

in case, i'd highly recommend finding way rewrite algorithm using transients, they're designed save time avoiding reallocation of memory , allowing collection mutable locally long reference collection never leaves function in created. managed cut heavily memory intensive operation's time 10x using them.

this article explains transients well!

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

also, may want rewriting loop structure in way allows use recur recursively call generatepermutations rather using whole name. you'll performance boost, , it'd tax stack lot less.

i hope helps.


Comments

Post a Comment

Popular posts from this blog

javascript - Slick Slider width recalculation -

-
i'm trying add slide in panel on slick container css. carousel works except new width not being calculated when space has been added. recalibrate once advance next slide i'd happen each time panel opened or closed. i've tried adding both margin , padding, neither makes difference. ideas? https://jsfiddle.net/mhigley/dpf7mlpl/ html: <button type="button" id="button"><i class="fa fa-arrow-right"></i></button> <aside> <h2>slide in panel</h2> <ol> <li>list item</li> <li>list item</li> <li>list item</li> <li>list item</li> <li>list item</li> </ol> </aside> <main role="main"> <div class="sections"> <section> <article> <h2>first slide</h2> <p>lorem ipsum d...
Read more

jsf - PrimeFaces Datatable - What is f:facet actually doing? -

-
looking through primefaces code in app noticed following line: <f:facet name="header">#{trainsearch.traincount} trains</f:facet> it looks overriding header, makes sense, can explain me in little more detail? what happening line of code? complete code listed below: <p:datatable id = "results" value = "#{trainsearch.trains}" var = "train" rendered="#{not empty trainsearch.trains}" styleclass = "train-search-table horizontal-border"> <f:facet name="header">#{trainsearch.traincount} trains</f:facet> <p:column headertext = "train id"> <p:panelgrid columns="1" styleclass = "train-id-grid" layout = "grid"> <h:outputtext styleclass = "train-id-label" value="#{train.traini}"/> <h:outputtex...
Read more

angular2 services - Angular 2 RC 4 Http post not firing -

-
i trying fire post request app , it's not working, tried multiple ways. don't see request being fired under network tab in chrome. not sure problem is, appreciated. import { injectable } '@angular/core'; import { http, headers } '@angular/http'; @injectable() export class userservice{ private _url="users"; constructor(private _http: http){ } checkifusernameexists(username){ return this._http.get(this._url+"/"+username) .map(response => response.json()) } createuser(user){ let headers = new headers(); headers.append('content-type', 'application/json') console.log(json.stringify(user)); return this._http.post(this._url, json.stringify(user),{headers: headers}) .map(response => response.json()) } } first need capture error , solve error: this._http.post(this._url, json.stringify(user),{headers: headers}) .subscribe( ...
Read more