From: Martin DeMello <martindemello@...>
Date: 2002-02-12T01:50:51+09:00
Subject: Re: array diff

David Alan Black <dblack@candle.superlink.net> wrote:

> (Mind you, I think the #delete_at could get slow with big arrays,
> since it's rewriting the array so often.)

As would all the calls to index (isn't that O(n)?). Hashing the array and
extracting keys at the end seems to be faster:

#!/usr/bin/ruby -w

require "benchmark"
include Benchmark

class Array
  
  def minus1 other
    out = self.dup
    other.each do |el|
      if out.index(el)
	out.delete_at out.index(el)
      end
    end
    out
  end

  def minus2 a
    h = Hash.new(0)
    self.each {|i| h[i] += 1 }
    a.each {|i| h[i] -= 1 if h[i] > 0 }
    h.reject!{|k,v| v == 0}
    retval = h.keys
    h.each_pair{|k,v| 
      if v>1 
        (v-1).times {retval << k}
      end
    }
    retval 
  end
end

a = Array.new
b = Array.new

1000.times {
  a << rand(100)
  b << rand(100)
}

puts a.minus1(b).sort == a.minus2(b).sort

n = 10

bm(12) {|x|
  x.report("index + delete") { n.times {a.minus1(b)}}
  x.report("-> hash + keys") { n.times {a.minus2(b)}}
}

-------------------------------
minus1 == minus2 : true
                  user     system      total        real
index + delete  3.240000   0.010000   3.250000 (  6.931924)
-> hash + keys  0.230000   0.000000   0.230000 (  0.467032)

-- 
Martin DeMello