If class X has a method <=>(aX), I can sort an Array containing
instances of X using Array.sort!.
What I really would like is an array that is always ordered. IOW, I want
the object to be inserted at the correct location inside the array when
the object is added to the array.
Is there an efficient way to do this?
Pete
--
Posted via http://www.ruby-forum.com/.
Yes. You can either use binary search on the Array to insert or you
use a Tree. Both can be found in RAA:
http://raa.ruby-lang.org/project/ruby-bsearch/
http://raa.ruby-lang.org/project/ruby-rbtree/
Kind regards
robert
2008/3/11, Peter Hug <pete@kapiti.co.nz>:
If class X has a method <=>(aX), I can sort an Array containing
instances of X using Array.sort!.What I really would like is an array that is always ordered. IOW, I want
the object to be inserted at the correct location inside the array when
the object is added to the array.Is there an efficient way to do this?
--
use.inject do |as, often| as.you_can - without end
You could use a priority queue. You can see some pure Ruby code for this in an old Ruby Quiz:
http://www.rubyquiz.com/quiz40.html
James Edward Gray II
On Mar 11, 2008, at 3:43 AM, Peter Hug wrote:
What I really would like is an array that is always ordered. IOW, I want
the object to be inserted at the correct location inside the array when
the object is added to the array.Is there an efficient way to do this?
Peter Hug wrote:
If class X has a method <=>(aX), I can sort an Array containing
instances of X using Array.sort!.What I really would like is an array that is always ordered. IOW, I want
the object to be inserted at the correct location inside the array when
the object is added to the array.Is there an efficient way to do this?
Pete
One option is to subclass Array and override the methods you use to
insert the elements. For example, consider the following:
class OrderedArray < Array
def =(index, element)
push(element)
end
def push(element)
super(element)
self.sort!
end
end
You could even add the code to insert the element in the correct place,
but this is a good start.
Another option is to use delegation to wrap the Array, and just
implement the methods you desire:
class OrderedArray < Array
def initialize
@array =
end
def =(index, element)
push(element)
end
def (index)
@array[index]
end
def pop
@array.pop
end
def push(element)
@array.push(element)
@array.sort!
end
end
With kind Regards, Sam and Harm
--
Posted via http://www.ruby-forum.com/\.
Heaps have some limitations that might not work for your application:
* can't delete elements
* can't find an arbitrary element - and iterate over elements in its
vicinity
A tree (red-black, AVL, etc) is quite a bit more flexible if you need more
functionality. In terms of big-O performance (runtime and memory) and
functionality, I don't believe heaps offer advantages.
For my day job, I use mostly use C++ that has heaps and red-black trees at
your fingertips (in STL). Occasionally, I've started with a heap because it
fit the functional requirements (and I know it is more memory efficient -
but, not for big-O). Later, many times I've had to swap it for a tree (i.e.
set or map in STL), because I needed more functionality.
Ruby, unfortunately is really lacking on this front. When doing geometric
stuff, I find every ounce of C++ STL useful. An STL-like ruby lib would be
useful. External iterators are also very important. Ruby's normal internal
iterators (what others might call visitors) don't have the same flexibility
(caller can go forward/backward/read/write/erase/insert at will).
On Tue, Mar 11, 2008 at 7:52 AM, James Gray <james@grayproductions.net> wrote:
On Mar 11, 2008, at 3:43 AM, Peter Hug wrote:
> What I really would like is an array that is always ordered. IOW, I
> want
> the object to be inserted at the correct location inside the array
> when
> the object is added to the array.
>
> Is there an efficient way to do this?You could use a priority queue. You can see some pure Ruby code for
this in an old Ruby Quiz:Ruby Quiz - Drawing Trees (#40)
James Edward Gray II
Binary heap-based priority queues make no (obvious) guarantee about the
order of elements, execept that first element in the array is the
minimum. More complicated heap structures don't even guarantee that
there's an array in there at all.
--Ken
On Tue, 11 Mar 2008 07:52:23 -0500, James Gray wrote:
On Mar 11, 2008, at 3:43 AM, Peter Hug wrote:
What I really would like is an array that is always ordered. IOW, I
want
the object to be inserted at the correct location inside the array when
the object is added to the array.Is there an efficient way to do this?
You could use a priority queue. You can see some pure Ruby code for
this in an old Ruby Quiz:Ruby Quiz - Drawing Trees (#40)
James Edward Gray II
--
Ken (Chanoch) Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/
Robert Klemme wrote:
2008/3/11, Peter Hug <pete@kapiti.co.nz>:
If class X has a method <=>(aX), I can sort an Array containing
instances of X using Array.sort!.What I really would like is an array that is always ordered. IOW, I want
the object to be inserted at the correct location inside the array when
the object is added to the array.Is there an efficient way to do this?
Yes. You can either use binary search on the Array to insert or you
use a Tree. Both can be found in RAA:http://raa.ruby-lang.org/project/ruby-bsearch/
http://raa.ruby-lang.org/project/ruby-rbtree/
Thanks Robert, this RAA is a little treasure chest!
Actually, I found the the bsearch array extensions do a fantastic job
for what I need. The only thing I added was a couple of methods to
add/remove elements:
#
# Add an element at the correct location (does not allow duplicates)
#
def bsearch_insert(element)
bounds = bsearch_range { | x | x <=> element }
if bounds.first == bounds.last then
self.insert(bounds.first, element)
bounds.first
else
nil
end
end
#
# Delete an element from the array
#
def bsearch_delete(element)
idx = bsearch_first { | x | x <=> element }
self.delete_at(idx) unless idx == nil
end
Thanks heaps (to all the other people who replied too of course!)
Pete
--
Posted via http://www.ruby-forum.com/\.
Peter Hug wrote:
> If class X has a method <=>(aX), I can sort an Array containing
> instances of X using Array.sort!.
>
> What I really would like is an array that is always ordered. IOW, I want
> the object to be inserted at the correct location inside the array when
> the object is added to the array.
>
> Is there an efficient way to do this?
>
> PeteOne option is to subclass Array and override the methods you use to
insert the elements. For example, consider the following:class OrderedArray < Array
May I humbly suggest that SortedArray might be a more accurate choice of name.
Arrays are by nature ordered, it's just that the order doesn't happen
to be determined by the sort order of the elements.
Another option is to use delegation to wrap the Array, and just
implement the methods you desire:
A much better choice, but.
class OrderedArray < Array
Should be just
class OrderedArray
No need to subclass Array.
On 3/11/08, Harm Aa <nepaccount@gmail.com> wrote:
--
Rick DeNatale
My blog on Ruby
http://talklikeaduck.denhaven2.com/
Ruby, unfortunately is really lacking on this front.
Did you see my references to libs in RAA? Do they lack something that you need?
When doing geometric
stuff, I find every ounce of C++ STL useful. An STL-like ruby lib would be
useful. External iterators are also very important. Ruby's normal internal
iterators (what others might call visitors) don't have the same flexibility
(caller can go forward/backward/read/write/erase/insert at will).
That's an interesting point you make. I haven't noticed the lack of
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. 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 =.
Can you leak a bit more information about the scenarios where you need
more / different behavior?
Kind regards
robert
2008/3/11, Eric Mahurin <eric.mahurin@gmail.com>:
--
use.inject do |as, often| as.you_can - without end
> 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.
When doing geometric
> stuff, I find every ounce of C++ STL useful. An STL-like ruby lib
would be
> useful. External iterators are also very important. Ruby's normal
internal
> iterators (what others might call visitors) don't have the same
flexibility
> (caller can go forward/backward/read/write/erase/insert at will).That's an interesting point you make. I haven't noticed the lack of
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.
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.
On Tue, Mar 11, 2008 at 9:18 AM, Robert Klemme <shortcutter@googlemail.com> wrote:
2008/3/11, Eric Mahurin <eric.mahurin@gmail.com>:
From my experience, many/most algorithms you implement on large geometric or