Tassilo Horn <tass...@member.fsf.org> writes: Now I'm really a bit confused. I've just added atom counters and increased them in the comparison functions in order to check if the lazy variants really test less than the standard sort.
> A better solution [that doesn't overrun the stack] seems to be to use > a sequence comprehension [instead of filter/remove]: > > (defn sort-parts > "Lazy, tail-recursive, incremental quicksort. Works against > and creates partitions based on the pivot, defined as 'work'." > [work] > (lazy-seq > (loop [[part & parts] work] > (if-let [[pivot & xs] (seq part)] > (let [smaller? #(< % pivot)] > (recur (list* > (for [x xs :when (smaller? x)] x) > pivot > (for [x xs :when ((complement smaller?) x)] x) > parts))) > (when-let [[x & parts] parts] > (cons x (sort-parts parts))))))) > > (defn qsort [xs] > (sort-parts (list xs))) (take 2 (qsort [1 9 2 8 3 7 4 6 5])) executes #(< % pivot) 42 times. [I replaced the compare fn with #(do (swap! q1 inc) (< % pivot)) to get to this result where q1 was (atom 0) initially.] > (defn qsort2 [xs] > (lazy-seq > (when (seq xs) > (let [[p & r] xs] > (concat (qsort (for [y r :when (< y p)] y)) > [p] > (qsort (for [y r :when (>= y p)] y))))))) (take 2 (qsort2 [1 9 2 8 3 7 4 6 5])) executes the 2 :when predicates only 16 times in total. [Same counting approach as above.] The standard sort function given #(do (swap! q3 inc) (compare %1 %2)) as its comparison function compares 21 times. So my simple qsort2 seems to have saved 5 comparisons. But the adapted JoC-version takes twice as many comparisons as the standart sort of the whole seq! Why is that? Then I tried sorting the complete seq using my qsort2 instead of only taking the two first items. That also takes 16 comparisons, but well, that's clear because of the min-max structure of the vector. Taking only the first item takes only 8 comparisons as it should. So it seems, qsort is flawed, and the difference in comparisons between qsort2 and sort when sorting the complete seq is that the latter uses merge-sort, not quick-sort, right? But what I don't understand is why qsort, although it compares nearly thrice as often than qsort2, is still about as fast as qsort2. I'd really appreciate if someone could share some light. Bye, Tassilo -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
