From: Guillaume Marcais <guslist@...>
Date: 2003-05-30T00:15:32+09:00
Subject: Re: Array.extend versus instance.extend

On Thursday 29 May 2003 07:20 am, you wrote:
> On Thu, 29 May 2003 20:56:34 +0900, Brian Candler wrote:
> > Another idea, "length != 0" could be replaced with "not empty?"
>
> Using 'until' instead of 'while' does reduce it even further :-)
>
>
> module ArrayMisc
> 	def shift_until(klass)
> 		res = []
> 		until empty? or klass === first
> 			res << self.shift
> 		end
> 		res
> 	end
> 	def pop_until(klass)
> 		res = []
> 		until empty? or klass === last
> 			res.unshift(self.pop)
> 		end
> 		res
> 	end
> end

This is faster:
module ArrayMisc2
  def shift_until(klass)
    p = -1
    detect { |x| p += 1; klass === x }
    slice!(0, p)
  end
  def pop_until(klass)
    p = -1
    reverse.detect { |x| p += 1; klass === x }
    slice!(-p, p)
  end
end

Guillaume.

Speed test:
[gus@comp ruby]$ cat array.rb
#! /usr/bin/ruby

module ArrayMisc
  def shift_until(klass)
    res = []
    until empty? or klass === first
      res << self.shift
    end
    res
  end
  def pop_until(klass)
    res = []
    until empty? or klass === last
      res.unshift(self.pop)
    end
    res
  end
end

module ArrayMisc2
  def shift_until(klass)
    p = -1
    detect { |x| p += 1; klass === x }
    slice!(0, p)
  end
  def pop_until(klass)
    p = -1
    reverse.detect { |x| p += 1; klass === x }
    slice!(-p, p)
  end
end

def equi_test(src, max, ext1, ext2)
  1.upto(10) do |i|
    b1 = src.dup
    b2 = src.dup
    b1.extend(ext1)
    b2.extend(ext2)
    c1 = b1.shift_until(max / i)
    c2 = b2.shift_until(max / i)
    puts("shift %d: %s %s" % [max / i, b1 == b2, c1 == c2])

    b1 = src.dup
    b2 = src.dup
    b1.extend(ext1)
    b2.extend(ext2)
    c1 = b1.pop_until(max / i)
    c2 = b2.pop_until(max / i)
    puts("pop %d: %s %s" % [max / i, b1 == b2, c1 == c2])
  end
end

def speed_test(src, max, ext)
  1.upto(10) do |i|
    b = src.dup
    b.extend(ext)
    t = Time.now
    b.shift_until(max / i)
    t = Time.now - t
    puts("shift %d: %s" % [max / i, t.to_s])

    b = src.dup
    b.extend(ext)
    t = Time.now
    b.pop_until(max / i)
    t = Time.now - t
    puts("pop %d: %s" % [max / i, t.to_s])
  end
end

max = 10000
a = Array.new
1.upto(max) do |i| a << i end

puts("Equi test")
equi_test(a, max, ArrayMisc, ArrayMisc2)

puts("Speed test with ArrayMisc")
speed_test(a, max, ArrayMisc)

puts("Speed test with ArrayMisc2")
speed_test(a, max, ArrayMisc2)

[gus@comp ruby]$ ruby array.rb
Equi test
shift 10000: true true
pop 10000: true true
shift 5000: true true
pop 5000: true true
shift 3333: true true
pop 3333: true true
shift 2500: true true
pop 2500: true true
shift 2000: true true
pop 2000: true true
shift 1666: true true
pop 1666: true true
shift 1428: true true
pop 1428: true true
shift 1250: true true
pop 1250: true true
shift 1111: true true
pop 1111: true true
shift 1000: true true
pop 1000: true true
Speed test with ArrayMisc
shift 10000: 0.582758
pop 10000: 3.7e-05
shift 5000: 0.46754
pop 5000: 0.116931
shift 3333: 0.343047
pop 3333: 0.243035
shift 2500: 0.268995
pop 2500: 0.313689
shift 2000: 0.2221
pop 2000: 0.365074
shift 1666: 0.189278
pop 1666: 0.398018
shift 1428: 0.162366
pop 1428: 0.423032
shift 1250: 0.14342
pop 1250: 0.440438
shift 1111: 0.127911
pop 1111: 0.454871
shift 1000: 0.116714
pop 1000: 0.46972
Speed test with ArrayMisc2
shift 10000: 0.044474
pop 10000: 0.000476
shift 5000: 0.022319
pop 5000: 0.022654
shift 3333: 0.015035
pop 3333: 0.030153
shift 2500: 0.011277
pop 2500: 0.034355
shift 2000: 0.009064
pop 2000: 0.036037
shift 1666: 0.007574
pop 1666: 0.037444
shift 1428: 0.00655
pop 1428: 0.038519
shift 1250: 0.005707
pop 1250: 0.039406
shift 1111: 0.005158
pop 1111: 0.040032
shift 1000: 0.004618
pop 1000: 0.040485