How to order a hash based on its keys?

Discussion in 'Ruby' started by Iñaki Baz Castillo, Jun 21, 2011.

  1. Hi, I want to order a hash using itds keys:

    irb> a =3D { 2=3D>"2", 3=3D>"3", 1=3D>"1" }
    irb> a.sort
    [[1, "1"], [2, "2"], [3, "3"]]

    But I want a resulting hash with keys ordered:

    { 1=3D>"1", 2=3D>"2", 3=3D>"3"}

    Is there any efficiente way? (I don't want the hast to be converted to
    an array and the to a hash again).

    Thanks.

    --=20
    I=C3=B1aki Baz Castillo
    <>
     
    Iñaki Baz Castillo, Jun 21, 2011
    #1
    1. Advertisements

  2. When you hear "order" and "hash" in the same sentence, you should
    think "hashes aren't ordered".
    1.9 keeps hashes initially in insertion order, but if you don't create
    your hash with the keys in the order you want, since Hash isn't
    ordered, I don't think there's a way to get what you want without
    creating an Array and then a second Hash, with the keys in the order
    you want.
     
    Adam Prescott, Jun 21, 2011
    #2
    1. Advertisements

  3. Atleast according to this StackOverflow question:
    http://stackoverflow.com/questions/4339553/sort-hash-by-key-return-hash-in-=
    ruby

    Hash[h.sort] seems to be the best way.

    Vikhyat Korrapati
    http://vikhyat.net/
     
    Vikhyat Korrapati, Jun 21, 2011
    #3
  4. Iñaki Baz Castillo

    Josh Cheek Guest

    (Resending this b/c it looks like it got blocked or the server crashed the
    first time. Hopefully it's not a duplicate)

    You could create your own data structure which keeps the elements sorted an=
    d
    supports the hash interface, ie https://gist.github.com/1038031

    I don't know if the overhead of keeping them sorted (in this case, in a BST=
    )
    is lower than the overhead of the Array. But if you are frequently iteratin=
    g
    over it, I would expect it to pay off (ie you would have to create a new
    array each time you iterate over a Hash, but you will not have to create
    over a SortedHash. So probably depends on the use case.
     
    Josh Cheek, Jun 21, 2011
    #4
  5. You could create your own data structure which keeps the elements sorted and
    Or maybe a rb tree (red-black tree) from the rbtree gem. Haven't used
    it myself though.
     
    Anurag Priyam, Jun 21, 2011
    #5
  6. See Adam's and Josh's replies: a Hash is generally unordered.
    However, what do you need this for? If it is for debugging purposes
    then you might as well override #inspect on a per instance basis or
    change it in Hash (not recommended). If you need that for other
    reasons then maybe a tree might be a better choice. There is for
    example
    http://raa.ruby-lang.org/project/ruby-rbtree/

    Kind regards

    robert

    --=20
    remember.guy do |as, often| as.you_can - without end
    http://blog.rubybestpractices.com/
     
    Robert Klemme, Jun 21, 2011
    #6
  7. though true a hash doesn't maintain order, you can sort the keys and
    use the result to do something.... (though you couldn't return an
    ordered hash)

    hashes_arent_ordered = { 2=>"2", 3=>"3", 1=>"1" }
    hashes_arent_ordered.keys.sort.each {|key| puts "key #{key}, value
    #{hashes_arent_ordered[key]}"}

    -Benjamin, Chicago
     
    Benjamin Fleischer, Jun 21, 2011
    #7
  8. It adds a bit overhead (of course):

    irb> h =3D {"a"=3D>1, "c"=3D>3, "b"=3D>2, "d"=3D>4}

    irb> Benchmark.realtime { 100000.times { h.sort } }
    0.787590503692627

    irb> Benchmark.realtime { 100000.times { Hash[h.sort] } }
    1.1099345684051514

    But seems good enough :)


    --=20
    I=C3=B1aki Baz Castillo
    <>
     
    Iñaki Baz Castillo, Jun 21, 2011
    #8
  9. I guess you didn't mind doing then? :)
     
    Adam Prescott, Jun 21, 2011
    #9
  10.  
    Iñaki Baz Castillo, Jun 21, 2011
    #10
  11. Hi, I don't understand your comment.


    --=20
    I=C3=B1aki Baz Castillo
    <>
     
    Iñaki Baz Castillo, Jun 21, 2011
    #11
  12. Sorry, my dog pressed "sent mail".

    I meant that I don't understand the point of your comments. In Ruby
    1.9 Hashes are ordered. I cannot change the order after creating them,
    but if you inspect elements of a Hash you get them in the order in
    which they were inserted. This is valid and useful for me (in my
    case).


    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.

    You can check it:

    ------------------------------------------
    require "benchmark"

    @hash =3D {}
    @rbtree =3D RBTree.new


    TIMES =3D ARGV[0] ? ARGV[0].to_i : 10000
    WORD =3D "z9hG4bK".freeze


    def gen_word(word, n)
    case word
    when :fixed_begin
    WORD + n.to_s
    when :dynamic_begin
    n.to_s + WORD
    end
    end

    def test(word)
    puts
    case word
    when :fixed_begin
    puts "Using word: \"z9hG4bK\" + n.to_s"
    when :dynamic_begin
    puts "Using word: n.to_s + \"z9hG4bK\""
    end

    puts
    printf "- Hash insertion: "
    puts time_hash_insertion =3D Benchmark.realtime {
    TIMES.times do |n|
    @hash[gen_word(word, n)] =3D 12345
    end
    }

    printf "- RBTree insertion: "
    puts time_rbtree_insertion =3D Benchmark.realtime {
    TIMES.times do |n|
    @rbtree[gen_word(word, n)] =3D 12345
    end
    }

    puts
    printf "- Hash deletion: "
    puts time_hash_deletion =3D Benchmark.realtime {
    TIMES.times do |n|
    @hash.delete(gen_word(word, n))
    end
    }

    printf "- RBTree deletion: "
    puts time_rbtree_deletion =3D Benchmark.realtime {
    TIMES.times do |n|
    @rbtree.delete(gen_word(word, n))
    end
    }

    puts
    puts "TOTAL:"
    puts "- Hash insertion + deletion: #{time_hash_insertion +
    time_hash_deletion}"
    puts "- RBTree insertion + deletion: #{time_rbtree_insertion +
    time_rbtree_deletion}"
    end


    puts "Entries: #{TIMES}"
    puts
    test:)fixed_begin)
    puts
    test:)dynamic_begin)
    ------------------------------------------



    Results:

    ------------------------
    Entries: 10000


    Using word: "z9hG4bK" + n.to_s

    - Hash insertion (seconds): 0.020041227340698242
    - RBTree insertion (seconds): 0.041683197021484375

    - Hash deletion (seconds): 0.035521745681762695
    - RBTree deletion (seconds): 0.023290157318115234

    TOTAL:
    - Hash insertion + deletion (seconds): 0.05556297302246094
    - RBTree insertion + deletion (seconds): 0.06497335433959961


    Using word: n.to_s + "z9hG4bK"

    - Hash insertion (seconds): 0.019947528839111328
    - RBTree insertion (seconds): 0.0295107364654541

    - Hash deletion (seconds): 0.029720067977905273
    - RBTree deletion (seconds): 0.01738262176513672

    TOTAL:
    - Hash insertion + deletion (seconds): 0.0496675968170166
    - RBTree insertion + deletion (seconds): 0.04689335823059082
    ------------------------


    --=20
    I=C3=B1aki Baz Castillo
    <>
     
    Iñaki Baz Castillo, Jun 21, 2011
    #12
    1. Advertisements

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 (here). After that, you can post your question and our members will help you out.