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

[しん]

これはまたすばやいレスを。

>   * どの順序が最適かは実は一意に決まらない(ような気がする)
うむ、、、、
この視点はなかったです。

>   * 順序の保存によってHashの効率が下がるのはうれしくない
はい、
私もそう思います。

「順序が保証されると嬉しいことはある」
という事例を示しはしてますが、して欲しいという強いおねがいが
あるわけではありません。
                                              出沢

[Masahiro Utsumi]

On 2007/08/21, at 0:35, しん wrote:

> # 出遅れたので、レスすべきメールが判らなくなってしまったので、
> 手近なのに
>
> Hash で順序を保存してくれると嬉しいことはあります。
> もともと Key でソートされてるデータをHashに取りこ
> んで
> 辞書というか変換テーブルと言うかにしておき、
> 書き出しもKeyでソートしてだしたい という事は良くあ
> ります。

私も順序を保存してもらえたらうれしいことはよくあります。
たとえばRailsなどでドロップダウンリストの要素を記述すると
きに
ITEMS = {
"jp" => '日本',
"us" => 'アメリカ',
"other" => 'その他'
}.freeze
を引数として渡すような用途です。

しかしながら、HASHはダイナミックに増えたり減ったり、伸びた
り縮んだり、
変わったりします。Hashの要素がHashだったりしますし、
内容がどんどん変化
しているものの順序を保持するのは実装するにあたりオーバーヘッドが
掛かりすぎるのではないでしょうか。順序が必要であれば配列の中に
Hashなり
配列をいれるととか、オーバラップクラスを作って実装する今のやり方で
なんとかやりくりできるのではないでしょうか。

もしオーバーヘッドがたいしたこと無ければ順序を保持してもらえたら
うれしいです。
.freezeした場合に限り順序が保証されるという制限付きでもありがた
いですね。

内海＠ベルギー

[pegacorn-2]

# どれにぶら下げるのが良いのかよくわからなくなってしまいましたが…

 From: Yukihiro Matsumoto <matz@...>
 Date: Tue, 21 Aug 2007 07:46:20 +0900
 Message-Id: <E1ING0v-0006do-JF@x31>
/~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> 実は私自身はHashの順序の保存については積極的に反対しているわ
> けではないのです。しかし、
>
>   * 一般的にはHashの順序が保存されない
>   * どの順序が最適かは実は一意に決まらない(ような気がする)
>   * 順序の保存によってHashの効率が下がるのはうれしくない
>
> というような理由により手つかずです。

インターフェイスとアルゴリズム（実装）の話が、ごっちゃになっている
ような気がします。

皆さんが共通して欲しがっているのは、Map とか Dictionary と
呼ばれている（？）ようなコンテナー（インターフェイス）では
ないでしょうか？

  例.
    foo[key] = value

で、
・順序
・検索速度
等は用途によって要求が異なると思います。

従って、現在の Hash に手を加えるのではなく、
用途によって要求が異なる部分を指定できる柔軟なコンテナークラスを
作るのが良いと思います。

# C++ の本ですけど、Modern C++ Design の「ポリシーを基にしたクラス・デザイン」
# が参考になると思います。


--
pegacorn

[Urabe Shyouhei-4]

Tanaka Akira wrote:
>> おお、田中さんを満足させる説明ってのは結構ハードル高そうだな。
>
> えぇ、納得できません。

うーん、やっぱりか。

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

そうですか?
ArrayとHashは別の名前がついている別のデータ構造ですね。それ
らの間に統合する理由が無いので、統合しないというだけだと思う
のですが。

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

統合する理由がなくて統合しない理由もないようなものは普通、統
合しない方に倒すと思います。違う例があれば教えてください。

> 違うものを違うクラスにするのはもっともなことです。問題は、
> Array と Hash がどう違うか、です。
>
> 「振舞いが少々似ている」とのことですが、似ている点ではなくて、
> 違う点・相容れない点について具体的に主張していただけないでしょ
> うか。

たとえばArrayのインスタンスaとHashのインスタンスhがあるとす
ると、

a[x] (x >= 0)

が存在すれば、少なくともa[0]からa[x]までのオブジェクトは存在
を仮定してよいはずです。ところがh[x]が存在してもそんな仮定は
おけない。この点は違いますよね。

あるいはたとえばeachのブロック引数がいまだとHashとArrayでは
異なっているわけですが、統合するとなるとどちらに合わせるべき
かは悩ましいところでしょう。each_with_indexはHash#eachとは挙
動が違うし。この点は明確に相容れないと言えます。

まあ、

