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

[Nobuyoshi Nakada-2]

なかだです。

At Wed, 22 Aug 2007 08:32:56 +0900,
GOTO Kentaro wrote in [ruby-list:43919]:

> > > * 格納された順序を覚えられる
> > > * keys.sort_by(&ord).each do |k| ... end の ord 相当を指定できる
> > > という二通りを必要とすることが多いんですが、両方サポートしているんでしょうか。
> >
> > 前者のみです。
>
> なるほど。
> 大クラス主義的にはずいぶんと貧弱な気がしました。
> でもまあ、例外を起こさないように任意の順序を指定するのは
> 手軽ではなかったりもしますね。

というか、今回の変更はst.cに対するものなので、直接rubyレベルの機
能を追加することはかなり面倒になります。

それに、任意の順序を指定したければ追加は簡単なので。

  class Hash
    def order(&b)
      sort(&b).inject(self.class.new) {|h, (k, v)| h[k] = v; h}
    end
    def order_by(&b)
      sort_by(&b).inject(self.class.new) {|h, (k, v)| h[k] = v; h}
    end
  end

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

[Tanaka Akira-3]

In article <86sl6dgikh.knu@...>,
  "Akinori MUSHA" <knu@...> writes:

>  1. 名実一致
>     Hash というその名称から、順序性を期待させるべきでない。
>     (この時点で大義がない)

これはありうる理由だと思います。
ただ、同時に、ときに名前と中身がずれることがあるのも事実だと
思います。

>  3. 互換性
>     記法が変わらないため、コード断片を見ただけでは順序性を期待
>     しているのかどうか読み取れなくなる。これは他の言語や古い
>     バージョンのRubyへの移植の妨げになる。

Ruby のバージョンについては過渡的な話でしょう。

他の言語については、PHP から Ruby への移植で困ったとかいう話
が今までに多かったでしょうか。

>     また、 shim (compatibility layer)を実装しようにも、大幅な
>     性能劣化を伴わずに実現できるか疑わしい。

必要なら 1.9 から backport すればいいでしょう。

>  2. 性能
>     メモリ使用量増加や速度低下をもたらし、今後の最適化の余地も
>     制限する。

どう最適化するか、想定していることはありますか?

速度低下は測定結果を見る限りあまり気にならないように思えます。

ただ、メモリ使用量増加はリアルな問題になり得ると思います。

もちろん、メモリ全体に対する st の割合が問題になるので、まず
は測定してみないことには、ということで測定してみました。

とりあえず測定対象は以下のものです。

* sample/test.rb
* test/runner.rb
* rm -rf .ext/rdoc して ./bin/rdoc --all --ri --op .ext/rdoc .

これらを valgrind の massif ではかってみました。
(massif は heap profiler です。いきなり ps で図が出ます。)

r13123 と r13128 で ruby を作って、

valgrind --tool=massif --format=html \
--alloc-fn=ruby_xmalloc --alloc-fn=ruby_xrealloc \
--alloc-fn=ruby_xrealloc2 --alloc-fn=ruby_xmalloc2 \
--alloc-fn=ruby_xcalloc \
./ruby ./bin/rdoc --all --ri --op .ext/rdoc .

などとして生成されたものを
http://cvs.m17n.org/~akr/diary/2007-08/
においておきました。
(test-all は runner.rb を実行したプロセスのものだけです。)

いきなりすごくでかくなる程って程じゃないですが、見てわかる影
響はあります。見比べると、st 関係が一番膨らんでるのは rdoc
ですかね。

とりあえず内部的に使ってる st で、順序が不要なことがわかって
いるものにまで順序を付けるのは避けたほうがいいんじゃないかと
感じます。シンボルのやつとか。
--
[田中 哲][たなか あきら][Tanaka Akira]

[Tetsuo Sakaguchi]

阪口です。

In message <20070821141439.GA92126%saka@...> 2007-08-21T23:14+0900,
        Tetsuo Sakaguchi <saka@...> wrote:
> PS. 時間がとれれば環境整えて自分でパッチを当ててみようかとも思いますが、、。

ちょっとためしたけど、単純に(ordered-hash抜きでは)適用できないので、

> このパッチ、rehashのメモリの割り当てが Calloc(=calloc) から、
> xrealloc に変更されていますね。

単純に Calloc -> xmalloc にしてみたもので、ベンチマークしてみました。
(diff は添付しておきます。エイやっと作ったので、ミスがあるかも。。)

