[ruby-list:39831] Re: (要素がString, Fixnum 以外の)配列の集合演算

mput です。

On 06 Jul 2004, at 18:03, [e-mail] wrote:

> 動作としては変わりません。
> Array#include?は線形時間なのでall?全体ではO(n^2)になります。一
> 方、Hash#include?は定数時間なので、最初にHashを作る手間はありま
> すが、全体ではO(n)になります。

だからといってHashの方が高速とは一概に言えないあたりがO記法の難しいところなわけで、以下のような実験をすると、実用的な状況では配列そのもの 
の方が速いのではないかと.... 何十個もインスタンス変数があるようなのは稀だと思いますし。


% cat tmp.rb
class Foo

   alias iv instance_variables
   alias ivg instance_variable_get
   alias ivs instance_variable_set
   def initialize(n)
     n.times do |i|
       ivs("@#{i}", i)
     end
   end

   def eql1(other)
     self.class == other.class and
       (sv = iv).size == (ov = other.iv).size and
       (v = nil; oh = {}; ov.each {|v| oh[v] = true}; sv).all? do |v|
         oh.include?(v) and
           ivg(v).eql?(other.ivg(v))
       end
   end

   def eql2(other)
     self.class == other.class and
       (sv = iv).size == (ov = other.iv).size and
       sv.all? do |v|
         ov.include?(v) and
           ivg(v).eql?(other.ivg(v))
       end
   end
end

require 'benchmark'

(1..32).each do |i|
   foo = Foo.new(i)
   bar = Foo.new(i)
   t1  = Benchmark.realtime { 2048.times { foo.eql1(bar) } }
   t2  = Benchmark.realtime { 2048.times { foo.eql2(bar) } }
   printf("%2d %s faster\n", i, t1>t2 ? "array":" hash")
   STDOUT.flush
end

% ruby tmp.rb
  1 array faster
  2 array faster
  3 array faster
  4 array faster
  5 array faster
  6 array faster
  7 array faster
  8 array faster
  9 array faster
10 array faster
11 array faster
12 array faster
13 array faster
14 array faster
15 array faster
16 array faster
17 array faster
18  hash faster
19  hash faster
20  hash faster
21  hash faster
22  hash faster
23  hash faster
24  hash faster
25  hash faster
26  hash faster
27  hash faster
28  hash faster
29  hash faster
30  hash faster
31  hash faster
32  hash faster
%