Extending standard library by priority queue or search tree

[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

 

[Robert Klemme]

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

 

[Joel VanderWerf]

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

 

[Artem Voroztsov]

Thank you all!

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