Extending standard library by priority queue or search tree

Ruby
1

I’d like to have guide for C++ programmers who wants to learn Ruby.
This guide should explain how to do things in Ruby they used to do in
C++, STL.

STL has container map which allows us to do the following
insert(key,value)
find_by_key(key)
delete_by_key(key)
min_by_key()
max_by_key()
extract_min_by_key()
extract_max_by_key()

running O(log N) each (N - number of elements in container)

So map could acts as associative array, and as priority queue as well.

Simple use case: find M most frequent words in big text of size N in
time O( N * log(M) ) or faster.

I don’t know how to solve this problem in Ruby using only standard
classes and not using gems (PriorityQueue) and not writing data
structures (RB-trees, or binary heap, or …) by myself.

Is it possible?

What do you think about

  1. implementing Hash as RB-tree and adding methods :first and :last
    returning min and max pair by key
  2. adding new class PriorityQueue to standard library
  3. adding new class SearchTree to standard library, which allows to do
    all that map does
    ?

Artem

2

2008/9/9 Artem V. [email protected]:

extract_max_by_key()
structures (RB-trees, or binary heap, or …) by myself.

Is it possible?

What do you think about

  1. implementing Hash as RB-tree and adding methods :first and :last
    returning min and max pair by key

Bad idea since this will change the character of Hash completely -
also, it’s no longer a Hash then.

  1. adding new class PriorityQueue to standard library
  2. adding new class SearchTree to standard library, which allows to do
    all that map does

Rather put an RBTree into the std lib. Note that such a thing does
exist already:

http://raa.ruby-lang.org/search.rhtml?search=rbtree

See also

http://raa.ruby-lang.org/search.rhtml?search=binary%20search

Kind regards

robert

3

Robert K. wrote:

Rather put an RBTree into the std lib. Note that such a thing does
exist already:

http://raa.ruby-lang.org/search.rhtml?search=rbtree

Also: gem install rbtree

Using rbtree, a priority queue is simple:

require ‘rbtree’

class PriorityQueue
def initialize
@tree = MultiRBTree.new
@mutex = Mutex.new
@cond = ConditionVariable.new
end

Push +obj+ with priority equal to +pri+ if given or, otherwise,

the result of sending #queue_priority to +obj+. Objects are

dequeued in priority order, and first-in-first-out among objects

with equal priorities.

def push(obj, pri = obj.queue_priority)
@mutex.synchronize do
@tree.store(pri, obj)
@cond.signal
end
end

def pop(non_block=false)
@mutex.synchronize do
if ([email protected])
return @tree.delete(last[0]) # highest key, oldest first
end

   if non_block
     raise ThreadError, "priority queue empty"
   end

   loop do
     @cond.wait(@mutex)
     if ([email protected])
       return @tree.delete(last[0])
     end
   end
 end

end
end

pq = PriorityQueue.new
pq.push “a”, 1
pq.push “c”, 3
pq.push “b”, 2
p pq.pop

4

Thank you all!

2008/9/9 Joel VanderWerf [email protected]: