Any chance you could rethink your approach & use a zipper?
On Jan 20, 9:32 am, Gabi <bugspy...@gmail.com> wrote: > I posted a question on SO about it. Interesting > discussion:http://stackoverflow.com/questions/2102606/algorithm-to-implement-non... > > On Jan 20, 5:39 pm, Christophe Grand <christo...@cgrand.net> wrote: > > > > > I concur: a map (or a sorted map if you need to emulate access to a > > subtree) can be an option. > > > [[1 2] [3 4]] is represented by {[0 0] 1, [0 1] 2, [1 0] 3, [1 1] 4} > > > On Wed, Jan 20, 2010 at 4:24 PM, Sean Devlin <francoisdev...@gmail.com> > > wrote: > > > How about a sorted set w/ a custom comparator? Of course, this rules > > > out transients, but maybe the flatness will make up for it? > > > > On Jan 20, 10:15 am, Gabi <bugspy...@gmail.com> wrote: > > >> I need to add/delete much more frequently than just updating > > >> actually. > > > >> On Jan 20, 4:59 pm, Sean Devlin <francoisdev...@gmail.com> wrote: > > > >> > Gabi, > > >> > A similar technique is used with sparse matrices. You usually have > > >> > severals arrays, one for the non-zero elements, and another one for > > >> > indexing the column and a third for indexing the rows. > > > >> >http://pasadena.wr.usgs.gov/office/baagaard/research/papers/thesis/fi... > > > >> > This should be fast as long as you're only updating. If you're > > >> > inserting/deleting, you might be able to get away with using a > > >> > collection of 1D trees. > > > >> > Sean > > > >> > On Jan 20, 9:18 am, Gabi <bugspy...@gmail.com> wrote: > > > >> > > These vectors represent trees which need to updated very frequently. > > >> > > So If there was an efficient way to use transients to represent > > >> > > transient trees the whole process would be much more efficient (so > > >> > > each update to a tree would be done in place instead of creating new > > >> > > one.) As discussed above, naive usage of transients won't help. > > >> > > Another approach would be implement in Java, but I wish there would > > >> > > some way to achieve this directly from Clojure. > > >> > > Now that I think about it, maybe the solution is to represent the > > >> > > tree > > >> > > as one dimensional vector instead of nested one (any good clojure > > >> > > algorithm for this ? Representing and traversing non binary trees as > > >> > > one dimensional vector?) > > > >> > > Jan 20, 12:53 pm, Christophe Grand <christo...@cgrand.net> wrote: > > > >> > > > Hi Gabi! > > > >> > > > Can you tell us more about your problem, what do those deeply > > >> > > > nested > > >> > > > vectors represent and how are you going to update them? (are all > > >> > > > updates batched in one part of your program?) > > > >> > > > With transients current implementation you can't write an > > >> > > > efficient update-in! > > > >> > > > Christophe > > > >> > > > On Wed, Jan 20, 2010 at 9:15 AM, Gabi <bugspy...@gmail.com> wrote: > > >> > > > > Guys, I really need your expertise here. > > >> > > > > I have lots of deeply nested vectors, which i need to manipulate > > >> > > > > frequently (thousands of times) > > >> > > > > What is the most effective way to do this ? > > > >> > > > > On Jan 17, 4:27 pm, Gabi <bugspy...@gmail.com> wrote: > > >> > > > >> Right. I thought that transient performing deep > > >> > > > >> 'transientivity'. > > >> > > > >> Here is a fixed version. It takes a regular coll converts > > >> > > > >> whatever it > > >> > > > >> can to transient and update the stuff. > > >> > > > >> The problem is that doing persistent!(assoc!(transient m)) on > > >> > > > >> each > > >> > > > >> level probably misses the whole point of performance. > > >> > > > >> So while it work, it probably slower than the regular update-in. > > >> > > > >> I need a better solution. > > > >> > > > >> (defn update-in!! > > >> > > > >> "modified version of core/update-in that works on, and return > > >> > > > >> transiants" > > >> > > > >> ([m [k & ks] f & args] > > >> > > > >> (if ks > > >> > > > >> (persistent!(assoc! (transient m) k (apply update-in!! > > >> > > > >> (get m k) > > >> > > > >> ks f args))) > > >> > > > >> (persistent!(assoc! (transient m) k (apply f (get m k) > > >> > > > >> args)))))) > > > >> > > > >> On Jan 17, 3:57 pm, Chouser <chou...@gmail.com> wrote: > > > >> > > > >> > On Sun, Jan 17, 2010 at 8:25 AM, Gabi <bugspy...@gmail.com> > > >> > > > >> > wrote: > > > >> > > > >> > >> user=> (persistent!(update-in!(transient v) [0] reverse)) > > > >> > > > >> > > Forgot to mention that v in the example is defined to [[1 > > >> > > > >> > > 2] [3 4]] > > > >> > > > >> > So you've got a transient vector of persistent vectors of > > >> > > > >> > numbers. The problem is your update-in! then calls assoc! on > > >> > > > >> > each level, but of course assoc! on the inner persistent > > >> > > > >> > vector > > >> > > > >> > fails. > > > >> > > > >> > You either need to make the inner vectors transient (and then > > >> > > > >> > call persist! on them when you're done) or use assoc! only at > > >> > > > >> > the > > >> > > > >> > outer level. > > > >> > > > >> > --Chouserhttp://joyofclojure.com/ > > > >> > > > > -- > > >> > > > > 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 > > > >> > > > -- > > >> > > > Professional:http://cgrand.net/(fr) > > >> > > > On Clojure:http://clj-me.cgrand.net/(en) > > > > -- > > > 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 > > > -- > > Professional:http://cgrand.net/(fr) > > On Clojure:http://clj-me.cgrand.net/(en)
-- 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
