The question is though, why doesn't this work to begin with and why does it work on 1.3.0-master-SNAPSHOT...? Is it broken or am I doing something wrong? :) Andreas
On 27/05/2011, at 1:28 PM, Ken Wesson wrote: > On Thu, May 26, 2011 at 10:28 PM, Armando Blancas > <armando_blan...@yahoo.com> wrote: >> Coercing m to int somehow prevents h from being boxed: >> >> user=> (defn bin-search [v k c] >> (loop [l 0 >> h (dec (count v))] >> (if (> l h) false >> (let [m (int (quot (+ l h) 2)) >> m-v (v m)] >> (cond (> m-v k) (recur (inc m) h) >> (> k m-v) (recur l (dec m)) >> :else m))))) >> #'user/bin-search >> user=> > > I doubt it. Rather, m is now an int so (dec m) can be a valid recur for h. > > The real question is why h was primitive to begin with, since there's > no coercion of h to int in either version of the code. > > To make this really fast you will want to use int throughout, though, > and unchecked arithmetic: > > (defn bin-search-fast [v k] > (loop [l (int 0) > h (int (dec (count v)))] > (if (> l h) false > (let [m (unchecked-divide (unchecked-add l h) 2) > m-v (v m)] > (cond > (< m-v k) (recur (unchecked-inc m) h) > (< k m-v) (recur l (unchecked-dec m)) > :else m))))) > > This works on ascending values: > > => (bin-search-fast (vec (map #(* % %) (range 1000))) 4096) > 64 > > And despite the proliferation of fast, wrapping unchecked-foo > operations, it is perfectly safe. > > The thing that would overflow and wrap first is the sum of l and h. > The worst case occurs when the target's right at the end of the > vector, and l ends up nearly equal to h, which stays one less than the > length of the vector. Then we're adding length - 1 and length - 2 for > 2*length - 3. This has to stay below 2147483647, so the maximum vector > length this can support is 2147483650/2 or 1073741825. > > Over a billion items; that takes up 4GB just for the object pointers > in the vector. You cannot hit this limit on 32-bit hardware -- OOME > would be thrown first -- and on 64-bit there'd be no penalty from > changing the code to use long instead of int, which makes the maximum > vector size enormously larger than you're likely to use in the > foreseeable future even on 64-bit hardware. > > The speed difference is about a factor of two: > > => (defn bin-search-slow [v k] > (loop [l 0 > h (Integer/valueOf (dec (count v)))] > (if (> l h) false > (let [m (quot (+ l h) 2) > m-v (v m)] > (cond > (< m-v k) (recur (inc m) h) > (< k m-v) (recur l (dec m)) > :else m))))) > #'user/bin-search-slow > => (def squares (vec (map #(* % %) (range 1000)))) > #'user/squares > => (time (dotimes [_ 1000] (bin-search-slow squares 4096))) > "Elapsed time: 1.37656 msecs" > => (time (dotimes [_ 1000] (bin-search-fast squares 4096))) > "Elapsed time: 0.7608 msecs" > > (Each timing is after several repetitions of the (time ...) line > preceding it, once the numbers have settled down as the JIT has done > its thing, on the hotspot server VM.) > > -- > Protege: What is this seething mass of parentheses?! > Master: Your father's Lisp REPL. This is the language of a true > hacker. Not as clumsy or random as C++; a language for a more > civilized age. > > -- > 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 -- "Test-driven Dentistry (TDD!) - Not everything should be test driven" - Michael Fogus -- ********************************************************** Andreas Koestler, Software Engineer Leica Geosystems Pty Ltd 270 Gladstone Road, Dutton Park QLD 4102 Main: +61 7 3891 9772 Direct: +61 7 3117 8808 Fax: +61 7 3891 9336 Email: andreas.koest...@leica-geosystems.com ************www.leica-geosystems.com************* when it has to be right, Leica Geosystems Please consider the environment before printing this email. -- 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
