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

[SASADA Koichi]

　ささだです。

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

　理由はなんでしょう。実装上たまたま順序が保障されているというのは良
いでしょうか。それとも、これも混乱を招く（保障されてると思ってどんど
んコードを書いちゃう人がいる）からダメでしょうか。


　名前を変えるのは賛成なのですが、問題なのは多分リテラルで簡単に書け
るかどうかってことだと思うのですよねぇ。

--
// SASADA Koichi at atdot dot net

[Shingo Hagiwara]

萩原といいます。

普段はただの利用者です。
この順序保存機能を、今のHashクラスに統合するのは僕も反対です。

理由は単純でして、メモリです。
9MBで考えるとたいしたこと有りませんが、
ギガ越えするプログラムを書いている人が少ないとは思えません。
そして、順序など必要ないのに、メモリ食いのHashを使わざるを得ない
環境になるのは正直悲しいです。
また、追加、削除、を繰り返した場合、再ソートしないと順序が順序でなくなる
ような曖昧なもののためにそんなにメモリをさきたくもないです。
かといって、Pushの度に自動で再ソートされてもHash本来の高速性が失われ
これも悲しくなります。

もともと、順序機能を付けたHashの実装を怠けた事から発生した
問題なので、もし組み込むのであれば、サブクラスにするのが妥当だと
素人目に思えます。

それでは、失礼しました。

[Urabe Shyouhei-4]

Shingo Hagiwara wrote:
> もともと、順序機能を付けたHashの実装を怠けた事から発生した
> 問題なので、

怠けとか言われるのは心外ですね。クラス名がわざわざHashとなって
いる以上、一般にこのデータ構造で順序が保存されないのは何も特別
なことではありません。問題でもないと思ってます。

[Fujimoto Hisa]

藤本です。

以前、人の書いたC++のプログラムを読んでいて、mapのイ
テレータを使っている
簡単なコードが何をしてるのかしばらく理解できなかったことがありま
す。C++の
map(順序あり)をRubyのHash(順序なし)のよ
うなものであると、自分が勘違いし
ていたのが原因でした。

勘違いとはいえこのような経験をした立場からは、Hash自体の順
序の意味を簡
単に変えてしまって本当にいいのかなという疑問が残ります。

と、スレッドを読んでいて考えていたのですが…

On 2007/08/21, at 19:29, SASADA Koichi wrote:

> 　ささだです。
>
> Akinori MUSHA wrote:
>> 　1.9 においても、 Hash という名前のクラスで順序
>> を保証することには
>> 反対です。別クラスにするか、せめて生成時オプションにしてほし
>> い。
>
> 　理由はなんでしょう。実装上たまたま順序が保障されているという
> のは良
> いでしょうか。それとも、これも混乱を招く（保障されてると思って
> どんど
> んコードを書いちゃう人がいる）からダメでしょうか。

> 　名前を変えるのは賛成なのですが、問題なのは多分リテラルで簡単
> に書け
> るかどうかってことだと思うのですよねぇ。

順序が保障されているHashのリテラルが書けると、Objective-
Cのメソッ
ド呼出しに便利だということに気付きました。


藤本尚邦

[Shingo Hagiwara]

萩原です。

すいませんでした。
「Rubyの実装が怠けていた」という意味ではないです。
本スレッドの一番初めの投稿者の事です。

とりあえず、誤解を。

僕は、ハッシュは本来順序がないものと思ってます。

それでは。

[rubikitch]

るびきちです。

僕もHashをOrderedHash化するのには反対です。
それとは別にOrderedHashを作るべきでしょう。

--

以下は記法の話。

ただ、{ 1=>"one", 2=>"two" }というリテラル（現在はHashですが）が表す
オブジェクトには順序が保存されてればいいなと思ったことはあります。
かといって {〜} をOrderedHashリテラルにしてしまうと
Hashの文字列表記も同じになるので混乱を生じます。

