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
--