見ればわかる通り、当たり前ですが全体として性能がそこそこ上がっています。
(clear が落ちているように見えるけど、この値だと測定誤差とか他負荷の
要因は無視できないし。。。もうちょっと長時間で計らないと。。)

ご参考まで。

個人的には、組み込みクラスは基本的な機能に絞っておいて、派生的な
機能を持たせる場合でも、速度や記憶使用量の増加はせいぜい数%程度までの
ものにしておいて欲しいと思いますが、、。
(awk の連想配列でも要素の追加順序は保存されませんし、、、。)


1.8.6-p36 のまま
                                              user     system      total        real
add to empty hash                         1.150000   0.020000   1.170000 (  1.177728)
add to hash with 100000 elements          1.950000   0.030000   1.980000 (  1.978130)
each_key with 200000 elements             0.100000   0.000000   0.100000 (  0.099460)
keys.sort_by.each, 200000 elements        2.350000   0.030000   2.380000 (  2.373399)
delete 100000 times, non-existing key     0.060000   0.000000   0.060000 (  0.062486)
delete 100000 times, existing keys        0.490000   0.000000   0.490000 (  0.487005)
include? 100000 times, non-existing key   0.060000   0.000000   0.060000 (  0.054519)
include? 100000 times, existing keys      0.400000   0.000000   0.400000 (  0.401355)
clear hash with 100000 elements           0.020000   0.000000   0.020000 (  0.022875)

rehash で、Calloc -> xmalloc したもの
                                              user     system      total        real
add to empty hash                         0.960000   0.010000   0.970000 (  0.978789)
add to hash with 100000 elements          1.680000   0.020000   1.700000 (  1.692938)
each_key with 200000 elements             0.080000   0.000000   0.080000 (  0.085035)
keys.sort_by.each, 200000 elements        1.610000   0.020000   1.630000 (  1.629927)
delete 100000 times, non-existing key     0.050000   0.000000   0.050000 (  0.047612)
delete 100000 times, existing keys        0.320000   0.000000   0.320000 (  0.326661)
include? 100000 times, non-existing key   0.040000   0.000000   0.040000 (  0.043253)
include? 100000 times, existing keys      0.380000   0.010000   0.390000 (  0.373585)
clear hash with 100000 elements           0.040000   0.000000   0.040000 (  0.047428)

--
阪口哲男＠図書館情報メディア研究科．大学院．筑波大学
Tetsuo SAKAGUCHI.
Graduate School of Library, Information and Media Studies
University of Tsukuba, JAPAN.

--- ruby-1.8.6-p36-org/st.c 2007-02-13 08:01:19.000000000 +0900
+++ ruby-1.8.6-p36/st.c 2007-08-22 20:41:40.984776000 +0900
@@ -321,7 +321,9 @@
     unsigned int hash_val;
 
     new_num_bins = new_size(old_num_bins+1);
