From: Robert Klemme <bob.news@...>
Date: 2004-07-13T17:22:23+09:00
Subject: Re: A little algorithmic help requested...


"Jason Creighton" <androflux@softhome.net.remove.to.reply> schrieb im
Newsbeitrag
news:20040712105553.44b0cf99.androflux@softhome.net.remove.to.reply...
> On Mon, 12 Jul 2004 15:47:41 +0200,
> "Robert Klemme" <bob.news@gmx.net> wrote:
>
> >
> > "Jason Creighton" <androflux@softhome.net.remove.to.reply> schrieb im
> > Newsbeitrag
> > news:20040711153514.4b895d41.androflux@softhome.net.remove.to.reply...
> > > On Sun, 11 Jul 2004 16:10:34 +0900,
> > > Hal Fulton <hal9000@hypermetrics.com> wrote:
> > >
> > > > Here's a problem my tired brain is having trouble with.
> > > >
> > > > Given a sorted array of integers, convert them into as many
> > > > ranges as possible (ranges of three or more).
> > > >
> > > > Example:
> > > > [1,2,3,4,6,7,8,11,12,15,16,17] ==> [1..4,6..8,11,12,15..17]
> > > >
> > > > How would *you* do this?
> > >
> > > Here's one that doesn't follow that "need at least three of more"
> > > limitation, but it's how *I* would do it, because it returns an
array of
> > > *only* ranges, which seems like it would be more fun to deal with
that a
> > > mix of ranges and numbers.
> > >
> > > module Enumerable
> > >   def to_ranges
> > >     ranges = Array.new
> > >     self.sort.each do |e|
> > >       if ranges[-1] == nil or ranges[-1].end.succ != e
> > >         ranges << Range.new(e,e)
> > >         next
> > >       end
> > >       ranges[-1] = Range.new(ranges[-1].begin, e)
> > >     end
> > >     return ranges
> > >   end
> > > end
> >
> > Nice and short, although I'd use "else" instead of "next"! :-)
>
> Oh, right, that would be easier. :)
>
> > However, there is a performance drawback: you recreate ranges all over
> > again.  In the worst case of an array that contains all numbers from 1
to
> > 1000 you create 999 Range instances and keep only one of them.  That's
not
> > efficient.
>
> I realized I was doing this, but I didn't think the performance hit
> would be that much. But doing it a nicer was is much faster:

See? :-)

> ~/prog/rb$ ruby range-problem.rb
>                 user     system      total        real
> to_ranges   2.340000   0.000000   2.340000 (  2.338682)
> to_ranges2  0.410000   0.000000   0.410000 (  0.400007)

That's quite some difference.  Wow!

> range-problem.rb:
> #! /usr/bin/ruby -w
>
> # NOTE: to_ranges assumes sorted object.
>
> module Enumerable
>   def to_ranges
>     ranges = Array.new
>     self.each do |e|
>       if ranges[-1] == nil or ranges[-1].end.succ != e
>         ranges << Range.new(e,e)
>       else
>         ranges[-1] = Range.new(ranges[-1].begin, e)
>       end
>     end
>     return ranges
>   end
>
>   def to_ranges2
>     ranges = Array.new
>     low, high = nil, nil
>     self.each do |e|
>       if low == nil
>         # First item in collection
>         low, high = e,e
>       elsif high.succ != e
>         # We hit something out of sequence
>         ranges << Range.new(low,high)
>         low, high = e, e
>       else
>         high = e
>       end
>     end
>     ranges << Range.new(low,high)
>     return ranges
>   end
> end

Now you've implemented it basically the same way I did (as far as I
remember). :-)  Thanks for the measuremets!

Regards

    robert