From: Robert Klemme <shortcutter@...>
Date: 2011-06-22T22:24:03+09:00
Subject: Re: How to order a hash based on its keys?

On Wed, Jun 22, 2011 at 11:50 AM, Iñaki Baz Castillo <ibc@aliax.net> wrote:
> 2011/6/22 Robert Klemme <shortcutter@googlemail.com>:
>>> I already worker with rbtree. The only difference (or one of them) is
>>> the way in which keys are inserted. rbtree requires all the keys being
>>> the same class. In my tests rbtree is better for deleting elements but
>>> worse than a Hash for inserting them.
>>
>> <snip>benchmark</snip>
>>
>> Now I am confused.  What do you need?  A fast data structure?  An
>> ordered data structure?  What is more important?  You will need to do
>> a trade off here.  What are your requirements anyway?
>
> Ok. I get some data and convert it into a Hash whose key is a priority
> value (integer, 0 is the best priority). The value of each entry is of
> course the data value associated with such priority. But such hash has
> not been ordered, this is, probably entry 1 has priority 2 while entre
> 2 has priority 1 (or whatever).

Well, in that case an Array would be much more efficient.  You just
need a way to deal with holes, e.g.

prio_data = []

def prio_data.each_pair
  each_with_index do |x,i|
    yield i, x if x
  end
end

prio_data[1] = "foo"
prio_data[4] = "bar"

prio_data.each_pair {|prio,v| printf "key=%p val=%p\n", prio, v}

> Then I just want to get a new hash in which entries are ordered by
> priority.

Why do you need a second container object?  Is this just for sorting
purposes or do you actually need to maintain the state from a given
point in time?

Kind regards

robert


PS: In similar situations a priority queue can be helpful.
http://en.wikipedia.org/wiki/Priority_queue

-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/