Sorting a Hash

ruby-talk
1

I want to have a hash with its elements sorted with a custom sort order.
Consider the example

···

#---------------------
test_hash = {"A" => "first", "B" => "second"}
puts test_hash.keys.join(", ")
order_arr = ["B", "A"]

test_hash.sort do |x,y|
   (order_arr.index(x[0])?order_arr.index(x[0]):order_arr.length) <=>
(order_arr.index(y[0])?order_arr.index(y[0]):order_arr.length)
end
puts test_hash.keys.join(", ")
#----------------------

Output:
  A, B
  => true

I want to order such that the keys (or values) when returned in an array are
ordered.
Obviously the above snipper does *not* work because Hash#sort does not sort
the Hash but returns an array of arrays with elements sorted according to
sort block.

I can maintain a parallel array of sorted keys but it is kind of kludgy.
Can I sort the hash "in place" such that the Hash#keys and Hash#values
return sorted results, without me having to maintain this array of arrays
separately?

TIA

2

I can maintain a parallel array of sorted keys but it is kind of kludgy.
Can I sort the hash "in place" such that the Hash#keys and Hash#values
return sorted results, without me having to maintain this array of arrays
separately?

The short answer is "No". :slight_smile: There's a bunch of SortedHashes floating out
there on the net though, so you don't have to write it yourself.

TIA

···

On 2/28/07, Nasir Khan <rubylearner@gmail.com> wrote:

3

this __exactly__ what rbtree does. look on the raa.

-a

···

On Thu, 1 Mar 2007, Nasir Khan wrote:

I want to have a hash with its elements sorted with a custom sort order.
Consider the example

--
be kind whenever possible... it is always possible.
- the dalai lama

4

Well there's nothing stopping you from adding methods to Hash to
return sorted keys and values. Of course you can also just do

hash.keys.sort
or
hash.values.sort

The first one will likely do what you want, but I suspect that what
you really want for values is to get them as ordered by the sorted
keys.

Here's a quick implementation of two additional methods for hash, I
wouldn't recommend changing the implementation of the existing keys
and values methods:

rick@frodo:/public/rubyscripts$ cat shash.rb
class Hash

  def sorted_keys(&sort_block)
    keys.sort(&sort_block)
  end

  def values_sorted_by_keys(&sort_block)
    values_at(*sorted_keys(&sort_block))
  end
end

test_hash = {"Fred" => "Wilma", "Barney" => "Betty",
             "Ricky" => "Lucy", "Fred" => "Ethel",
             "Ralph" => "Alice", "Ed" => "Trixie"}

p test_hash.keys
p test_hash.values
p test_hash.sorted_keys
p test_hash.values_sorted_by_keys
p test_hash.sorted_keys {|a, b| b <=> a}
p test_hash.values_sorted_by_keys {|a, b| b <=> a}

rick@frodo:/public/rubyscripts$ ruby shash.rb
["Ralph", "Ricky", "Barney", "Fred", "Ed"]
["Alice", "Lucy", "Betty", "Ethel", "Trixie"]
["Barney", "Ed", "Fred", "Ralph", "Ricky"]
["Betty", "Trixie", "Ethel", "Alice", "Lucy"]
["Ricky", "Ralph", "Fred", "Ed", "Barney"]
["Lucy", "Alice", "Ethel", "Trixie", "Betty"]

···

On 2/28/07, Nasir Khan <rubylearner@gmail.com> wrote:

I want to order such that the keys (or values) when returned in an array are
ordered.
Obviously the above snipper does *not* work because Hash#sort does not sort
the Hash but returns an array of arrays with elements sorted according to
sort block.

I can maintain a parallel array of sorted keys but it is kind of kludgy.
Can I sort the hash "in place" such that the Hash#keys and Hash#values
return sorted results, without me having to maintain this array of arrays
separately?

--
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/

5

