Thanks Ken, using this approach brings a ~1000 times speedup :) (def a (sparse-vec (range 100000) (range 100000)))
(def b (time (assc-ken a 111111 0))) "Elapsed time: 0.249 msecs" (def b (time (assc a 111111 0))) "Elapsed time: 252.06 msecs" Very worthwhile and it's clearer as well. Cheers Andreas On 26/05/2011, at 11:11 PM, Ken Wesson wrote: > On Thu, May 26, 2011 at 8:19 AM, Andreas Kostler > <andreas.koestler.le...@gmail.com> wrote: >> (let [new-indices (sort (conj indices i)) >> new-idx (bin-search new-indices i) >> [chunk1 chunk2] (split-at new-idx vals)] >> (SparseVec. new-indices (into (conj (vec chunk1) o) chunk2)))))) >> (ith-val [this i] >> (get vals (bin-search indices i) 0))) >> >> Can you guys think of ways of making this more idiomatic and/or performant? > > Yes. Drop the sort and avoid split-at. Just use binary search to find > the correct value for new-idx (the position of the next index higher > than i, or else the indices vector's length) and then > > (SparseVec. > (into (conj (subvec indices 0 new-idx) i) (subvec indices new-idx)) > (into (conj (subvec vals 0 new-idx) o) (subvec vals new-idx))) > > The binary search you're doing anyway, and subvec is cheap. There's > one more into on vectors, but the sort would have been n log2 n and > the into is n log32 n, indeed k log32 k where k is the length of the > tail. The latter logarithmic factors are much smaller at a given > length of vector. > > Tune this, then test its performance against a naive solution using a > plain-jane hash map. > > -- > 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