-    new_bins = (st_table_entry**)Calloc(new_num_bins, sizeof(st_table_entry*));
+    new_bins = (st_table_entry**)
+    xmalloc(new_num_bins * sizeof(st_table_entry*));
+    for (i = 0; i < new_num_bins; i++) new_bins[i] = 0;
 
     for(i = 0; i < old_num_bins; i++) {
  ptr = table->bins[i];

[Yoshiyuki Uehara]

植原といいます。

# いまさらですが…

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

Java ではインターフェースとして

  Map: キー、値のペアを保持する
  SortedMap: キーがソートされた Map

の２つがありますが、実装には下記の３つがあります。

  HashMap: Mapの実装。キーの順序を保証しない。
  TreeMap: SortedMapの実装。キーがソートされている。
  LinkedHashMap: Mapの実装(HashMapのサブクラス)。
                 予測可能な繰り返し順序(キーの追加順)を持つ。

http://www.hellohiro.com/map.htm
http://sdc.sun.co.jp/java/docs/j2se/1.4/ja/docs/ja/api/java/util/LinkedHashMap.html

個人的には Java の開発で LinkedHashMap を使用することは結構あります。
# テストケースの expected 記述や、Web アプリで select の元データなど。

[ujihisa]

氏久といいます。

既に少し議論に挙げられていましたが…
Hashという名前から明らかに順序を期待しなくなりますが
それでも順序を期待するときにHashを使いたくなることがあるのは
Hashには専用のリテラルがあるからでしょう。
配列、シンボル、正規表現、Rangeなども同様です。

[:a => 1, :b => 2]をOrderedHashにすると、[{:a => 1, :b => 2}]かどうかの
互換性の問題があるので、ここは正規表現を見習って

{:a => 1, :b => 2}o

のように末尾になにか付けるというのはどうでしょうか。


# 個人的には、Setは{:a, :b, :c, :d}のように
# 書けるようになって欲しいと思ってる人

[Tanaka Akira-3]

In article <87zm0kaz60.fsf@...>,
  Tanaka Akira <akr@...> writes:

> いきなりすごくでかくなる程って程じゃないですが、見てわかる影
> 響はあります。見比べると、st 関係が一番膨らんでるのは rdoc
> ですかね。

もうちょっと測った結果、どうもインスタンス変数を表現する
st (iv_tbl) が膨らんでるのが原因のようです。

インスタンス変数の順序を覚えてほしいと思う人は、まぁ、個人的
には pp と inspect でその順序を使いたいという気はしますが、
st_table_entry のフィールドをふたつ増やしてまでしたいかとい
うと、それほどには思いません。

とすると、st ぜんぶを順序つきにするのはさすがにやりすぎで、
やるにしても両方提供して、少なくとも iv_tbl は順序なしにする
のが順当のように思います。そうすれば、rdoc のケースでは、メ
モり消費はたいして増えないようになる感じがします。
(測った結果、インスタンス変数以外では Hash は出てこなくて、
むしろ Range が出てきたので、Hash は支配的でないように思う)

もちろん、rdoc のケースでそうだったからといってすべてのケー
スで問題ないとは限らないわけで、Hash をたくさんたくさんつか
うケースでは問題になるでしょう。

というわけで、Hash::Ordered とかとして別に作るのがいいんじゃ
ないですかね。

そして、リテラルの {} を Hash::Ordered にするとかどうですか
ね。{} にはどこにも hash という単語が出てきませんし、記法と
しても順序がありますし。まぁ、1次元の文字列でプログラムを書
く以上、順序の無い記法というのはまずありえないわけですが...
--
[田中 哲][たなか あきら][Tanaka Akira]

[Yugui-2]

Yuguiといいます。

07/08/23 に Tanaka Akira<akr@...> さんは書きました:
> In article <87zm0kaz60.fsf@...>,
> というわけで、Hash::Ordered とかとして別に作るのがいいんじゃ
> ないですかね。
>
> そして、リテラルの {} を Hash::Ordered にするとかどうですか
> ね。{} にはどこにも hash という単語が出てきませんし、記法と
> しても順序がありますし。まぁ、1次元の文字列でプログラムを書
> く以上、順序の無い記法というのはまずありえないわけですが...

同意です。
 * Hashという名前である以上は順序は期待できないのが自然だと思います
 * 順序を保たないで効率を重視したい場合の選択肢を残して欲しいです。
 * リテラルには順序があるように見えるという意見には一理あります。
 * リテラル表記を用いる大部分のケースにおいて、順序を保つコストは
   許容できると思います。

なので
 * Hashクラスは現状維持
 * Hash::Orderedを新設
 * 従来ハッシュリテラルと呼ばれていた表記はHash::Orderedのリテラルに。
 * Hash[:a => 1, :b => 2]のような表記でHashのインスタンスを生成できればばよい。

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

[Shin'ya Adzumi]

あづみです。

Yugui さんは書きました:
>  * 従来ハッシュリテラルと呼ばれていた表記はHash::Orderedのリテラルに。

ふと、今手元のＰＣに入っている ruby1.8.6 を見てみたら

  yaml/baseemitter.rb:                    @seq_map = true if v.class == Hash

というのがありますね。
こういう書き方してるスクリプトはちょっとマズいかも。

# ざっと見た限り、あんまり多くはなさそうだけど


安積伸弥
adzumi@...

[Shugo Maeda]

前田です。

On 08/23/2007 01:42 PM, Tanaka Akira wrote:
> というわけで、Hash::Ordered とかとして別に作るのがいいんじゃ
> ないですかね。
>
> そして、リテラルの {} を Hash::Ordered にするとかどうですか
> ね。{} にはどこにも hash という単語が出てきませんし、記法と
> しても順序がありますし。まぁ、1次元の文字列でプログラムを書
> く以上、順序の無い記法というのはまずありえないわけですが...

空のHashを作る時にHash.newの代りに{}を使っているコードが多い
ので、かなりの部分は実際にはHash::Orderedが使われることになる
のではないでしょうか。

excelsior:ruby-trunk$ fgrep '= {}' lib/**/*.rb|wc -l
377
excelsior:ruby-trunk$ fgrep '= Hash.new' lib/**/*.rb|wc -l
40

極端にHashをよく使うプログラム以外でメモリ効率がそれほど悪く
なければ、Hashそのものに順序を付けてしまう方がすっきりしてい
てよいと思います。
# 効率上の問題が大きければ、組み込みの順序付Hashはあきらめる
# ということで。
また、互換性に関しては、1.8→1.9で互換性が保たれていれば、そ
れほど大きな問題ではないのではないでしょうか。

On 08/24/2007 03:04 PM, Yugui wrote:
>  * Hashという名前である以上は順序は期待できないのが自然だと思います

一般的にHashに順序を期待すべきでないというのはその通りだと思
うのですが、だからといってRubyのHashに順序があってはいけない
ということはないと思います。
それにArrayにもいろんなコレクション(queue/stackなど)の機能が
詰め込まれてますよね。

--
前田 修吾

[Yukihiro Matsumoto]

まつもと ゆきひろです

In message "Re: [ruby-list:43927] Re: Hashへの生成順は保障されないのか？"
    on Fri, 24 Aug 2007 15:04:52 +0900, Yugui <yugui@...> writes:

|> そして、リテラルの {} を Hash::Ordered にするとかどうですか
|> ね。{} にはどこにも hash という単語が出てきませんし、記法と
|> しても順序がありますし。まぁ、1次元の文字列でプログラムを書
|> く以上、順序の無い記法というのはまずありえないわけですが...
|
|同意です。
| * Hashという名前である以上は順序は期待できないのが自然だと思います
| * 順序を保たないで効率を重視したい場合の選択肢を残して欲しいです。
| * リテラルには順序があるように見えるという意見には一理あります。
| * リテラル表記を用いる大部分のケースにおいて、順序を保つコストは
|   許容できると思います。
|
|なので
| * Hashクラスは現状維持
| * Hash::Orderedを新設
| * 従来ハッシュリテラルと呼ばれていた表記はHash::Orderedのリテラルに。
| * Hash[:a => 1, :b => 2]のような表記でHashのインスタンスを生成できればよい。

同意しません。

  * 全く同じ機能で性質だけ異なるクラスを複数用意するのは大ク
    ラス主義を標榜するRuby的でない

  * Hashという名前はHashアルゴリズムを使っていることしか意味
    しない。keyの登場順序があるかどうかはスコープ外。ただし、
    Rubyで順序があると他の言語で「順序はないのか」と騒ぐ人が
    居たりして、教育的問題が発生する可能性は否定しない。

  * 時間効率には順序を保たないかどうかは関係ない。

  * 空間効率にはある程度関係があるが、ちゃんとベンチマークを
    取ってみないとなにも言えない。それでも、どれだけ重大かは
    ケースバイケースだと思うけど。

  * とはいえ、インスタンス変数やシンボルテーブルにまで順序を
    保証するのはやりすぎなので、それはやめる方向で。

と考えています。ですから、将来ありえる組み合わせは

  * 1.8のまま、順序は導入しない
  * Hashに順順序を導入する(ただし、インスタンス変数やシンボルテー
    ブルなどにはない)

のいずれかではないかと。気持ち的には後者に傾いています。

                                まつもと ゆきひろ /:|)

[Tanaka Akira-3]

In article <46CE97C8.4090807@...>,
  Shugo Maeda <shugo@...> writes:

> 極端にHashをよく使うプログラム以外でメモリ効率がそれほど悪く
> なければ、Hashそのものに順序を付けてしまう方がすっきりしてい
> てよいと思います。

まぁ、それもいいんじゃないですか。

> # 効率上の問題が大きければ、組み込みの順序付Hashはあきらめる
> # ということで。

「極端にHashをよく使うプログラム」がどのくらいあるかですかねぇ。
具体的にはなにがあるのだろう?

ただ、見つかったとして、それを測定するにはまずインスタンス変
数などには順序がなくて、Hash には順序がある、という Ruby が
必要になりますが。
--
[田中 哲][たなか あきら][Tanaka Akira]

[Yukihiro Matsumoto]

まつもと ゆきひろです

In message "Re: [ruby-list:43931] Re: Hashへの生成順は保障されないのか？"
    on Fri, 24 Aug 2007 18:52:55 +0900, Tanaka Akira <akr@...> writes:

|「極端にHashをよく使うプログラム」がどのくらいあるかですかねぇ。
|具体的にはなにがあるのだろう?

occur.rb? かなり人工的ですね。

|ただ、見つかったとして、それを測定するにはまずインスタンス変
|数などには順序がなくて、Hash には順序がある、という Ruby が
|必要になりますが。

(やる気になれば)なかださんが近いうちに作ってくださるのではな
いかと。

[NISHI Takao]

にし＠おかやまです。

At Fri, 24 Aug 2007 18:52:55 +0900,
Tanaka Akira wrote:
> 「極端にHashをよく使うプログラム」がどのくらいあるかですかねぇ。
> 具体的にはなにがあるのだろう?

「よくつかう」ってのに該当するかどうかは不明ですが，REXMLではタグの属
性を保存するのにHashのサブクラスを使ってます。

大きなXML文書を食わせるとHashが大量に生成されることになるので，ボディ
ブローのように効いてきそう。

--
NISHI Takao   D add ninth Co.,Ltd.  http://www.Dadd9.com/
   1-2-24 Toyonari, Okayama, 700-0942, Japan               @@@@
   Phone:[phone]  Facsimile:[phone]        OO/
   PGP:1466 BB16 3186 CC11 1A06 713C 5518 3A2A A122 118A  -|/

[Fujimoto Hisa]

藤本です。

立場は、Hashリテラルの左から順が保証されるとうれしい派です。

# RubyCocoaでObjective-Cのメッセージ送信に使える

リテラルでの左から順の保証が実現するなら、それがどんなふうに実装される
かにはあまりこだわりはありません。なので「リテラルの実体＝順序を保障す
る改良Hash」でも十分にありがたいのですが、さらに、現在のHashリテラルと
プログラミング上の互換性が維持されていれば、リテラルの実体はHashでなく
てもいいと思っています。

On 8/24/07, Yukihiro Matsumoto <matz@...> wrote:

> In message "Re: [ruby-list:43927] Re: Hashへの生成順は保障されないのか？"
>     on Fri, 24 Aug 2007 15:04:52 +0900, Yugui <yugui@...> writes:
>
> |> そして、リテラルの {} を Hash::Ordered にするとかどうですか
> |> ね。{} にはどこにも hash という単語が出てきませんし、記法と
> |> しても順序がありますし。まぁ、1次元の文字列でプログラムを書
> |> く以上、順序の無い記法というのはまずありえないわけですが...
> |
> |同意です。
> | * Hashという名前である以上は順序は期待できないのが自然だと思います
> | * 順序を保たないで効率を重視したい場合の選択肢を残して欲しいです。
> | * リテラルには順序があるように見えるという意見には一理あります。
> | * リテラル表記を用いる大部分のケースにおいて、順序を保つコストは
> |   許容できると思います。
> |
> |なので
> | * Hashクラスは現状維持
> | * Hash::Orderedを新設
> | * 従来ハッシュリテラルと呼ばれていた表記はHash::Orderedのリテラルに。
> | * Hash[:a => 1, :b => 2]のような表記でHashのインスタンスを生成できればよい。
>
> 同意しません。
>
>   * 全く同じ機能で性質だけ異なるクラスを複数用意するのは大ク
>     ラス主義を標榜するRuby的でない
>
>   * Hashという名前はHashアルゴリズムを使っていることしか意味
>     しない。keyの登場順序があるかどうかはスコープ外。ただし、
>     Rubyで順序があると他の言語で「順序はないのか」と騒ぐ人が
>     居たりして、教育的問題が発生する可能性は否定しない。
>
>   * 時間効率には順序を保たないかどうかは関係ない。
>
>   * 空間効率にはある程度関係があるが、ちゃんとベンチマークを
>     取ってみないとなにも言えない。それでも、どれだけ重大かは
>     ケースバイケースだと思うけど。
>
>   * とはいえ、インスタンス変数やシンボルテーブルにまで順序を
>     保証するのはやりすぎなので、それはやめる方向で。
>
> と考えています。ですから、将来ありえる組み合わせは
>
>   * 1.8のまま、順序は導入しない
>   * Hashに順序を導入する(ただし、インスタンス変数やシンボルテー
>     ブルなどにはない)
>
> のいずれかではないかと。気持ち的には後者に傾いています。

railsで多用されているようなキーワード引数のかわりなど、Hashリテラルの使
われ方としては:

  * 要素数が少なめ
  * 全てのキー値を使うことが多い
  * 新しい値を入れることは少ない
　* 左から順に繰り返す(とうれしい。この話題の発端)

というパターンが多いのではないかと思います(間違った推測かももしれません
が)。このタイプの使われ方に最適なのはどれか、あるいはたいして違いがない
のか。というところが、リテラルの実体にふさわしいデータ構造を選択する上
でのポイントのひとつだと思います。

もし、プログラミング上の互換性を維持できるより適切なデータ構造(どうなん
でしょう？＞データ構造に詳しい方々)があれば、リテラルの実体をHashからそ
ちらに乗り換えるという選択もありうるのではないかと思います。

藤本尚邦(hisa)

[Mitsuhiko OHKUBO]

大久保といいます。Ruby初心者ですがよろしくお願いします。


  時刻 2007/08/24 17:33:11
  Yukihiro Matsumoto さんは書きました
>   * 全く同じ機能で性質だけ異なるクラスを複数用意するのは大ク
>     ラス主義を標榜するRuby的でない
    「大クラス主義」が良くわからかったのですが、「少機能のクラス
を多数用意するよりも多機能なクラスを少数用意しましょう」というこ
とだろう、と思っての提案なのですが、違ってたらご指摘ください。

    Hashインスタンス生成時に順序維持の特性を持つハッシュライブラ
リの実装を使うか、持たないハッシュライブラリの実装を使うかを指定
できるようにはならないでしょうか？順序維持の特性が重要な場合があ
る一方で、他の特性（メモリ使用量とか）が重要な場合もありますので、
選択できる道を残しておいて欲しいです。


>   * Hashに順序を導入する(ただし、インスタンス変数やシンボルテー
>     ブルなどにはない)
    将来、さらに高性能なハッシュライブラリが現れた場合に、Hashの
仕様が順序維持を含むために、Hashの実装にそのライブラリを利用でき
ない、という状況は起き得ることなのでしょうか？
    もう一つ、同様の場合に、Hashの実装にそのライブラリを利用する
ためにHashの仕様から順序維持が外される、という状況は起き得ること
なのでしょうか？

    高性能なハッシュライブラリが利用できなかったり、動作している
コードが将来動作しなくなったり、といったことよりは、Hashが順序維
持の特性を持たないことの方がまだ嬉しいです。主観で申し訳ないので
すが。

    そもそも、現状のハッシュライブラリより高性能なライブラリが出
現しそうな情勢かどうかを知らないので、ナンセンスなことを尋ねてい
たらお許しください。


*-------*-------*-------*-------*-------*-------*-------*-------
                                                     大久保 光彦

[Yukihiro Matsumoto]

まつもと ゆきひろです

In message "Re: [ruby-list:43936] Re: Hashへの生成順は保障されないのか？"
    on Sat, 25 Aug 2007 01:59:53 +0900, m-ohkubo@... (Mitsuhiko OHKUBO) writes:

|>   * 全く同じ機能で性質だけ異なるクラスを複数用意するのは大ク
|>     ラス主義を標榜するRuby的でない
|    「大クラス主義」が良くわからかったのですが、「少機能のクラス
|を多数用意するよりも多機能なクラスを少数用意しましょう」というこ
|とだろう、と思っての提案なのですが、違ってたらご指摘ください。

そういうような意味です。

|    Hashインスタンス生成時に順序維持の特性を持つハッシュライブラ
|リの実装を使うか、持たないハッシュライブラリの実装を使うかを指定
|できるようにはならないでしょうか？順序維持の特性が重要な場合があ
|る一方で、他の特性（メモリ使用量とか）が重要な場合もありますので、
|選択できる道を残しておいて欲しいです。

選択肢が多い方がよいかと言うと必ずしもそうではないのです。と
いうか、ハッシュエントリひとつあたり2ワードの増加が問題にな
るような局面ではRubyの使用そのものが不適切な可能性が高いと思
います。

|>   * Hashに順序を導入する(ただし、インスタンス変数やシンボルテー
|>     ブルなどにはなない)
|    将来、さらに高性能なハッシュライブラリが現れた場合に、Hashの
|仕様が順序維持を含むために、Hashの実装にそのライブラリを利用でき
|ない、という状況は起き得ることなのでしょうか？
|    もう一つ、同様の場合に、Hashの実装にそのライブラリを利用する
|ためにHashの仕様から順序維持が外される、という状況は起き得ること
|なのでしょうか？

これはknuさんの懸念ですね。ですが、ハッシュと言うのはかなり古
典的なアルゴリズムですし、これから極端に性能が違うライブラリ
が登場する可能性はかなり低いと思います。Judyのような「キャッ
シュラインを意識した高速でHashっぽいライブラリ」というのは存
在しますが、JudyはHashではありませんし。

                                まつもと ゆきひろ /:|)

[Mitsuhiko OHKUBO]

大久保です。


    丁寧なご返答どうもありがとうございます。
    説明いただき、私の懸念は杞憂に終わりそうな印象を持ちました。


  時刻 2007/08/25 02:34:14
  Yukihiro Matsumoto さんは書きました
> まつもと ゆきひろです
>
> In message "Re: [ruby-list:43936] Re: Hashへの生成順は保障されないのか？"
>     on Sat, 25 Aug 2007 01:59:53 +0900, m-ohkubo@... (Mitsuhiko OHKUBO) writes:

> |    「大クラス主義」が良くわからかったのですが、「少機能のクラス
> |を多数用意するよりも多機能なクラスを少数用意しましょう」というこ
> |とだろう、と思っての提案なのですが、違ってたらご指摘ください。
>
> そういうような意味です。
    了解しました。

> |    Hashインスタンス生成時に順序維持の特性を持つハッシュライブラ
> |リの実装を使うか、持たないハッシュライブラリの実装を使うかを指定
> |できるようにはならないでしょうか？順序維持の特性が重要な場合があ
> |る一方で、他の特性（メモリ使用量とか）が重要な場合もありますので、
> |選択できる道を残しておいて欲しいです。
>
> 選択肢が多い方がよいかと言うと必ずしもそうではないのです。と
> いうか、ハッシュエントリひとつあたり2ワードの増加が問題にな
> るような局面ではRubyの使用そのものが不適切な可能性が高いと思
> います。

    このケースでは、ユーザが選択を行うコストに比べて得られる利益
が少ない、ということですね。了解しました。

    使用そのものが不適切、という指摘はそのとおりかもしれません。
私の場合、自分用プログラムを組んでいるので、使って楽しいのが一番、
という理由（だけ）で使用しています。仕事では通らない理由ですね。

> |    将来、さらに高性能なハッシュライブラリが現れた場合に、Hashの
> |仕様が順序維持を含むために、Hashの実装にそのライブラリを利用でき
> |ない、という状況は起き得ることなのでしょうか？
> |    もう一つ、同様の場合に、Hashの実装にそのライブラリを利用する
> |ためにHashの仕様から順序維持が外される、という状況は起き得ること
> |なのでしょうか？
>
> これはknuさんの懸念ですね。ですが、ハッシュと言うのはかなり古
> 典的なアルゴリズムですし、これから極端に性能が違うライブラリ
> が登場する可能性はかなり低いと思います。Judyのような「キャッ
> シュラインを意識した高速でHashっぽいライブラリ」というのは存
> 在しますが、JudyはHashではありませんし。

    ハッシュライブラリはほぼ煮詰まっている、ということなのですね。
了解しました。


*-------*-------*-------*-------*-------*-------*-------*-------
                                                     大久保 光彦

[Masahiro Sugaya]

菅谷です。今日も暑いですね。

初心者なので的外れかもしれませんがその時はお許し下さい。

ハッシュに順序があると嬉しい派です。
ただ、暗号プログラムを書いている人なんかは順序がランダムな方が嬉しかったりしないでしょうか。

順序ありがデフォルトでハッシュのキーの生成アルゴリズムをごっそり入れ替えられるメソッドがあったらどうなんでしょう。

07/08/25 に Mitsuhiko OHKUBO<m-ohkubo@...> さんは書きました:

> 大久保です。
>
>
>     丁寧なご返答どうもありがとうございます。
>     説明いただき、私の懸念は杞憂に終わりそうな印象を持ちました。
>
>
>   時刻 2007/08/25 02:34:14
>   Yukihiro Matsumoto さんは書きました
> > まつもと ゆきひろです
> >
> > In message "Re: [ruby-list:43936] Re: Hashへの生成順は保障されないのか？"
> >     on Sat, 25 Aug 2007 01:59:53 +0900, m-ohkubo@...
> (Mitsuhiko OHKUBO) writes:
>
> > |    「大クラス主義」が良くわからかったのですが、「少機能のクラス
> > |を多数用意するよりも多機能なクラスを少数用意しましょう」というこ
> > |とだろう、と思っての提案なのですが、違ってたらご指摘ください。
> >
> > そういうような意味です。
>     了解しました。
>
> > |    Hashインスタンス生成時に順序維持の特性を持つハッシュライブラ
> > |リの実装を使うか、持たないハッシュライブラリの実装を使うかを指定
> > |できるようにはならないでしょうか？順序維持の特性が重要な場合があ
> > |る一方で、他の特性（メモリ使用量とか）が重要な場合もありますので、
> > |選択できる道を残しておいて欲しいです。
> >
> > 選択肢が多い方がよいかと言うと必ずしもそうではないのです。と
> > いうか、ハッシュエントリひとつあたり2ワードの増加が問題にな
> > るような局面ではRubyの使用そのものが不適切な可能性が高いと思
> > います。
>     このケースでは、ユーザが選択を行うコストに比べて得られる利益
> が少ない、ということですね。了解しました。
>
>     使用そのものが不適切、という指摘はそのとおりかもしれません。
> 私の場合、自分用プログラムを組んでいるので、使って楽しいのが一番、
> という理由（だけ）で使用しています。仕事では通らない理由ですね。
>
> > |    将来、さらに高性能なハッシュライブラリが現れた場合に、Hashの
> > |仕様が順序維持を含むために、Hashの実装にそのライブラリを利用でき
> > |ない、という状況は起き得ることなのでしょうか？
> > |    もう一つ、同様の場合に、Hashの実装にそのライブラリを利用する
> > |ためにHashの仕様から順序維持が外される、という状況は起き得ること
> > |なのでしょうか？
> >
> > これはknuさんの懸念ですね。ですが、ハッシュと言うのはかなり古
> > 典的なアルゴリズムですし、これから極端に性能が違うライブラリ
> > が登場する可能性はかなり低いと思います。Judyのような「キャッ
> > シュラインを意識した高速でHashっぽいライブラリ」というのは存
> > 在しますが、JudyはHashではありませんし。
>     ハッシュライブラリはほぼ煮詰まっている、ということなのですね。
> 了解しました。
>
>
> *-------*-------*-------*-------*-------*-------*-------*-------
>                                                      大久保 光彦
>
>
>