> ちなみに、私は、Ruby で Array と Hash がわかれているのは、
> Perl がそうだったからだと憶測しています。

この理由はかなりありそうですよね。そこはほんのりと同意。

[Urabe Shyouhei-4]

Masahiro Utsumi wrote:
> もしオーバーヘッドがたいしたこと無ければ順序を保持してもらえたらうれしい
> です。
> .freezeした場合に限り順序が保証されるという制限付きでもありがたいですね。

たとえばキーのオブジェクト同士がComparableという制
約をつければ、B木クラスを作成することで望みのものが
得られるでしょう。
O(1)がO(log(n))になるオーバーヘッドのことを「たいし
たこと無い」と表現する場合は、ですが。

# でもB木を実装したクラスにHashという名前を付けるの
# は絶対違う

[tachibana]

pegacorn さんは書きました:

> 皆さんが共通して欲しがっているのは、Map とか Dictionary と
> 呼ばれている（？）ようなコンテナー（インターフェイス）では
> ないでしょうか？

「Hash的なアクセス」というインターフェースの総称としては
"Map"あたりが最適かなぁと私は思ったりします。
今話題になっているヤツは"ArrayMap"とか"OrderedMap"とか呼びたいですね。

標準で入ってない色んなデータ構造を一括してぶち込んだライブラリが
デファクトスタンダードとして存在してれば、
「ああ、その目的ならHashじゃなくてOrderdMapが最適だね。
　このライブラリが有名だからインストールして使うと良い。
　あと、Hashやデータ構造一般については
　もーちょい知っておいた方がいいと思うよ」
であっさり済んでいたような気も。
Javaで言うjakartaのcommons-langのノリで。

# なにげに初投稿だったりで、よろしくお願いします。
# 普段はJava屋でして、Rubyの精神や前提の知識などを
# 解さぬ発言をしでかしてしまいましたら申し訳ありません……。

/++
 + @from tachibana (deadzone@...)
 +/

[Kazuhiro NISHIYAMA]

西山和広です。

At Tue, 21 Aug 2007 08:14:22 +0900,
Masahiro Utsumi wrote:

>
> 私も順序を保存してもらえたらうれしいことはよくあります。
> たとえばRailsなどでドロップダウンリストの要素を記述すると きに
> ITEMS = {
> "jp" => '日本',
> "us" => 'アメリカ',
> "other" => 'その他'
> }.freeze
> を引数として渡すような用途です。
>
> しかしながら、HASHはダイナミックに増えたり減ったり、伸びた り縮んだり、
> 変わったりします。Hashの要素がHashだったりしますし、 内容がどんどん変化
> しているものの順序を保持するのは実装するにあたりオーバーヘッドが
> 掛かりすぎるのではないでしょうか。順序が必要であれば配列の中に Hashなり
> 配列をいれるとか、オーバラップクラスを作って実装する今のやり方で
> なんとかやりくりできるのではないでしょうか。

Railsなら ActiveSupport::OrderedHash を使うのはどうでしょうか?


--
|ZnZ(ゼット エヌ ゼット)
|西山和広(Kazuhiro NISHIYAMA)

[Nobuyoshi Nakada-2]

なかだです。

At Tue, 21 Aug 2007 07:46:20 +0900,
Yukihiro Matsumoto wrote in [ruby-list:43879]:
> 実は私自身はHashの順序の保存については積極的に反対しているわ
> けではないのです。しかし、
>
>   * 一般的にはHashの順序が保存されない
>   * どの順序が最適かは実は一意に決まらない(ような気がする)

「どの順序」と選べるほど選択肢はないような気がするのですが。

>   * 順序の保存によってHashの効率が下がるのはうれしくない

[ruby-dev:24569]を1.9最新用に直して、Hal Fultonから送られてきた
ベンチマークを試してみました。

http://www.rubyist.net/~nobu/ruby/ordered-hash-1.9.diff
http://www.rubyist.net/~nobu/ruby/ordered-hash-1.8.diff

予想通りdeleteがやや遅くなっていますが、思ったほどの影響はないよ
うです。逆にeachやsort_byが速くなっているのは、二重配列から単純
なdouble linked listをたどるようになっているのが大きいのかもしれ
ません。

前
add to empty hash                         0.650000   0.010000   0.660000 (  0.654691)
add to hash with 100000 elements          0.710000   0.020000   0.730000 (  0.730761)
each_key with 200000 elements             0.050000   0.000000   0.050000 (  0.053228)
keys.sort_by.each, 200000 elements        1.150000   0.000000   1.150000 (  1.159369)
delete 100000 times, non-existing key     0.040000   0.000000   0.040000 (  0.034815)
delete 100000 times, existing keys        0.260000   0.000000   0.260000 (  0.256023)
include? 100000 times, non-existing key   0.050000   0.000000   0.050000 (  0.046105)
include? 100000 times, existing keys      0.230000   0.000000   0.230000 (  0.225641)
clear hash with 100000 elements           0.030000   0.000000   0.030000 (  0.037633)

