From: "Simon Kröger" <SimonKroeger@...>
Date: 2005-08-07T04:18:19+09:00
Subject: Re: algorithm help


> To put some figures in here, I did a bit of benchmarking and indeed the 
> bitset version is quite slooooouw:
> 
> $ ruby ranges-2.rb
>                          user     system      total        real
> bitset               37.734000   0.000000  37.734000 ( 38.354000)
> inject-range          0.313000   0.000000   0.313000 (  0.318000)
> inject-array          0.156000   0.000000   0.156000 (  0.153000)
> inject-array-2        0.140000   0.000000   0.140000 (  0.140000)
> inject-array-map      0.204000   0.000000   0.204000 (  0.210000)
> 
> (Code attached)
> 
> Anyway, it was fun playing around with this. :-)
> 
> Kind regards
> 
>    robert

Nice one,

now we are getting some hard numbers to play with.

i added a larger range 1000..5000 to the test set which should come
closer to ara's problem at hand.

NUMBERS = [3, 4, 5, 6, 7, 8, 9, 15, 38, 39, 40, 41] +
	(1000..5000).to_a + [6789, 6790, 9998, 9999]

I get the following numbers:

                           user     system      total        real
bitset               79.047000   0.094000  79.141000 ( 80.407000)
inject-range         41.609000   0.328000  41.937000 ( 43.000000)
inject-array         17.219000   0.047000  17.266000 ( 17.296000)
inject-array-2       17.687000   0.031000  17.718000 ( 18.688000)
inject-array-map     16.797000   0.078000  16.875000 ( 16.906000)
to_ranges             0.453000   0.000000   0.453000 (  0.453000)

Interestingly this brings the bitset approach back in play, but it
also clearly shows what can be done with the right algorithm:

def to_ranges first, last
   if (NUMBERS[last] - NUMBERS[first]).abs==last-first
     return [[NUMBERS[first],NUMBERS[last]]]
   end
   r1 = to_ranges(first, (first+last)/2)
   r2 = to_ranges((first+last)/2+1, last)
   if (r1.last[1] - r2.first[0]).abs == 1
     r2[0] = [r1.last[0],r2.first[1]]
     r1.pop
   end
   r1 + r2
end

This would have been a nice quiz question, but i guess its worn
out by now.

cheers

Simon