[Yukihiro Matsumoto]

まつもと ゆきひろです

In message "Re: [ruby-list:43940] Re: Hashへの生成順は保障されないのか？"
    on Sat, 25 Aug 2007 12:10:27 +0900, "Masahiro Sugaya" <easylifenw@...> writes:

|ハッシュに順序があると嬉しい派です。
|ただ、暗号プログラムを書いている人なんかは順序がランダムな方が嬉しかったりしないでしょうか。
|
|順序ありがデフォルトでハッシュのキーの生成アルゴリズムをごっそり入れ替えられるメソッドがあったらどうなんでしょう。

うーむ、ランダムであるというのは順序についての特定の仮定を置
けないという意味だと思うので、セキュリティ的に安全という仮定
も置けないと思います。順序についての安全性が必要であれば(そん
なケースは思いつきませんが)明示的にshuffleすべきだと思います。

あるいは私も想像もしないようなケースでHashの順序が影響してく
るんでしょうか。

[sheepman]

こんにちは、sheepman です。

Hash に順序が保証された場合、内容は同じだけど順序が違う Hash 同士の
同一判定はどうなるんでしょうか。

{:a => 1, :b => 2} == {:b => 2, :a => 1}  #=>  ?

Hash#== に順序は考慮されるべきではないと思いますが、順序も含めた
同一性を判定するメソッドも欲しい気がします。HTML をパースして Hash
を使って表した時とか。

あと順序が保証された Hash を Marshal#dump,load したときに
順序は保存されるかも気になります。

--
sheepman / TAMURA Takashi
sheepman@...