update-in! (?)

[Gabi]

I really needed an update-in! version that works on transients. I
couldn't find one so I just modified the original update-in core (just
replaced "assoc" "assoc!"):

(defn update-in!
"modified version of core/update-in that works on, and return
transients"
([m [k & ks] f & args]
(if ks
(assoc! m k (apply update-in! (get m k) ks f args))
(assoc! m k (apply f (get m k) args)))))

user=> (persistent!(update-in!(transient v) [0] reverse))
[(2 1) [3 4]]

BUT when using nested paths, it fails:

user=>(persistent!(update-in!(transient v) [0 0] inc))
java.lang.ClassCastException: clojure.lang.PersistentVector cannot be
cast to clojure.lang.ITransientAssociative

Any idea how to solve this?

[Gabi]

Forgot to mention that v in the example is defined to [[1 2] [3 4]]

[Chouser]

On Sun, Jan 17, 2010 at 8:25 AM, Gabi <bugs...@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.

--Chouser
http://joyofclojure.com/

[Gabi]

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:

[Gabi]

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 ?

[Christophe Grand]

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

> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@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+u...@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)

[Gabi]

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

[Sean Devlin]

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/figs/methods/sparseMatrix.gif

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

[Gabi]

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

[Sean Devlin]

How about a sorted set w/ a custom comparator? Of course, this rules
out transients, but maybe the flatness will make up for it?

[Gabi]

Can you elaborate more ? How can trees be represented in sorted sets?

[Christophe Grand]

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}

--

[Gabi]

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

[brianh]

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

[Gabi]

I don't think zipper would help in this case