仮に [ 1=>"one", 2=>"two" ] をOrderedHashリテラルにしてみるとどうなんでしょうね。
Hashの機能を持ちながら配列の機能（順序保存）を持っているので適任な気がします。
Ruby 1.8では [{1=>"one", 2=>"two"}] と解釈されるけど、
この記法で Hash 1つからなる配列を作ることは稀な気がします。

でも、OrderedHashってそんなに利用頻度高いのかな？ただあると便利なだけかな？
要素数が少なければ普通に alist で十分な気がします。

そもそもRubyのHashに順序を期待する人が現れるのは、
Hashリテラルが少し配列っぽく見えるからだと僕は考えています。
{1,2,3,4}（ {1=>2, 3=>4} と解釈される）なんてのもできますし。

--
rubikitch
http://www.rubyist.net/~rubikitch/

[Akinori MUSHA]

At Tue, 21 Aug 2007 19:29:11 +0900,
SASADA Koichi wrote:
> Akinori MUSHA wrote:
> > 　1.9 においても、 Hash という名前のクラスで順序を保証することには
> > 反対です。別クラスにするか、せめて生成時オプションにしてほしい。
>
> 　理由はなんでしょう。実装上たまたま順序が保障されているというのは良
> いでしょうか。それとも、これも混乱を招く（保障されてると思ってどんど
> んコードを書いちゃう人がいる）からダメでしょうか。

　そうですね。まとめになってしまいますが、

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

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

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

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

などが理由です。

> 　名前を変えるのは賛成なのですが、問題なのは多分リテラルで簡単に書け
> るかどうかってことだと思うのですよねぇ。

　リテラル表現を用意すると、バックポートしない限り下位互換性を
失いますが、それはさておき。

　[ x1 => y1, ... ] だと順序付きマップを生成するとか？これは今は
[{ x1 => y1, ... ]} と解釈されますが、文法的には配列と区別可能。

　Set もそろそろ組み込みに…。こちらはもちろん { x, y, z, w }。
わかりにくいか！ (j/k)


　%m{ x1 => y1, ... } みたいなのもないことはないと思います。


　が、そもそもリテラル記法が必要なほど多用されるかどうか。

--
                     /
                    /__  __            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"

[Shin'ya Adzumi]

あづみです。

あらあらあらって感じであっさり入っちゃいましたねえ。

SASADA Koichi さんは書きました:
> 　理由はなんでしょう。実装上たまたま順序が保障されているというのは良
> いでしょうか。それとも、これも混乱を招く（保障されてると思ってどんど
> んコードを書いちゃう人がいる）からダメでしょうか。

「たまたま」なんて都合のいい言葉が通用しますかねえ。
個人的には不幸な未来が待ってるようにしか思えないです。

そもそも「たまたま」なら実装するメリットってあるんでしょうか。
ほとんど遅くならなかっただけで、メモリは食うし、デメリットしかないような。
前のパッチで速くなるなら、順序を保証しなくても速くなるんじゃない？と思うのは短絡すぎ？

> 　名前を変えるのは賛成なのですが、問題なのは多分リテラルで簡単に書け
> るかどうかってことだと思うのですよねぇ。

リテラルで簡単に書けるから、Hash がいろんな使われ方しちゃうっても大きいんでしょうね。


安積伸弥
adzumi@...

[松房 一郎]

OrderedHash.new()にArrayを渡せるようにしておけば
OrderedHash.new([1. "One", 2, "Two"])
という書き方でリテラルもどきにできます。メリットは、
- リテラルと同様にオブジェクトの値がプログラムソースでわかる
- 文法の拡張は不要なので、下位互換性を維持できる

Akinori MUSHA さんは書きました, (2007/08/21 21:47):
 > 　リテラル表現を用意すると、バックポートしない限り下位互
換性を

> 失いますが、それはさておき。
>
> 　[ x1 => y1, ... ] だと順序付きマップを生成するとか？これは今は
> [{ x1 => y1, ... ]} と解釈されますが、文法的には配列と区別可能。
>
> 　Set もそろそろ組み込みに…。こちらはもちろん { x, y, z, w }。
> わかりにくいか！ (j/k)
>
>
> 　%m{ x1 => y1, ... } みたいなのもないことはないと思います。
>
>
> 　が、そもそもリテラル記法が必要なほど多用されるかどうか。
>

[rubikitch]

From: 松房 一郎 <adj41380@...>
Subject: [ruby-list:43908] Re: Hashへの生成順は保障されないのか？
Date: Tue, 21 Aug 2007 22:22:21 +0900

> OrderedHash.new()にArrayを渡せるようにしておけば
> OrderedHash.new([1. "One", 2, "Two"])
> という書き方でリテラルもどきにできます。メリットは、

それならいっそのこと OrderedHash[1, "One", 2, "Two"] のほうがいいのでは？
([ 〜 ])がちょっと嫌。

でも現文法でできるところはそこまででしょうね。
なんといっても => がないとHashという感じがしませんし。
--
rubikitch
http://www.rubyist.net/~rubikitch/

[Tetsuo Sakaguchi]

阪口です。

ちょっとベンチマークの値が気になったので、パッチを
覗いてみたのですが、ちょっと気になる点を見つけました。
（重箱の角でしかないかもしれませんが。。）

In message <20070821014331.6640AE02CB@...> 2007-08-21T10:43+0900,
        Nobuyoshi Nakada <nobu@...> wrote:
> http://www.rubyist.net/~nobu/ruby/ordered-hash-1.9.diff
> http://www.rubyist.net/~nobu/ruby/ordered-hash-1.8.diff

このパッチ、rehashのメモリの割り当てが Calloc(=calloc) から、
xrealloc に変更されていますね。
このパッチによってrehash時の「0初期化」処理の分は少なくとも
速くなると思うので、それによって（ある程度）相殺されているということは
ないでしょうか？

(あと、私が計るとブロックを { sg.generate; sg.generate } のみにした時と
add to empty hashを比較したら、1.579real : 1.796real のようになったので、
最初の2つはどちらかというとシンボル生成の時間がかなりを占めるようです。
環境にもよると思いますが。)

PS. 時間がとれれば環境整えて自分でパッチを当ててみようかとも思いますが、、。
--
阪口哲男＠図書館情報メディア研究科．大学院．筑波大学
Tetsuo SAKAGUCHI.
Graduate School of Library, Information and Media Studies
University of Tsukuba, JAPAN.

[pegacorn-2]

「保証する」のも「たまたま」なのも反対です。

 From: SASADA Koichi <ko1@...>
 Date: Tue, 21 Aug 2007 19:29:11 +0900
 Message-Id: <46CABE7A.2040700@...>
/~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> 　理由はなんでしょう。実装上たまたま順序が保障されているというのは良
> いでしょうか。それとも、これも混乱を招く（保障されてると思ってどんど
> んコードを書いちゃう人がいる）からダメでしょうか。

◇「保証する」の場合

・保証されなくても良い場合でも、メモリの使用量が 5/3 倍にもなるのは
  受入れ難い

・保証されなくても良い場合でも、遅くなるかもしれない
  # 訳あって実務的なスクリプトとデータが全く手元に無いので、
  # 実際速くなる方が多いのか少ないのかわかりませんが、
  # メモリの使用量が 5/3 倍にもなると速度低下をもたらす気がします。

> 　名前を変えるのは賛成なのですが、問題なのは多分リテラルで簡単に書け
> るかどうかってことだと思うのですよねぇ。

 ・それが問題になるほど多用されるとは思わない


◇「たまたま」の場合

・メモリの使用量が 5/3 倍にもなるのは受入れ難い

・混乱を招くかもしれない
  （保障されてると思ってコードを書いてしまう人が出てくるかもしれない）
  # Hash ではありませんが、C++ で初めてプログラムを書いたときに、
  # std::map を実装で使って順序性を期待させるべきでない場面で
  # 順序性を保証してしまった経験があります… orz

・遅くなるかもしれない

・速くなるかもしれないという以外に利点が無い


--
pegacorn

[NAKAMURA Akifumi]

A.nakamuraです。


マニュアル見たんですが、
http://www.ruby-lang.org/ja/man/?cmd=view;name=Hash
この冒頭の説明(現時点での)を読んだだけで
「こりゃ順序無いよな」と「わかる」人ってのは、
ハッシュという単語の持つ真の意味を理解してる人で、
わからん人はわからんで終わっちゃうんじゃないでしょうか？
Hashという名がアルゴリズムを暗示(どころではないが)してる
ということに気づかない人は気づかない。

「連想配列」という言葉も、順序が無いとは言ってないわけで。
(有るとも言ってませんが)

んー。ハッシュとは何ぞや、みたいなことも書いたほうがいいのかなあ。
あるいは説明してる外部サイトにリンクしちゃうとか？
WikipediaJ:ハッシュテーブル …
うーん何だかいきなり濃い話になってるし…



rubikitch@... さんは書きました:
> なんといっても => がないとHashという感じがしませんし。

個人的にはどういうわけかHashのあれの「=>」に何年たっても馴染めないでいます。
リテラルで「一発で」書けることには強い魅力は感じますが、
Hashのあのリテラルがどうも好めない。

そこで「一段かまして」書くという妥協を考えたりします。
あるいはHash[key,value,...]と同様の路線で。

で、
OrderedHash[1, "One", 2, "Two"]
もそれと似たようなもんかなと思うんで一票。
OrderdHashという名前が長くていやだ！というなら、
aでもなんでもいい(わら)から別名で呼べばいいし。

っていうか、欲しい人が
def a(data)
  HogehogeConntainer.new(data)
end
って書くってことで良いような気がするんだよなあ。
Ruby本体を一番弄らずに済むのはコレ、でしょうか。

確かに時として、リテラルに直結してるクラスが
「うらやましく」思えることも有るんですが、
「一段かます」つまりコンバートすると考えれば、
まあ妥協の範囲かなと思っています。
Arrayなりなんなりを1つ使い捨てることになりますが、
LLなんだからイイヤンというか(^^;。
そしてリテラルで書くってことは(JSON的に使う場合を除けば)
あまり巨大なデータは入れないだろって鯖読んでみたり。


あと、
%m{ x1 => y1, ... }
または
%m{ x1, y1, ... }
みたいに
括弧にPrefixつける(というのでしょうか？)ことで意味を変える、
っていう仕組みをもし(Rubyで書くときに)使えるんだったら、
色々やれそうですね。
＃収拾つかなくなる恐れもありますが(^^;

[SASADA Koichi]

　ささだです．

rubikitch@... wrote:
> そもそもRubyのHashに順序を期待する人が現れるのは、
> Hashリテラルが少し配列っぽく見えるからだと僕は考えています。
> {1,2,3,4}（ {1=>2, 3=>4} と解釈される）なんてのもできますし。

　実は，こっそり {1,2,3,4} は 1.9 からは禁止されるような方針だったり
します（処理系からは消されています）．

　まつもとさんはぎゃっという人が居たらやめよう，と言ってましたが，今
はぎゃっというチャンスな気がします．

--
// SASADA Koichi at atdot dot net
// これに関しては，どっちでもいいんですが，どっちでもいいので
// 無くす意味はないんじゃないかと思っています．

[SASADA Koichi]

　ささだです．

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

　性能に関しては別の意見もあるのですが，この問題は確かにそう思います．


　しかし，仕様に関して，わかりやすい問題だからでしょうか，凄い盛り上
がりますね．ruby 1.9 では色々と変更するようなのですが，ここにポスト
したほうがいろいろ意見が聞ける？

--
// SASADA Koichi at atdot dot net

[ARAI Shunichi]

> 　実は，こっそり {1,2,3,4} は 1.9 からは禁止されるような方針だったり
> します（処理系からは消されています）．

> 　まつもとさんはぎゃっという人が居たらやめよう，と言ってましたが，今
> はぎゃっというチャンスな気がします．

ぎゃっ！

すでに{1,2,3,4}方式を沢山つかってサービス開始してしまいました。
静的に判断できる問題なので、移行支援ツールが登場すれば
簡単に移行できるような気もしますけども....

Ruby 1.9への移行支援ビジネスができそう。

---
あらいしゅんいち

[GOTO Kentaro]

にぎわってるのにまぎれてよく読まずに書いちゃいますが、
いま話題になってるクラスはどんな API なんでしょうか。
ハッシュに順序をつけるといっても、経験的には少なくとも
* 格納された順序を覚えられる
* keys.sort_by(&ord).each do |k| ... end の ord 相当を指定できる
という二通りを必要とすることが多いんですが、両方サポートしているんでしょうか。

前者の場合、delete された後に再格納された場合の順序をどうしたらいいのか
というのがばあいによってちがったりするので、結局どうまとめるのがいいのか
よくわかんなくて日常生活では要るものを都度つくってます。


ごとけん

[Nobuyoshi Nakada-2]

なかだです。

At Wed, 22 Aug 2007 01:36:59 +0900,
GOTO Kentaro wrote in [ruby-list:43916]:
> ハッシュに順序をつけるといっても、経験的には少なくとも
> * 格納された順序を覚えられる
> * keys.sort_by(&ord).each do |k| ... end の ord 相当を指定できる
> という二通りを必要とすることが多いんですが、両方サポートしているんでしょうか。

前者のみです。

> 前者の場合、delete された後に再格納された場合の順序をどうしたらいいのか
> というのがばあいによってちがったりするので、結局どうまとめるのがいいのか
> よくわかんなくて日常生活では要るものを都度つくってます。

追加は最後です。

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

[rubikitch]

From: NAKAMURA Akifumi <BXQ04723@...>
Subject: [ruby-list:43912] Re: Hashへの生成順は保障されないのか？
Date: Wed, 22 Aug 2007 00:53:54 +0900

> 「連想配列」という言葉も、順序が無いとは言ってないわけで。
> (有るとも言ってませんが)

あぁ、昔はPerlからの流れで僕もHashを「連想配列」と呼んでいましたね。
連想配列という言葉から「連想配列⊂配列」な印象を持って、
では配列ならば順序があるだろうと期待する人がいるかもしれませんね。

<昔話>
Cしか知らなかった当時、Perl4を触って初めて連想配列に出会ったときの衝撃を今で
もはっきりと覚えています。
</昔話>

--
rubikitch
http://www.rubyist.net/~rubikitch/

[GOTO Kentaro]

ずぼらな質問に答えてくれて中田さんどうもありがとうです。

07/08/22 に Nobuyoshi Nakada<nobu@...> さんは書きました:
> > * 格納された順序を覚えられる
> > * keys.sort_by(&ord).each do |k| ... end の ord 相当を指定できる
> > という二通りを必要とすることが多いんですが、両方サポートしているんでしょうか。
>
> 前者のみです。

なるほど。
大クラス主義的にはずいぶんと貧弱な気がしました。
でもまあ、例外を起こさないように任意の順序を指定するのは
手軽ではなかったりもしますね。

ちなみに僕が順序をほしがるときはたいてい文字列処理の一環で、
それも多くはファイルの読み書きの場合です。たとえば、to_yaml の順序が
気になるようなばあいとかですね。あるいはXMLの属性みたいなのの
出現順序を覚えておきたいときとか。to_yaml だったら Hash#each を
書き換えて keys.sort_by 順で実行するようにしちゃうし、
出現順記録の場合は、格納順を覚える配列を持たせてます。
文字列以外の場合をあさってみると、ノードにラベルが
ついた木を作るときなんかも Hash のネストで代用したりしますが、
そういうときに必要な順序の定義はアプリケーション依存ですね。

ごとけん
# 連想配列と聞くと AWK を思い出します