Forum: Ruby Preserve insert order in a Hash

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
40700f4fc57ab1ed04e235c7b7ae4d50?d=identicon&s=25 Me Me (melmoth)
on 2008-09-18 11:50
Hi,
I would like to know if it's possible to insert values in a Hash and
then extract all of them in the same insertion order.

I noticed that if I then try to print the content of an Hash using
"each" the order is not the same as the insertion.

Thanks
6087a044557d6b59ab52e7dd20f94da8?d=identicon&s=25 Peña, Botp (Guest)
on 2008-09-18 11:58
(Received via mailing list)
From: Me Me [mailto:emanuelef@tiscali.it]
# I would like to know if it's possible to insert values in a Hash and
# then extract all of them in the same insertion order.

only in ruby 1.9

C:\ruby1.9\bin>irb.bat
> h={}
=> {}

> h[1]=1
=> 1

> h[2]=1
=> 1

> h[3]=1
=> 1

> h
=> {1=>1, 2=>1, 3=>1}

> h[1.5]=1
=> 1

> h
=> {1=>1, 2=>1, 3=>1, 1.5=>1}

> h[0]=1
=> 1

> h
=> {1=>1, 2=>1, 3=>1, 1.5=>1, 0=>1}

> RUBY_VERSION
=> "1.9.0"
Da33a4ac652c1c8900392a8599206640?d=identicon&s=25 Thomas B. (tpreal)
on 2008-09-18 12:01
Peña, Botp wrote:
> From: Me Me [mailto:emanuelef@tiscali.it]
> # I would like to know if it's possible to insert values in a Hash and
> # then extract all of them in the same insertion order.
>
> only in ruby 1.9

Could anybody explain why this feature was added? Isn't it going to slow
down the operations on the Hash? I think it is useless to mix Array with
Hash.

TPR.
40700f4fc57ab1ed04e235c7b7ae4d50?d=identicon&s=25 Me Me (melmoth)
on 2008-09-18 12:21
Thomas B. wrote:
> Peña, Botp wrote:
>> From: Me Me [mailto:emanuelef@tiscali.it]
>> # I would like to know if it's possible to insert values in a Hash and
>> # then extract all of them in the same insertion order.
>>
>> only in ruby 1.9
>
> Could anybody explain why this feature was added? Isn't it going to slow
> down the operations on the Hash? I think it is useless to mix Array with
> Hash.
>
> TPR.

well, basically I just need a Hash to use String as indexes like

sourceInfo = Hash.new
sourceInfo["var1"]=123
sourceInfo["var2"]=2
sourceInfo["var3"]=3
sourceInfo["var4"]=23

and then print them in the exact order of insertion
F472b397918df02e70d8d7d0cf086c00?d=identicon&s=25 Dick Davies (Guest)
on 2008-09-18 12:26
(Received via mailing list)
On Thu, Sep 18, 2008 at 11:13 AM, Me Me <emanuelef@tiscali.it> wrote:
>> Hash.
>
> and then print them in the exact order of insertion

Can't you just sort them on the way out?
i.e.

sourceinfo.keys.sort.each { |k|
  sourceinfo[k].do_stuff
}
40700f4fc57ab1ed04e235c7b7ae4d50?d=identicon&s=25 Me Me (melmoth)
on 2008-09-18 12:29
Dick Davies wrote:
> On Thu, Sep 18, 2008 at 11:13 AM, Me Me <emanuelef@tiscali.it> wrote:
>>> Hash.
>>
>> and then print them in the exact order of insertion
>
> Can't you just sort them on the way out?
> i.e.
>
> sourceinfo.keys.sort.each { |k|
>   sourceinfo[k].do_stuff
> }

thanks
well in this case they will be sorted alphabetically, right?
the example is simplyfied, in my case the keys have differernt names.
2a013c7c624c6e96320c369a1cbc26ee?d=identicon&s=25 unknown (Guest)
on 2008-09-18 12:32
(Received via mailing list)
a  = []
a.push 1
a.push 2
a.push 3
a.each {|e|puts e}
40700f4fc57ab1ed04e235c7b7ae4d50?d=identicon&s=25 Me Me (melmoth)
on 2008-09-18 12:34
unknown wrote:
> a  = []
> a.push 1
> a.push 2
> a.push 3
> a.each {|e|puts e}

I think this is not my case, I need a Hash as I explained
0ec4920185b657a03edf01fff96b4e9b?d=identicon&s=25 Yukihiro Matsumoto (Guest)
on 2008-09-18 12:36
(Received via mailing list)
Hi,

In message "Re: Preserve insert order in a Hash"
    on Thu, 18 Sep 2008 18:54:20 +0900, "Thomas B." <tpreal@gmail.com>
writes:

|Could anybody explain why this feature was added?

Useful for some cases, especially for keyword arguments.

|Isn't it going to slow down the operations on the Hash?

No. hash reference operation does not touch order information, only
for iteration.  Memory consumption increased a bit.

              matz.
