On Tue, Mar 11, 2008 at 9:18 AM, Robert K.
[email protected]
wrote:
2008/3/11, Eric M. [email protected]:
Ruby, unfortunately is really lacking on this front.
Did you see my references to libs in RAA? Do they lack something that you
need?
Sorry, I didn’t see your post. I jumped in the thread later. I have
seen
that red-black tree API before.
external iterators (there is in fact an implementation, albeit with
limited functionality) so far. For me the most pressing disadvantage
of #each and family so far was that you cannot iterate several
collections at the same time with this.
Yep. Forgot about that one. That is quite useful for “external”
iterators
too.
For random access you can use
an Array with index. And for Arrays it would be fairly easy to write
a thin wrapper around such an index which will allow all the movements
and operations you are wanting.
For deletions there are also methods that will do the job with O(n).
Alternatively, when using Arrays, you can use #splice! and []=.
For arrays, there is little need for external iterators, since random
access is O(1). The array index itself can act as an external iterator
and
be no less efficient than a full external iterator (which could access
an
array element without needing the array).
Can you leak a bit more information about the scenarios where you need
more / different behavior?
Here are a few applications I can recall:
-
sweep-line algorithms. I’ve done several implementations and used
others. To have an efficient O(n*log(n)) one, these are some of the
things
I use from sorted-tree structures and their iterator:
- multi set/map: allows for duplicate entries (to deal with multiple
coincident edges)
- find: gives an iterator to an item
- lower/upper bound: more specific find when dealing with duplicates
or if
the item doesn’t exist yet
- ++/-- on an iterator: go to neighbor above/below
- erase using iterator: O(1) erase an item you’ve already found
- insert (w/ and w/o iterator hint): with an iterator hint, the insert
is
O(1), w/o it is O(log(n))
-
range/region query. Iterators can be useful for looking to neighbors
or
inserting/deleting in O(1) time. Unfortunately, the STL (multi) set/map
typically isn’t sufficient to to implement some of these structures.
But,
an API similar to what’s in STL (including external iterators) is quite
useful. Google libkdtree++ to see one implementation.
-
MST (minimum spanning tree). Kruskal’s can get away with just a heap,
but
Prim’s algorithm needs a deletions. Iterators may not be needed. This
is
also similar to Dijkstra’s shortest path algorithm. Also, building
steiner
trees can use various sorted tree structures (don’t remember if external
iterators are needed). Geometric MST’s or steiner trees also take
advantage
of additional structures like sweep-lines or region query structures.
From my experience, many/most algorithms you implement on large
geometric or
graph (as in graph theory) data sets can take advantage of sorted
structures
and associated (external) iterators. I’m sure there are many other
applications when you are dealing with large data sets (where simple
O(n**2)
or slower algorithms aren’t good enough).
At one time Gonzalo Garramuño made an C++ STL to ruby i/f using swig. I
also did something similar for python using swig and used it for some
sweep-line/MST/steiner. I only learned/used python because there was an
api
into the db I was using (in addition to C++).
Note that I still would prefer using ruby compared to C++, but the
libraries
in C++ are more in line with what I do unfortunately (and I need C++ for
performance). But, ruby has clearly improved my C++. I use templates
regularly to get my duck-typing (arbitrary typing). I use both external
iterators and internal iterators (visitors) where appropriate in C++.
And,
I think my general OO skills in C++ have improved because of ruby. The
syntax is very ugly and I have to deal with too many details, but the
majority of the concepts in C++ are there in some form.