From: "trans.  (T. Onoma)" <transami@...>
Date: 2004-10-06T09:17:13+09:00
Subject: Re: [RCR] New [] Semantics

I did some benchmarking of my mod to Range class:

CURRENT
                user     system      total        real
range_nan:    2.000000   0.020000   2.020000 (  2.048289)
range_small:  0.380000   0.010000   0.390000 (  0.404542)
range_med:   42.030000   0.050000  42.080000 ( 42.115926)

NEW
                user     system      total        real
range_nan:    4.780000   0.300000   5.080000 (  5.073047)
range_small:  0.910000   0.060000   0.970000 (  0.988524)
range_med:    0.890000   0.060000   0.950000 (  0.983201)


As is, this looses about 50% speed on non-numeric ranges and small ranges, but 
quickly catches up and vastly outruns on larger numeric ranges. Of course 
this is also pure Ruby code vs. the internal C code (I presume). With a bit 
more tweaking and implementation in core I believe this would beat the 
current code on non-numeric and small ranges too, and of course be even more 
vastly superior on the large numerics.

Also, I gave it some thought, and think it would be best if a new class called 
NumericRange were made for this. Range could coerce/factory to NumericRange 
if the range arguments met the criteria.

Of course, my version also has a couple extra features like exclude_first? and 
step, too ;)

T.


----------------------------------------

require 'benchmark'

$n = 50000

def range_nan
  $n.times { ('a'..'k').member?('f') }
  $n.times { ('a'..'k').member?('r') }
end

def range_small
  $n.times { (0..6).member?(3) }
  $n.times { (0..6).member?(7) }
end

def range_med
  $n.times { (0..1000).member?(500) }
  $n.times { (0..1000).member?(1001) }
end

### --- bench ---

puts "\nCURRENT"
Benchmark.bm(10) do |b|
  b.report("range_nan:") { range_nan }
  b.report("range_small:") { range_small }
  b.report("range_med:") { range_med }
end

puts "\nNEW"
require 'succ.succ/range'
Benchmark.bm(10) do |b|
  b.report("range_nan:") { range_nan }
  b.report("range_small:") { range_small }
  b.report("range_med:") { range_med }
end

puts


----------------------------------
>
> Infinity = 1.0/0
>
> # for added flare ;)
> module Comparable
>   alias old_between? between?
>   def between?(a,b=nil)
>     if a.kind_of?(Range)
>       a.circumscribes?(self)
>     else
>       old_between(a,b)
>     end
>   end
> end
>
>
> class Range
>
>   alias init_old initialize
>   def initialize(first, last, exfirst=false, exlast=false, step=1)
>     @exclude_first = exfirst
>     @step = step
>     init_old(first, last, exlast)
> # not needed, Ruby catches already
> #     if ! numeric_range? && first == -Infinity
> #       raise "Ordinal range can not begin with -Infinity."
> #     end
>   end
>
>   def exclude_first?
>     @exclude_first
>   end
>   alias exclude_begin? exclude_first?
>   alias exclude_last? exclude_end?
>
>   def numeric_range?
>     @numeric_range ||= (first.kind_of?(Numeric) && last.kind_of?(Numeric))
>   end
>
>   def infinite_range?
>     @infinite_range ||= (first.abs == Infinity or last.abs == Infinity)
>   end
>
>   def step(s=nil)
>     if s
>       @step = s
>     else
>       @step ||= 1
>     end
>     @step
>   end
>   def x(s)
>     @step = s
>     self
>   end
>
>   def member?(val)
>     if numeric_range?
>       return false if ! circumscribes?(val)
>       return true if first == -Infinity && last == Infinity  # ?
>       return true if val.abs == Infinity  # this one was tricky
>       if first.abs != Infinity
>         return (((val + first) % step) == 0)
>       elsif first == -Infinity  # flip this around
>         r = Range.new(-last,Infinity,exclude_last?,exclude_first?,step)
>         return r.member?(-val)
>       else  # first == Infinity
>         true
>       end
>     else  # ordinal range
> # looks like this isn't needed as Ruby sees this a bad news already!
> #       # last can't be Infinite too (otherwise it be numeric range)
> #       if first == -Infinity
> #         # should be caught in initialize but I can't trap literal so...
> #         raise "Ordinal range can not begin with -Infinity."
> #       end
>       # basic operation
>       til = exclude_last? ? -1 : 0
>       elem = exclude_first? ? first.succ : first
>       while (elem <=> last) < til
>         return true if (val <=> elem) == 0
>         step.times { elem = elem.succ }
>       end
>     end
>     false
>   end
>   alias include? member?
>
>   def circumscribes?(val)
>     case val<=>first
>     when -1 then return false
>     when 0 then return false if exclude_first?
>     end
>     case val<=>last
>     when 1 then return false
>     when 0 then return false if exclude_last?
>     end
>     return true
>   end
>
> end
>
>
> -------------------
>
>   # no doubt there are a lot more tests to do ;)
>
>   require 'succ.succ/range'
>   require 'test/unit'
>
>   class GeneralTest < Test::Unit::TestCase
>     def test_circumscribes?
>       a = (1..10)
>       assert_equal(false, a.circumscribes?(0))
>       assert_equal(true, a.circumscribes?(1))
>       assert_equal(true, a.circumscribes?(2))
>       assert_equal(true, a.circumscribes?(9))
>       assert_equal(true, a.circumscribes?(10))
>       assert_equal(false, a.circumscribes?(11))
>       a = (1...10)
>       assert_equal(false, a.circumscribes?(0))
>       assert_equal(true, a.circumscribes?(1))
>       assert_equal(true, a.circumscribes?(2))
>       assert_equal(true, a.circumscribes?(9))
>       assert_equal(false, a.circumscribes?(10))
>       assert_equal(false, a.circumscribes?(11))
>       a = Range.new(1,10,true,false)
>       assert_equal(false, a.circumscribes?(0))
>       assert_equal(false, a.circumscribes?(1))
>       assert_equal(true, a.circumscribes?(2))
>       assert_equal(true, a.circumscribes?(9))
>       assert_equal(true, a.circumscribes?(10))
>       assert_equal(false, a.circumscribes?(11))
>       a = Range.new(1,10,true,true)
>       assert_equal(false, a.circumscribes?(0))
>       assert_equal(false, a.circumscribes?(1))
>       assert_equal(true, a.circumscribes?(2))
>       assert_equal(true, a.circumscribes?(9))
>       assert_equal(false, a.circumscribes?(10))
>       assert_equal(false, a.circumscribes?(11))
>     end
>   end
>
>   class LrgNumericTest < Test::Unit::TestCase
>     def test_include
>       a = (0...100000000)
>       assert_equal(true, a.include?(0))
>       assert_equal(true, a.include?(1000))
>       assert_equal(true, a.include?(1000000))
>       assert_equal(false, a.include?(100000000))
>       assert_equal(false, a.include?(Infinity))
>     end
>     def test_include_with_step
>       a = (0..100000000).x 5
>       assert_equal(true, a.include?(0))
>       assert_equal(true, a.include?(5))
>       assert_equal(false, a.include?(70007))
>       assert_equal(true, a.include?(5000005))
>       assert_equal(false, a.include?(Infinity))
>     end
>   end
>
>   class InfTest < Test::Unit::TestCase
>     def test_include?
>       a = (-Infinity..-3)
>       assert_equal(true, a.include?(-Infinity))
>       assert_equal(true, a.include?(-4))
>       assert_equal(true, a.include?(-3))
>       assert_equal(false, a.include?(-2))
>       assert_equal(false, a.include?(Infinity))
>       a = (-Infinity...-3)
>       assert_equal(true, a.include?(-Infinity))
>       assert_equal(true, a.include?(-4))
>       assert_equal(false, a.include?(-3))
>       assert_equal(false, a.include?(-2))
>       assert_equal(false, a.include?(Infinity))
>       a = (-3..Infinity)
>       assert_equal(false, a.include?(-Infinity))
>       assert_equal(false, a.include?(-4))
>       assert_equal(true, a.include?(-3))
>       assert_equal(true, a.include?(-2))
>       assert_equal(true, a.include?(Infinity))
>       a = (-Infinity..Infinity)
>       assert_equal(true, a.include?(-Infinity))
>       assert_equal(true, a.include?(-4))
>       assert_equal(true, a.include?(-3))
>       assert_equal(true, a.include?(-2))
>       assert_equal(true, a.include?(Infinity))
>       a = (-3..-2)
>       assert_equal(false, a.include?(-Infinity))
>       assert_equal(false, a.include?(-4))
>       assert_equal(true, a.include?(-3))
>       assert_equal(true, a.include?(-2))
>       assert_equal(false, a.include?(Infinity))
>     end
>   end
>
>    class OrdinalTest < Test::Unit::TestCase
>      def test_include
>        a = ('a'..'g')
>        assert_equal(false, a.include?(-Infinity))
>        assert_equal(true, a.include?('a'))
>        assert_equal(true, a.include?('c'))
>        assert_equal(false, a.include?('z'))
>        assert_equal(false, a.include?(Infinity))
>      end
>      def test_error
>        assert_raises(ArgumentError) {
>          a = (-Infinity..'z')
>        }
>      end
>    end
>
> --------------------
>
> Loaded suite range_test
> Started
> ......
> Finished in 0.024425 seconds.
>
> 6 tests, 65 assertions, 0 failures, 0 errors

-- 
( o _  カラチ
 //    trans.
/ \    transami@runbox.com

I don't give a damn for a man that can only spell a word one way.
-Mark Twain