4feed660d3728526797edeb4f0467384?d=identicon&s=25 Bill Kelly (Guest)
on 2008-09-18 13:46
(Received via mailing list)
From: "Me Me" <emanuelef@tiscali.it>
>
> I think this is not my case, I need a Hash as I explained

Here's an implementation for ruby 1.8 ... I apologize for the lack of
tests.


class InsertOrderPreservingHash
  include Enumerable

  def initialize(*args, &block)
    @h = Hash.new(*args, &block)
    @ordered_keys = []
  end

  def []=(key, val)
    @ordered_keys << key unless @h.has_key? key
    @h[key] = val
  end

  def each
    @ordered_keys.each {|k| yield(k, @h[k])}
  end
  alias :each_pair :each

  def each_value
    @ordered_keys.each {|k| yield(@h[k])}
  end

  def each_key
    @ordered_keys.each {|k| yield k}
  end

  def keys
    @ordered_keys
  end

  def values
    @ordered_keys.map {|k| @h[k]}
  end

  def clear
    @ordered_keys.clear
    @h.clear
  end

  def delete(k, &block)
    @ordered_keys.delete k
    @h.delete(k, &block)
  end

  def reject!
    del = []
    each_pair {|k,v| del << k if yield k,v}
    del.each {|k| delete k}
    del.empty? ? nil : self
  end

  def delete_if(&block)
    reject!(&block)
    self
  end

  %w(merge!).each do |name|
    define_method(name) do |*args|
      raise NotImplementedError, "#{name} not implemented"
    end
  end

  def method_missing(*args)
    @h.send(*args)
  end
end


# example:

h = InsertOrderPreservingHash.new

h[:aaa] = 0
h[:foo] = 123
h[:bar] = 456
h[:baz] = 789
h.delete :aaa
h[:aaa] = 1

h.each_pair {|k,v| p [k,v]}

# produces:

[:foo, 123]
[:bar, 456]
[:baz, 789]
[:aaa, 1]


Regards,

Bill
753dcb78b3a3651127665da4bed3c782?d=identicon&s=25 Brian Candler (candlerb)
on 2008-09-18 14:50
> well, basically I just need a Hash to use String as indexes like
>
> sourceInfo = Hash.new
> sourceInfo["var1"]=123
> sourceInfo["var2"]=2
> sourceInfo["var3"]=3
> sourceInfo["var4"]=23

What do you want to happen if sourceInfo["var2"] is assigned a second
time? Do you want to replace it where it originally was in the sequence,
or do you want to delete it and add the new value to the end? Or do you
want both elements to appear at the same time? Or doesn't it matter?

I am just wondering because perhaps all you need is

sourceInfo = []
sourceInfo << ["var1",123]
sourceInfo << ["var2",2]
sourceInfo << ["var3",3]
sourceInfo << ["var4",4]
sourceInfo.each { |k,v| puts "#{k}=>#{v}" }

At least, that's fine if all you want to do is iterate over the
collection and add new elements. Finding or deleting elements by key
requires a linear search:

dummy,value = sourceInfo.find { |k,v| k == "var2" }

However you can optimise this by building a hash as you go which points
to the same elements; or you could build an array containing just the
keys.

  class HashAndArray
    def initialize
      @h, @a = {}, []
    end
    def [](k)
      @h[k]
    end
    def []=(k,v)
      @a << k unless @h.has_key?(k)
      @h[k] = v
    end
    def each
      @a.each { |k| yield k,@h[k] }
    end
  end

  sourceInfo = HashAndArray.new
  sourceInfo["var1"]=123
  sourceInfo["var2"]=2
  sourceInfo["var3"]=3
  sourceInfo["var4"]=23
  sourceInfo.each { |k,v| puts "#{k}=>#{v}" }
  puts sourceInfo["var2"]

Adding a delete() method is left as an exercise.
8f6f95c4bd64d5f10dfddfdcd03c19d6?d=identicon&s=25 Rick Denatale (rdenatale)
on 2008-09-18 14:52
(Received via mailing list)
On Thu, Sep 18, 2008 at 6:28 AM, Yukihiro Matsumoto
<matz@ruby-lang.org>wrote:

> |Isn't it going to slow down the operations on the Hash?
>
> No. hash reference operation does not touch order information, only
> for iteration.  Memory consumption increased a bit.
>

If I remember correctly, it's been a while since I looked at the code,
1.9
implements this by using a singly linked list which introduces a small
overhead only when elements are either added or deleted.

--
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/
F1d6cc2b735bfd82c8773172da2aeab9?d=identicon&s=25 Nobuyoshi Nakada (nobu)
on 2008-09-18 14:55
(Received via mailing list)
Hi,

Yukihiro Matsumoto wrote in [ruby-talk:315237]:
At Thu, 18 Sep 2008 19:28:28 +0900,
> |Could anybody explain why this feature was added?
>
> Useful for some cases, especially for keyword arguments.

And the performance of iterations improved a little, but
significantly.
0ec4920185b657a03edf01fff96b4e9b?d=identicon&s=25 Yukihiro Matsumoto (Guest)
on 2008-09-18 15:11
(Received via mailing list)
Hi,

In message "Re: Preserve insert order in a Hash"
    on Thu, 18 Sep 2008 21:44:23 +0900, "Rick DeNatale"
<rick.denatale@gmail.com> writes:

|> No. hash reference operation does not touch order information, only
|> for iteration.  Memory consumption increased a bit.
|>
|
|If I remember correctly, it's been a while since I looked at the code, 1.9
|implements this by using a singly linked list which introduces a small
|overhead only when elements are either added or deleted.

You're right.  Thank you for pointing out.

              matz.
8f6f95c4bd64d5f10dfddfdcd03c19d6?d=identicon&s=25 Rick Denatale (rdenatale)
on 2008-09-18 15:18
(Received via mailing list)
On Thu, Sep 18, 2008 at 8:42 AM, Brian Candler <b.candler@pobox.com>
wrote:

> or do you want to delete it and add the new value to the end? Or do you
> want both elements to appear at the same time? Or doesn't it matter?


FWIW, Ruby 1.9 seems to keep the original insertion order, reassiging a
value to an existing key leaves the order unchanged:

$ irb1.9
irb(main):001:0> a = {a: 1, b: 2, c: 3}
=> {:a=>1, :b=>2, :c=>3}
irb(main):002:0> a.keys
=> [:a, :b, :c]
irb(main):003:0> a[:b] = 4
=> 4
irb(main):004:0> a.keys
=> [:a, :b, :c]
irb(main):005:0> a
=> {:a=>1, :b=>4, :c=>3}
irb(main):006:0>

At least my somewhat out of date 1.9 does

$ ruby1.9 -v
ruby 1.9.0 (2008-03-21 revision 0) [i686-darwin9.2.2]

--
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/
40700f4fc57ab1ed04e235c7b7ae4d50?d=identicon&s=25 Me Me (melmoth)
on 2008-09-18 17:24
Bill Kelly wrote:
> From: "Me Me" <emanuelef@tiscali.it>
>>
>> I think this is not my case, I need a Hash as I explained
>
> Here's an implementation for ruby 1.8 ... I apologize for the lack of
> tests.
>

Thanks a lot! That worked perfectly
Bye
1bac2e65d64faf472cf2ebc94f0f5ee0?d=identicon&s=25 Ara Howard (ahoward)
on 2008-09-18 17:57
(Received via mailing list)
On Sep 18, 2008, at 3:42 AM, Me Me wrote:

>
gem install orderedhash

a @ http://codeforpeople.com/
Ea24630ec42f69f9b67d8f9b5b203c55?d=identicon&s=25 jim finucane (Guest)
on 2008-09-18 21:23
(Received via mailing list)
If scale is needed this has been implemented by Takuma Ozawa as a very
efficient RB tree which I used on a Mac:

sudo gem install rbtree
irb
require 'rbtree'
a=RBTree.new
a['x']=1
a['z']=2
a['y']=3
a
============> #RBTree:{'x'=>1,'y'=>3,'z'=>2}
1bac2e65d64faf472cf2ebc94f0f5ee0?d=identicon&s=25 Ara Howard (ahoward)
on 2008-09-19 00:11
(Received via mailing list)
On Sep 18, 2008, at 10:01 AM, jim finucane wrote:

> a
cfp:~ > cat a.rb
require 'rubygems'
require 'rbtree'


# rbtree is sorted by the keys 'natural' sort order
# *not* the insertion order

rb = RBTree.new

rb['z'] = 3
rb['y'] = 2
rb['x'] = 1

rb.each do |key, value|
   puts "#{ key } : #{ value }"
end



cfp:~ > ruby a.rb
x : 1
y : 2
z : 3


a @ http://codeforpeople.com/
84dc575c33a123789521d53cad0f62ae?d=identicon&s=25 Lloyd Linklater (lloyd)
on 2008-09-19 17:55
Peña, Botp wrote:
> From: Me Me [mailto:emanuelef@tiscali.it]
> # I would like to know if it's possible to insert values in a Hash and
> # then extract all of them in the same insertion order.
>
> only in ruby 1.9

Well, that is not *entirely* true.

h={}
p h
h[1]=1
p h
h[2]=1
p h
h[3]=1
p h
h
p h
h[1.5]=1
p h
h
p h
h[0]=1
p h
h
p h

yields:

{}
{1=>1}
{1=>1, 2=>1}
{1=>1, 2=>1, 3=>1}
{1=>1, 2=>1, 3=>1}
{1=>1, 2=>1, 3=>1, 1.5=>1}
{1=>1, 2=>1, 3=>1, 1.5=>1}
{1=>1, 2=>1, 3=>1, 1.5=>1, 0=>1}
{1=>1, 2=>1, 3=>1, 1.5=>1, 0=>1}


in JRUBY 1.1 which I am running on windows under netbeans.
This topic is locked and can not be replied to.