On Wed, Jul 15, 2009 at 3:51 AM, Jan Rychter<j...@rychter.com> wrote: > I am not sure what you mean about subvecs, though -- I currently use > them for dropn and rot operations, and I don't know how to avoid using > them:
The problem with subvec is that it doesn't really create a "new" vector, it just adds a level of indirection off of the original vector. So for example, if you look up, say, index 2 in the subvec, it knows to go look up index 5 in the original vec. If you create a subvec of a subvec of a subvec, etc. pretty soon every lookup results in a chain of forty lookups until it gets to the original vector, and your performance grinds to a halt. > > (defmacro stack-dropn [stack n] > `(let [stack# ~stack] > (subvec stack# 0 (- (stack-count ~stack#) ~n)))) > You really don't want to use subvec here. Just right a function that pops the stack n times using pop. > (defmacro stack-rot [stack] > `(let [stack# ~stack] > (if (> (stack-count stack#) 1) > (apply conj (vector (peek stack#)) (subvec stack# 0 (dec (count > stack#)))) > stack#))) > > (incidentally, if anyone can suggest a better rot implementation, I > would be very grateful -- rot "rotates" the stack, putting the last > element of the vector first) Subvec doesn't hurt you so much here, because you're immediately turning around and using conj to rebuild a whole new vector, so you're not going to run into a problem with nested subvecs. Still, you're probably slightly better off using pop, rather than the subvec. Another variation (probably similar performance, but maybe easier to read?) would be to replace the whole line with (vec (cons (peek stack#) (pop stack#))). It looks like stack-rot is going to be the bottleneck in your app since it requires traversing the whole vector to build the new one, but I think the list-based implementation would be a bit worse, so I think your choice to use vectors here is sound. For stack-dropn and stack-rot to both be fast, I think that you really want to use a deque. Unfortunately, Clojure doesn't have a built-in deque, and I don't see one in contrib, but you could look at clojure.lang.PersistentQueue and read Okasaki's Functional Data Structures to draw some inspiration. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
