Extending standard library by priority queue or search tree

  • Thread starter Artem Voroztsov
  • Start date

A

Artem Voroztsov

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
 
Ad

Advertisements

R

Robert Klemme

2008/9/9 Artem Voroztsov said:
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

Bad idea since this will change the character of Hash completely -
also, it's no longer a Hash then.
2) adding new class PriorityQueue to standard library
3) 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 search

Kind regards

robert
 
J

Joel VanderWerf

Robert said:
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
 
Ad

Advertisements

A

Artem Voroztsov

Thank you all!

2008/9/9 Joel VanderWerf said:
Robert said:
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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top