I posted a question on SO about it. Interesting discussion:
http://stackoverflow.com/questions/2102606/algorithm-to-implement-non-binary-trees-using-1-dimensional-vector
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