後
                                              user     system      total        real
add to empty hash                         0.550000   0.020000   0.570000 (  0.558828)
add to hash with 100000 elements          0.620000   0.010000   0.630000 (  0.636749)
each_key with 200000 elements             0.040000   0.000000   0.040000 (  0.043783)
keys.sort_by.each, 200000 elements        0.270000   0.010000   0.280000 (  0.276364)
delete 100000 times, non-existing key     0.030000   0.000000   0.030000 (  0.035522)
delete 100000 times, existing keys        0.270000   0.000000   0.270000 (  0.265942)
include? 100000 times, non-existing key   0.030000   0.000000   0.030000 (  0.028704)
include? 100000 times, existing keys      0.190000   0.000000   0.190000 (  0.193877)
clear hash with 100000 elements           0.040000   0.000000   0.040000 (  0.035513)

---

# Hash benchmarking suite
# by Ryan Leavengood

require 'benchmark'

class SymbolGen
  def initialize(value='aaaaaaaa')
    @value = value
  end

  def generate
    result = @value.intern
    @value = @value.succ
    result
  end
end

if $0 == __FILE__
  sg = SymbolGen.new
  h = {}
  iterations = 100000
  Benchmark.bm(40) do |bx|
    block = proc { h[sg.generate] = sg.generate }
    bx.report("add to empty hash") { iterations.times &block }
    bx.report("add to hash with #{iterations} elements") { iterations.times &block }
    bx.report("each_key with #{2*iterations} elements") { h.each_key {|key|} }
    bx.report("keys.sort_by.each, #{2*iterations} elements") { h.keys.sort_by{|k| k.to_s}.each {|key|} }
    bx.report("delete #{iterations} times, non-existing key") { iterations.times { h.delete(:not_a_key) } }
    sg2 = SymbolGen.new
    bx.report("delete #{iterations} times, existing keys") { iterations.times { h.delete(sg2.generate); sg2.generate } }
    bx.report("include? #{iterations} times, non-existing key") { iterations.times { h.include?(:not_a_key) } }
    bx.report("include? #{iterations} times, existing keys") { iterations.times { h.include?(sg2.generate); sg2.generate } }
    bx.report("clear hash with #{iterations} elements") { h.clear }
  end
end

---

--
--- 僕の前にBugはない。
--- 僕の後ろにBugはできる。
    中田 伸悦

[pegacorn-2]

 From: Nobuyoshi Nakada <nobu@...>
 Date: Tue, 21 Aug 2007 10:43:25 +0900
 Message-Id: <20070821014331.6640AE02CB@...>
/~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> >   * どの順序が最適かは実は一意に決まらない(ような気がする)
>
> 「どの順序」と選べるほど選択肢はないような気がするのですが。

大きく分けてもこれくらいはあるかと。
・登録順
・特定順（昇順等）
・ランダム（っぽいのも含めて）


--
pegacorn

[Nobuyoshi Nakada-2]

なかだです。

At Tue, 21 Aug 2007 11:17:45 +0900,
pegacorn wrote in [ruby-list:43888]:
> > >   * どの順序が最適かは実は一意に決まらない(ような気がする)
> >
> > 「どの順序」と選べるほど選択肢はないような気がするのですが。
>
> 大きく分けてもこれくらいはあるかと。
> ・登録順

[ruby-dev:24569]はこれですね。

> ・特定順（昇順等）

Hashはkeyを限定しないので、定義できないのではないかと思います。
たとえば {'one'=>1, 1.0=>1} はどういう順序になるんでしょうか。

> ・ランダム（っぽいのも含めて）

  ・ hash値順(num_binsでmodとってますが)

--
--- 僕の前にBugはない。
--- 僕の後ろにBugはできる。
    中田 伸悦

[pegacorn-2]

 From: Nobuyoshi Nakada <nobu@...>
 Date: Tue, 21 Aug 2007 11:27:16 +0900
 Message-Id: <20070821022722.A2F7EE02D3@...>
/~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> > ・特定順（昇順等）
>
> Hashはkeyを限定しないので、定義できないのではないかと思います。
> たとえば {'one'=>1, 1.0=>1} はどういう順序になるんでしょうか。

ソートの基準を定義するオブジェクトを指定させれば、
どういう順序にでもできると思います。
# C++ の std::map の 3 番目のテンプレート引数をイメージしました。


--
pegacorn

[SASADA Koichi]

　ささだです。

Nobuyoshi Nakada wrote:
>>   * 順序の保存によってHashの効率が下がるのはうれしくない
>
> [ruby-dev:24569]を1.9最新用に直して、Hal Fultonから送られてきた
> ベンチマークを試してみました。

　私は順序を保存する実行時間オーバヘッドを嫌っていたのですが、この結
果を見ると速いですね。というか、ハッシュ全体をなめる処理が速くなるの
は道理ですねぇ。追加が遅くなるのでは、と心配していたんですが、ほとん
ど変わってないし。というか、速くなってるし（ただ、この評価だけだとあ
れなので、こっちでも追試してみます）。

　利用メモリは 5/3 倍になるので、9MB（1M要素で）消費していたのが
15MB ですか。まぁ、Ruby 的にはメモリ食いはあんまり気にしないんで、い
れちゃってもいいんじゃないでしょうか。

--
// SASADA Koichi at atdot dot net

[Yukihiro Matsumoto]

まつもと ゆきひろです

瓢箪から駒。

In message "Re: [ruby-list:43891] Re: Hashへの生成順は保障されないのか？"
    on Tue, 21 Aug 2007 13:09:36 +0900, SASADA Koichi <ko1@...> writes:

|　利用メモリは 5/3 倍になるので、9MB（1M要素で）消費していたのが
|15MB ですか。まぁ、Ruby 的にはメモリ食いはあんまり気にしないんで、い
|れちゃってもいいんじゃないでしょうか。

とりあえず入れてみましょうか。なかださん、お願いしてもよい？

[Nobuyoshi Nakada-2]

なかだです。

At Tue, 21 Aug 2007 13:21:21 +0900,
Yukihiro Matsumoto wrote in [ruby-list:43892]:
> |　利用メモリは 5/3 倍になるので、9MB（1M要素で）消費していたのが
> |15MB ですか。まぁ、Ruby 的にはメモリ食いはあんまり気にしないんで、い
> |れちゃってもいいんじゃないでしょうか。
>
> とりあえず入れてみましょうか。なかださん、お願いしてもよい？

1.9には入れました。1.8は今のままで?

あと、st_reverse_foreach()というのも追加してあるんですが、
Hash#reverse_eachはいりませんか?

--
--- 僕の前にBugはない。
--- 僕の後ろにBugはできる。
    中田 伸悦

[SASADA Koichi]

　ささだです。

Yukihiro Matsumoto wrote:
> とりあえず入れてみましょうか。なかださん、お願いしてもよい？

　勢いで入ってしまったんですが、「今後、Ruby では Hash は生成順に
iterate する」というのを仕様として定めてしまってもいいのか、ちょっと
不安になっています。

　未定義だけど、たまたま実装がこうなっているのか、それとも Ruby は今
後生成順を保存するんですよ、というのか。

　どうしたもんでしょうか。


　ちなみに、reorder_by{} なんてメソッドもあっていいと思うんですが、
新しいエントリが追加されたら無視するしかないなぁ、と思う。

--
// SASADA Koichi at atdot dot net

[Yukihiro Matsumoto]

まつもと ゆきひろです

In message "Re: [ruby-list:43893] Re: Hashへの生成順は保障されないのか？"
    on Tue, 21 Aug 2007 13:59:43 +0900, Nobuyoshi Nakada <nobu@...> writes:

|> とりあえず入れてみましょうか。なかださん、お願いしてもよい？
|
|1.9には入れました。1.8は今のままで?

1.8には入れない方向で。

|あと、st_reverse_foreach()というのも追加してあるんですが、
|Hash#reverse_eachはいりませんか?

不要だと思います。

[Yukihiro Matsumoto]

まつもと ゆきひろです

In message "Re: [ruby-list:43894] Re: Hashへの生成順は保障されないのか？"
    on Tue, 21 Aug 2007 14:13:45 +0900, SASADA Koichi <ko1@...> writes:

|　勢いで入ってしまったんですが、「今後、Ruby では Hash は生成順に
|iterate する」というのを仕様として定めてしまってもいいのか、ちょっと
|不安になっています。
|
|　未定義だけど、たまたま実装がこうなっているのか、それとも Ruby は今
|後生成順を保存するんですよ、というのか。
|
|　どうしたもんでしょうか。

当面は前者「未定義だけど、たまたま実装がこうなっている」で通
しましょう。同じ理由でreverse_eachは導入しません。

|　ちなみに、reorder_by{} なんてメソッドもあっていいと思うんですが、
|新しいエントリが追加されたら無視するしかないなぁ、と思う。

reorder_by{}ってなにするの？ ブロック値でエントリをソートす
る？ うーむ。

[SASADA Koichi]

　ささだです。

Yukihiro Matsumoto wrote:
> reorder_by{}ってなにするの？ ブロック値でエントリをソートす
> る？ うーむ。

　そうそう。で、新しいエントリが加わったら、その順番は無視して後ろに
くっつけるだけ、というつもりでした。

　一般化を考えると order を決める Proc を登録して云々、になるんで
しょうか。marshal できなくなるので嫌だ、と言ってる人もいましたが、ど
んなもんですかね。

--
// SASADA Koichi at atdot dot net

普段はROMで忘れた頃に書き込んでる村山です．

>ソートの基準を定義するオブジェクトを指定させれば、
>どういう順序にでもできると思います。
># C++ の std::map の 3 番目のテンプレート引数をイメージしました。

順序づけは可能ですが，意味のない順序付けとなる場合もあると思います．
＃ダックタイピング的には許容範囲かもしれませんけど．

例えば「都道府県を(北の方から)順番に並べる」場合なども結構厄介ですよ．

>　一般化を考えると order を決める Proc を登録して云々、になるんで
> しょうか。marshal できなくなるので嫌だ、と言ってる人もいましたが、ど
> んなもんですかね。

Java屋の視点でいえば，
- Comparableインターフェースを実装して，そのオブジェクト自身に比較させる．
- 順序付けをさせる Comparatorオブジェクトを作る．
のいずれかですね．Comparableはそのオブジェクト自身が自然な順序付けで比較可能である
ことを表します．しかし比較可能でない，例えば値を表すオブジェクトなど以外では，
複数の順序付けが定義可能ということもあって，あまり推奨されていません．

なお一般的にはequalsメソッド(同値性比較メソッド．Rubyだと"=="でしたっけ？)との
一貫性が求められます．
http://java.sun.com/j2se/1.5.0/ja/docs/ja/api/java/lang/Comparable.html
http://java.sun.com/j2se/1.5.0/ja/docs/ja/api/java/util/Comparator.html

同じにする必要はないと思いますが参考までに．


ついでに言うとJavaでは
・順序を保存しないHash
・順序を保存する機能付きHash
は別々の物として実装するでしょうね．Hashはあくまでハッシュ表．
ハッシュ表と異なる物には異なる名前の異なるクラスを用意すると思います．
http://java.sun.com/j2se/1.5.0/ja/docs/ja/api/java/util/SortedMap.html

そうしないと計算量のオーダーとかが変わっちゃうし，順序付きにする分には問題なくても，
一度「順序付き」と定義してあとから「やっぱしやめた」とするとバージョン間の互換性問題に
発展するので商用のWeb系システムなどでは特に嫌われます．

--
I am locutus of Gmail. Resistance is FUTILE!! <locutus1701e@...>

[Akinori MUSHA]

At Tue, 21 Aug 2007 13:59:43 +0900,
Nobuyoshi Nakada wrote:

> なかだです。
>
> At Tue, 21 Aug 2007 13:21:21 +0900,
> Yukihiro Matsumoto wrote in [ruby-list:43892]:
> > |　利用メモリは 5/3 倍になるので、9MB（1M要素で）消費していたのが
> > |15MB ですか。まぁ、Ruby 的にはメモリ食いはあんまり気にしないんで、い
> > |れちゃってもいいんじゃないでしょうか。
> >
> > とりあえず入れてみましょうか。なかださん、お願いしてもよい？
>
> 1.9には入れました。1.8は今のままで?

　1.8 には入れないでください。

　1.9 においても、 Hash という名前のクラスで順序を保証することには
反対です。別クラスにするか、せめて生成時オプションにしてほしい。


　Set のサブクラス SortedSet は、(利用可能なときは) Hash に替えて
RBTree を使うことで実現しています。RBTree はそのアルゴリズム自体が
要素間の全順序関係に依拠しているため、適切であると考えました。

cf. http://raa.ruby-lang.org/project/ruby-rbtree

--
                     /
                    /__  __            Akinori.org / MUSHA.org
                   / )  )  ) )  /     FreeBSD.org / Ruby-lang.org
Akinori MUSHA aka / (_ /  ( (__(  @ iDaemons.org / and.or.jp

"Different eyes see different things,
    Different hearts beat on different strings --
       But there are times for you and me when all such things agree"