On 7/20/07, Jon Harrop <jon@ffconsultancy.com> wrote:
On Friday 20 July 2007 08:35:39 Loup Vaillant wrote:
> > ;-). I am open to new ideas. In part, I wanted a simple data structure
> > (easier to extend, among other things). Also, I use Set, Map, etc, quite
> > often, and those are also balanced trees: I thought that if I can live
> > with those, I can probably live with Vec as well.
This is the beginnings of an awesome data structure!
> So can I. Your current implementation is already very attractive, and
> looks very usable. For the new idea, have you thought of making (or
> specifying) syntactic sugar to use your array?
Should be very easy using the new camlp4. You might like to add a slicing
notation as well. :-)
> About improving performance...
I have two suggestions:
1. Add an extra node representing single elements that replaces Node(Empty, _,
Empty). The reduces GC stress enormously and makes the whole thing ~30%
faster.
2. Allow unbalanced sub trees. Balancing is slow and folds and maps don't need
to rebalance, but "get" should force rebalancing. Extracting subarrays should
return an unbalanced result.
> Is there a way to obtain a efficient filter?
Yes. I discovered a most-excellent way to do this. It requires arbitrary
metadata in every node, a constructor that composes subnodes to create the
metadata for the parent and a filter function that can cull branches from the
search tree.
I used this in my Mathematica implementation to provide asymptotically fast
filtering based upon lazily evaluated sets of symbols in each subnode. This
gave huge performance improvements with no significant performance overhead.
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?e
_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs