[ruby-dev:25207] Re: [ruby-cvs] ruby/lib/cgi/session, ruby/lib/cgi, ruby/lib, ruby/ext/openssl, ruby: * lib/set.rb (Set#==):

In article <[e-mail]>,
  [e-mail] (matz) writes:

> matz        Wed, 15 Dec 2004 15:35:56 +0900

>     * lib/set.rb (Set#==): [ruby-dev:25206]

>   Revision    Changes    Path

>   1.24        +8   -8    ruby/lib/set.rb
>     http://www.ruby-lang.org/cgi-bin/cvsweb.cgi/ruby/lib/set.rb?cvsroot=src&r1=1.23&r2=1.24

もしかしたら計算量なんて気にしないのかも知れませんが、Set#== のオーダ
が変わっているようです。

以前は、

% ./ruby -rset -ve '
100.times {|n| n *= 100
  s1 = Set.new; n.times {|i| s1 << i }
  s2 = Set.new; n.times {|i| s2 << i }
  tms1 = Process.times
  s1 == s2
  tms2 = Process.times
  puts "#{n} #{tms2.utime-tms1.utime}"
}
'
ruby 1.9.0 (2004-12-14) [i686-linux]
-e:6: warning: useless use of == in void context
0 0.0
100 0.0
200 0.0
300 0.0
400 0.0
500 0.0
600 0.0
700 0.01
800 0.0
900 0.01
1000 0.0
1100 0.0
1200 0.01
1300 0.01
1400 0.0
1500 0.0
1600 0.0
1700 0.0
1800 0.01
1900 0.01
2000 0.0
2100 0.0
2200 0.01
2300 0.01
2400 0.0
2500 0.01
2600 0.0
2700 0.01
2800 0.01
2900 0.00999999999999995
3000 0.01
3100 0.0
3200 0.01
3300 0.01
3400 0.01
3500 0.01
3600 0.0
3700 0.01
3800 0.00999999999999995
3900 0.01
4000 0.01
4100 0.01
4200 0.0099999999999999
4300 0.01
4400 0.01
4500 0.01
4600 0.01
4700 0.01
4800 0.01
4900 0.01
5000 0.01
5100 0.0099999999999999
5200 0.01
5300 0.02
5400 0.01
5500 0.02
5600 0.01
5700 0.01
5800 0.02
5900 0.01
6000 0.01
6100 0.01
6200 0.01
6300 0.01
6400 0.02
6500 0.02
6600 0.02
6700 0.02
6800 0.01
6900 0.01
7000 0.02
7100 0.02
7200 0.02
7300 0.02
7400 0.02
7500 0.01
7600 0.02
7700 0.02
7800 0.02
7900 0.0100000000000002
8000 0.00999999999999979
8100 0.0100000000000002
8200 0.00999999999999979
8300 0.02
8400 0.02
8500 0.02
8600 0.02
8700 0.02
8800 0.02
8900 0.02
9000 0.02
9100 0.02
9200 0.02
9300 0.02
9400 0.0299999999999998
9500 0.02
9600 0.02
9700 0.0100000000000002
9800 0.02
9900 0.02

というくらいで動いていたのが、変更後は

Z(3):akr@serein% ./ruby -rset -ve '
100.times {|n| n *= 100
  s1 = Set.new; n.times {|i| s1 << i }
  s2 = Set.new; n.times {|i| s2 << i }
  tms1 = Process.times
  s1 == s2
  tms2 = Process.times
  puts "#{n} #{tms2.utime-tms1.utime}"
}
'
ruby 1.9.0 (2004-12-15) [i686-linux]
-e:6: warning: useless use of == in void context
0 0.0
100 0.0
200 0.01
300 0.01
400 0.02
500 0.03
600 0.04
700 0.06
800 0.07
900 0.1
1000 0.12
1100 0.14
1200 0.17
1300 0.19
1400 0.23
1500 0.26
1600 0.3
1700 0.33
1800 0.37
1900 0.41
2000 0.46
2100 0.53
2200 0.57
2300 0.61
2400 0.67
2500 0.73
2600 0.78
2700 0.82
2800 0.94
2900 0.960000000000001
3000 1.02
3100 1.13
3200 1.16
3300 1.24
3400 1.3
3500 1.39
3600 1.46
3700 1.55
3800 1.63
3900 1.73
4000 1.79
4100 1.89
4200 2.0
4300 2.1
4400 2.22
4500 2.31
4600 2.41999999999999
4700 2.55
4800 2.69
4900 2.76
5000 2.9
5100 3.01000000000001
5200 3.11
5300 3.24
5400 3.38
5500 3.55
5600 3.65000000000001
5700 3.78
5800 3.90000000000001
5900 4.05
6000 4.2
6100 4.31
6200 4.23999999999999
6300 4.39
6400 4.59
6500 4.70999999999999
6600 4.90000000000001
6700 5.04000000000001
...

というように、時間がかかるようになっています。
たぶん、s1 == s2 で、O(s1.size * s2.size) になっているように思います。

また、ソースを眺めて気がついたのですが、

  def eql?(o)   # :nodoc:
    @hash.hash == o.hash
  end

という定義は変だと思います

% ./ruby -rset -e '
s1 = Set[]
s2 = Set[1]
p s1, s2, s1.eql?(s2)
'
#<Set: {}>
#<Set: {1}>
true
-- 
[田中 哲][たなか あきら][Tanaka Akira]