Part of what makes a hash a hash is the fact that the elements in it are not
in a sequential order, as far as I know. Trying to maintain a hash "in
order" kind of ruins some of its hashiness. (Is that a word? :P)

Dave

6

Trying to maintain a hash "in

order" kind of ruins some of its hashiness.

Requiring a map to maintain its entries sorted is not that unusual. You may
need this (like in my case) when you need not just the keyed access to the
hash elements but also the whole map, but in some order.

Java's java.util.SortedMap does just that.
As Ara pointed out in one of the responses, rbtree is a Ruby implementation
of it. But I wonder why RAA download is not available anymore, nor there is
a gem. Does anyone know if this could be in future Ruby versions?

Thanks Rick for a simple solution which externally does what I want from it,
however it sorts on each access to keys and values which is not very
efficient for cases when the map is not updated very frequently but is
accessed a number of times.
One could perhaps overload the = method and maintain a sorted parallel
array in the Hash object (this is what I did in my case).

Thanks for all the responses.

7

Works great in some cases, but array's function means that some operations are very slow.

I have a class library in IOWA that I extracted some time ago as a microproject that provides a structure that provides both hashlike and arraylike access semantics using a linked list with a hash key -> node index.

http://rubyforge.org/frs/download.php/12908/LinkedList_0.99.2.9.tar.gz

Kirk Haines

···

On Fri, 2 Mar 2007, Nasir Khan wrote:

One could perhaps overload the = method and maintain a sorted parallel
array in the Hash object (this is what I did in my case).

8

> One could perhaps overload the = method and maintain a sorted parallel
> array in the Hash object (this is what I did in my case).

Works great in some cases, but array's function means that some operations
are very slow.

Array is usually one of the fastest classes in Ruby. Of course the
real facts come from benchmarking.

Another approach would be to modify the code I posted and cache the
sorted keys, and use = to invalidate the cache, then re-sort on the
next access.

But one has to be careful if we are talking about patching Hash,
since if you look at the implementation of Hash you'll find that not
all changes go through the = method. There's a primitive c function
called rb_hash_aset which is used by several other methods besides
=.

I have a class library in IOWA that I extracted some time ago as a
microproject that provides a structure that provides both hashlike and
arraylike access semantics using a linked list with a hash key -> node
index.

http://rubyforge.org/frs/download.php/12908/LinkedList_0.99.2.9.tar.gz

This appears to be doing something different, it appears to be
providing some kind of a hybrid of a hash, and an array with set-like
behavior as well.

Rather than sorting the keys, it gives a sort of the insertion order
access which Hal Fulton keeps asking for. But it also has the dequeue
methods from array which push/pop/shift/unshift single values, BUT
since in this case it uses the value for the key, it also removes any
existing element with the value before adding it back.

···

On 3/1/07, khaines@enigo.com <khaines@enigo.com> wrote:

On Fri, 2 Mar 2007, Nasir Khan wrote:

--
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/

9

Array is usually one of the fastest classes in Ruby. Of course the
real facts come from benchmarking.

True. But if trying to deal with ordering elements stored in a hash, and one deletes (for example) one of those elements, one has to then do a delete on the array. If the array isn't short, this is slow. I've benchmarked this stuff to death before.

This appears to be doing something different, it appears to be
providing some kind of a hybrid of a hash, and an array with set-like
behavior as well.

Rather than sorting the keys, it gives a sort of the insertion order
access which Hal Fulton keeps asking for. But it also has the dequeue
methods from array which push/pop/shift/unshift single values, BUT
since in this case it uses the value for the key, it also removes any
existing element with the value before adding it back.

All true. And I admit that I am guilty of deleting the early parts of this conversation before noticing it, so I was just pointing out that if one's use case includes performing operations that arrays are slow at, that my lib might be useful. It mixes in Enumerable, so it is arbitrarily sortable.

Kirk Haines

···

On Fri, 2 Mar 2007, Rick DeNatale wrote: