[ruby-list:43857] Hashへの生成順は保障されないのか？

[Hiroshi Kasamatsu]

こんにちは、笠松と申します。
vine linux 4.1でruby1.8.5(rpmパッケージ版)を使っています。

次のようなHashを生成したとします。
pair=Hash.new
pair["apple"]="apple"
pair["and"]="and"
pair["bee"]="bee"
pair["cat"]="cat"

このhashを表示したら
apple=>apple
and=>and
bee=>bee
cat=>cat
のように生成順を期待していたのですが、

pair.each do |key, val|
  print key, "=>", val, "\n"
end
で表示させると、
cat=>cat
and=>and
bee=>bee
apple=>apple
の順になってしまいました。できれば生成していった順で
表示されるとよいのですが、hashの中身はどのような基準で
並べられているのでしょうか？
ご教授の程、よろしくお願いいたします。

[Urabe Shyouhei-4]

Hiroshi Kasamatsu wrote:
> の順になってしまいました。できれば生成していった順で
> 表示されるとよいのですが、hashの中身はどのような基準で
> 並べられているのでしょうか？

うーん、Hashはその名前のとおりHashです。
もうちょっと具体的にいうと外部連鎖ハッシュです。

ハッシュがどのような仕組みになっているかはちょっとこのML
の趣旨からは外れるような気がするので適宜データ構造の教科
書をご覧になることなどをおすすめしますが、Hashという名前
のクラスでなんらかの順序のようなものが保存される期待を抱
かれるという発想は斬新でした。どのような文脈からそのよう
に思われたのか、後学のために教えていただけますか?

[内山紀明]

はじめまして，内山と申します．

> の順になってしまいました。できれば生成していった順で
> 表示されるとよいのですが、hashの中身はどのような基準で

Hashクラスを継承したクラスを定義してはいかがでしょうか．
例えば，以下のようにOrderedHashクラスを定義します．

class OrderedHash < Hash
  def initialize
    @index = []
  end

  def []=(key, val)
    @index.push(key)
    super(key, val)
  end

  def each
    @index.each do |key|
      yield(key, self[key])
    end
    self
  end
end

[]=とeachメソッドをオーバーライドしています．
結果として以下のようになります．

>> pair = OrderedHash.new
=> {}
>> pair["apple"]="apple"
=> "apple"
>> pair["and"]="and"
=> "and"
>> pair["bee"]="bee"
=> "bee"
>> pair["cat"]="cat"
=> "cat"
>> pair["dog"]="dog"
=> "dog"

>> pair.each do |key, val|
>>   print key, "=>", val, "\n"
>> end
apple=>apple
and=>and
bee=>bee
cat=>cat
dog=>dog
=> {"cat"=>"cat", "and"=>"and", "bee"=>"bee", "apple"=>"apple", "dog"=>"dog"}

ご参考になれば幸いです．


--
--- We Ain't Seen Nothin' Yet.
　内山 紀明
　uchiyama.noriaki@...
　http://blog.fulltext-search.biz/

[Shima Shizuo]

こんにちは、嶋です。

>Hashクラスを継承したクラスを定義してはいかがでしょうか．
>例えば，以下のようにOrderedHashクラスを定義します．
>
>class OrderedHash < Hash
>  def initialize
>    @index = []
>  end
>
>  def []=(key, val)
>    @index.push(key)
>    super(key, val)
>  end
>
>  def each
>    @index.each do |key|
>      yield(key, self[key])
>    end
>    self
>  end
>end

同じkeyを複数回指定されると、each で同じkey,valが複数回出てきて
しまいそうですね。

  def []=(key, val)
+    @index.delete(key)
    @index.push(key)
    super(key, val)
  end

とするのがいいかなぁ・・


----
Shima Shizuo  r6@...

[Yugui-2]

Yuguiと言います。

用途と実際のデータサイズにもよりますけれども、
データサイズが小さいかランダムアクセスが少ないのであればhash mapの代わりに
assoc vectorもありえますよね。

Arrayクラスにはそのためのassoc, rassocメソッドがあります。
役に立つか分かりませんが、ご参考までに。

--
Yugui
yugui@...
http://idm.s9.xrea.com

[Hiroshi Kasamatsu]

皆さん、早速のレスありがとうございます。
笠松です。Urabeさんの御指摘通りHashに順序まで期待するのは
Hashの趣旨からして無理があるのかもしれません。
ただ結果の表示は生成していった順が私にとって必要なので、
Yuguiさん、内山さん、嶋さんのアドバイス、参考にさせて
頂きたいと思います。

ところで、Urabeさんの次の御指摘ですが、

> ハッシュがどのような仕組みになっているかはちょっとこのML
> の趣旨からは外れるような気がするので適宜データ構造の教科
> 書をご覧になることなどをおすすめしますが、Hashという名前
> のクラスでなんらかの順序のようなものが保存される期待を抱
> かれるという発想は斬新でした。どのような文脈からそのよう
> に思われたのか、後学のために教えていただけますか?
>
今、タッチタイプの練習プログラムを作っているところで、
単語を表示させてそれをタッチタイプします。
表示された単語をkey,タイプされた文字列をvalとして
hashに格納します。終了後、結果を表示させて
うまく打てたかを見るわけですが、出来ればタイプしていった
順に表示された方がよく覚えているしフィードバックされやすいと
いった心理的なものです。結果のエラー分析だけというのであれば、
特別順番などは必要ではなく、表示単語とタイプされた結果の関係
だけでよいかと思います。

最後に、タイトルの保障は保証ですよね、お恥ずかしいです。

[Urabe Shyouhei-4]

Hiroshi Kasamatsu wrote:
> 今、タッチタイプの練習プログラムを作っているところで、
> 単語を表示させてそれをタッチタイプします。
> 表示された単語をkey,タイプされた文字列をvalとして
> hashに格納します。終了後、結果を表示させて
> うまく打てたかを見るわけですが、出来ればタイプしていった
> 順に表示された方がよく覚えているしフィードドバックされやすいと
> いった心理的なものです。結果のエラー分析だけというのであれば、
> 特別順番などは必要ではなく、表示単語とタイプされた結果の関係
> だけでよいかと思います。

これだけの情報からはなぜわざわざHashを使われるのかが見えてきません。
たとえば[[key1, val1], [key2, val2], ...]でも十分に役目を果たすでしょう。
なぜわざわざHashなんですかね?

[山崎雄介]

山崎（ゆ）です。

PseudoHashなるものがあります。
http://raa.ruby-lang.org/project/pseudohash/

require 'pseudohash'
pair = PseudoHash.new
pair["apple",true]="apple"
pair["and",true]="and"
pair["bee",true]="bee"
pair["cat",true]="cat"

pair.order.each do |key|
  print key, "=>", pair[key], "\n"
end

配布されているPseudoHashでは、順序付きにするのに、
pair["apple",true]="apple"
としなければいけないのですが、順序付け以外の目的でPseudoHashが必要な場合
はないと思ったので、[]メソッドを書き換えて使っています。

require 'pseudohash'

class PseudoHash
  def []=(k, *rest)
    val, set = rest.reverse
#   order.push k if set and not order.include? k
    order.push k if         not order.include? k
    aset(k,val)
  end
end

pair = PseudoHash.new
pair["apple"]="apple"
pair["and"]="and"
pair["bee"]="bee"
pair["cat"]="cat"

pair.order.each do |key|
  print key, "=>", pair[key], "\n"
end
_______________________
Yusuke Yamasaki <y-yamasaki@...>

[Masahiro Sugaya]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

菅谷です。
初めまして。
データ数が多い場合に同じような使い方をしたいのですが、

> Arrayクラスにはそのためのassoc, rassocメソッドがあります。
> 役に立つか分かりませんが、ご参考までに。

Arrayのassoc、rassocの計算量はどうなっているんでしょうか？
頭から順番に比較しているんでしょうかね。

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFGyZjyDP6vpMJARxYRAqIPAJ9M3SpiU9PZHNhXRZ/ce2nJV1JGWACeP7gm
LRErCE1wiZOMt7ogxkOWx9M=
=UIke
-----END PGP SIGNATURE-----

[Masahiro Sugaya]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

菅谷です。
すみません。ソースを見たらそうなってました。

> 頭から順番に比較しているんでしょうかね。


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (MingW32)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFGyaX0DP6vpMJARxYRAj08AKCtrLlIRQtNuEzFaN6NfHGep2YLZwCfaN1/
lLps9uYB99dl+hGPmfOkKCg=
=voYl
-----END PGP SIGNATURE-----

[Hiroshi Kasamatsu]

Urabeさん、笠松です。レスありがとうございます。

> これだけの情報からはなぜわざわざHashを使われるのかが見えてきません。
> たとえば[[key1, val1], [key2, val2], ...]でも十分に役目を果たすでしょう。
> なぜわざわざHashなんですかね?

そう言われてみれば、そうですね。ぱっと思い浮かんだのが
Hashだったので、Hashを使いました。

[Hiroshi Kasamatsu]

山崎さん、レスありがとうございます。
笠松です。


> PseudoHashなるものがあります。
> http://raa.ruby-lang.org/project/pseudohash

Hashにも順序があっていいと考えた人もいたんですね。少し、安心しました。
早速試してみたいと思います。

[Urabe Shyouhei-4]

Hiroshi Kasamatsu wrote:
>> これだけの情報からはなぜわざわざHashを使われるのかが見えてきません。
>> たとえば[[key1, val1], [key2, val2], ...]でも十分に役目を果たすでしょう。
>> なぜわざわざHashなんですかね?
>
> そう言われてみれば、そうですね。ぱっと思い浮かんだのが
> Hashだったので、Hashを使いました。

もちろんプログラマですから自分の直観を信じることは重要です。
けれど、ぱっとHashが思い浮かんだからってHashを使ってそこで
生成順が保存されないのを嘆かれるのは筋が違うでしょう。

大学などでアルゴリズム基礎論を学べば真っ先に教わるのが「適
切なアルゴリズムと適切なデータ構造はどちらが欠けてもダメ」
という話なはずです。適切なデータ構造が何かをもうちょっと調
査してから書かれた方がよかった気がしてなりません。

[cuzic]

cuzic です。

横レスですが・・・

> どのような文脈からそのように思われたのか、後学のために教えていただけますか?

Hash の生成順が保存されない件ですが、PHP 出身で Ruby を
始めた方はよく勘違いする箇所のように思います。
笠松さんが PHP 出身かどうかは分かりませんが。。

PHP では順序が保存されるのです。

$ php
<?php

$a = array();
$a["ruby"] = 1;
$a["perl"] = 2;
$a["java"] = 3;
$a["haskell"] = 4;
foreach($a as $key => $value){
  print $key . " " . $value . "\n";
}
?>
^D
ruby 1
perl 2
java 3
haskell 4

ではでは。

[Urabe Shyouhei-4]

cuzic wrote:
> PHP では順序が保存されるのです。
>
> $ php
> <?php
>
> $a = array();

この行からも分かるとおりPHPのあれはArrayなのです。
var_dump($a);するとちゃんとarray(4)と出てきますよ。
Arrayというクラスのオブジェクトで順序が保存されている
ことには何ら疑問をはさむ余地がないのは分かります。

翻ってRubyではArrayとHashは別建てのクラスなのは言うま
でもありません。もちろんArrayとHashが分かれていること
にはちゃんと設計上の意味があります。
「わざわざHashという名前が付けられてArrayとは厳密に区
別されているクラス」に対して順序の保存を期待するとい
うその感覚がまだ理解できません。なんでなんですか。

[Tanaka Akira-3]

In article <46C9E7BB.4060100@...>,
  Urabe Shyouhei <shyouhei@...> writes:

> 翻ってRubyではArrayとHashは別建てのクラスなのは言うま
> でもありません。もちろんArrayとHashが分かれていること
> にはちゃんと設計上の意味があります。

どんな意味でしょう?
--
[田中 哲][たなか あきら][Tanaka Akira]

[Urabe Shyouhei-4]

おお、田中さんを満足させる説明ってのは結構ハードル高そうだな。

ええと、基本的にRubyのクラス階層というのは振舞いが似てるから
という理由だけでサブクラスにしたり単一のクラスに統合したりは
しないように分けられているはずです。なんでかというと振舞いは
moduleとして取り出すことができるからです。たとえばStringと
ArrayはCレベルではほとんど同じ(配列のなかみがcharかVALUEかく
らいしか違わない)ですが、それらの共通の振舞いはEnumerableに
ごっそり分離されているため、RubyレベルではString < Arrayに
なったりもせず、あるいはStringがArrayに吸収されることもなく、
完全に関係ないクラスとしてそれぞれ存在しているわけですね。
で、ArrayとHashってのは振舞いが少々似ている以上の共通点はな
いわけです。つまり、統合する理由がない。Rubyの世界観において
Arrayのような機能とHashのような機能を両方提供することにした
場合に、「すべてがオブジェクト」という原則から考えてもクラス
を作らない方針はありえず、かといって上記のようにそれらを統合
するのはおかしいので、結局現状のようにそれぞれ別のクラスにな
るというのが一番自然であるべき姿のはずです。

