From: sinara@...
Date: 1997-01-31T14:35:53+09:00
Subject: [ruby-list:1993] Re: Hash of Hash/Array(Re: [Dist] Mutex module)

原です。

From: keiju@shljapan.co.jp (石塚圭樹 )
Subject: [ruby-list:1986] Re: [Dist] Mutex module 
Date: Fri, 31 Jan 97 05:27:39 JST

> けいじゅ＠SHLジャパンです. 

> 松本氏の[ruby-list: 1960]にあったようにArrayはlistとし, Vectorとして
> extendされたArrayはtuppleにするというのも1つの手かも知れませんね.

なるほど、それはいいかもしれないです。


> >私の感じではなんとなく、オブジェクトと１：１対応して（すぎ？）いる
> >id でハッシュを引くのは手軽だけどもったいないような気がするんです。
> >そのハッシュってところどころ間の抜けた配列みたいなもんですよね。そ
> >れなら、オブジェクトの生成順に自分で番号を振って番号だけで管理した
> >方が高速ではないかしら？
> 
> それはないんですよね. ハッシュの検索コストは要素数に比例せず一定ですが, 
> 線形検索だと要素数に比例しますし, 2分検索だと要素数の対数に比例するこ
> とになります.


それは array.include?(key) のコストと hash[key] の比較ですね。
私がいいたかったのは、id はオブジェクトと 1:1 対応しているのだか
ら、いっそオブジェクトの生成順に番号 n を振ろうと。n とオブジェク
トは 1:1 だから、n をオブジェクトと思っていい。このばあい、検索は
array.include?(n) ではなくて、

array[n]

で済むでしょう、ということです。（ハードウェアとしてのメモリが線
形構造であるかぎり、もっとも高速な検索ですね。^^;）hash 関数とし
て n を取ったハッシュみたいなもんです。ただし hash 関数を構成する
コストがかからない。