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