まとめると違うものは違うものとしてきちんと違うクラスにするの
がRubyのクラス階層の設計のはずず。ArrayとHashが分かれてる意味
はArrayとHashが違うものだからでしょう。

[Tanaka Akira-3]

In article <46C9FA45.6090705@...>,
  Urabe Shyouhei <shyouhei@...> writes:

> おお、田中さんを満足させる説明ってのは結構ハードル高そうだな。

えぇ、納得できません。

> ええと、基本的にRubyのクラス階層というのは振舞いが似てるから
> という理由だけでサブクラスにしたり単一のクラスに統合したりは
> しないように分けられているはずです。なんでかというと振舞いは
> moduleとして取り出すことができるからです。たとえばStringと
> ArrayはCレベルではほとんど同じ(配列のなかみがcharかVALUEかく
> らいしか違わない)ですが、それらの共通の振舞いはEnumerableに
> ごっそり分離されているため、RubyレベルではString < Arrayに
> なったりもせず、あるいはStringがArrayに吸収されることもなく、
> 完全に関係ないクラスとしてそれぞれ存在しているわけですね。

module により、クラスを関連づける方向付けが弱くなっているの
はそうでしょう。

> で、ArrayとHashってのは振舞いが少々似ている以上の共通点はな
> いわけです。つまり、統合する理由がない。Rubyの世界観において

統合する理由がないからといって、統合しない理由があることには
ならないでしょう。

> Arrayのような機能とHashのような機能を両方提供することにした
> 場合に、「すべてがオブジェクト」という原則から考えてもクラス
> を作らない方針はありえず、かといって上記のようにそれらを統合
> するのはおかしいので、結局現状のようにそれぞれ別のクラスにな
> るというのが一番自然であるべき姿のはずです。

統合する理由がない、ということから統合するのがおかしいという
ことは導けません。統合する理由がないとしても、統合しない理由
もないかもしれないからです。

> まとめると違うものは違うものとしてきちんと違うクラスにするの
> がRubyのクラス階層の設計のはず。ArrayとHashが分かれてる意味
> はArrayとHashが違うものだからでしょう。

違うものを違うクラスにするのはもっともなことです。問題は、
Array と Hash がどう違うか、です。

「振舞いが少々似ている」とのことですが、似ている点ではなくて、
違う点・相容れない点について具体的に主張していただけないでしょ
うか。

ちなみに、私は、Ruby で Array と Hash がわかれているのは、
Perl がそうだったからだと憶測しています。
--
[田中 哲][たなか あきら][Tanaka Akira]

[しん]

# 出遅れたので、レスすべきメールが判らなくなってしまったので、手近なのに

Hash で順序を保存してくれると嬉しいことはあります。
もともと Key でソートされてるデータをHashに取りこんで
辞書というか変換テーブルと言うかにしておき、
書き出しもKeyでソートしてだしたい という事は良くあります。

hash.each_key.sort.each{|key| } とかしてますが、
hash.each{} でそれができればすっきりします。

困るのは Keyのsortが単純な比較ではないとき、
たとえば支社名を北の方からとか組織図の順にとか言う場合です。
出力順に並んだ 支社名のArray を用意するなど、本質ではないところで
苦労することに。

順序を保存してしまうと困ったことが起きるかどうかは考えていませんが
脊髄反射的には「順序を保証されていないで使ってるんだから、
今から生成順が保証されても困ることはなさそう。

                                                   出沢

[Yukihiro Matsumoto]

まつもと ゆきひろです

In message "Re: [ruby-list:43878] Re: Hashへの生成順は保障されないのか？"
    on Tue, 21 Aug 2007 07:35:43 +0900, しん <dezawa@...> writes:

|Hash で順序を保存してくれると嬉しいことはあります。

それは分かります。

実は私自身はHashの順序の保存については積極的に反対しているわ
けではないのです。しかし、

  * 一般的にはHashの順序が保存されない
  * どの順序が最適かは実は一意に決まらない(ような気がする)
  * 順序の保存によってHashの効率が下がるのはうれしくない

というような理由により手つかずです。