A little algorithmic help requested

[David_A_Black3 (David A. Black)]

Hi --

"Jason Creighton" <androflux@softhome.net.remove.to.reply> schrieb im
Newsbeitrag
news:20040711153514.4b895d41.androflux@softhome.net.remove.to.reply...
>
> > 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"!

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. IMHO a solution in module Enumerable (i.e. a general solution)
should do better with respect to time and space.

Just for fun, here's a "purely functional" version, though not
suitable for Enumerable because it uses size, and not very robust
because it doesn't sort... but, like I said, just for fun

  def to_ranges
    values_at(*(0...size).find_all {|i|
                at(i) != at(i-1) + 1 }).zip(
    values_at(*(0...size).find_all {|i|
                at(i) != at(i+1) - 1 rescue true })).
      map {|a,b| Range.new(a,b) }
  end

(Annoyingly repetitve as to code... could of course be split out.)

David

···

On Mon, 12 Jul 2004, Robert Klemme wrote:

> On Sun, 11 Jul 2004 16:10:34 +0900, > > Hal Fulton <hal9000@hypermetrics.com> wrote:

--
David A. Black
dblack@wobblini.net

[Jason_Creighton3 (Jason Creighton)]

"Jason Creighton" <androflux@softhome.net.remove.to.reply> schrieb im
Newsbeitrag
news:20040711153514.4b895d41.androflux@softhome.net.remove.to.reply...
>
> > 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:

~/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)

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

if __FILE__ == $0
  require 'benchmark'
  Benchmark.bm(10) do |b|
    b.report("to_ranges") { (1..2**16).to_ranges }
    b.report("to_ranges2") { (1..2**16).to_ranges2 }
  end
end

Jason Creighton

···

On Mon, 12 Jul 2004 15:47:41 +0200, "Robert Klemme" <bob.news@gmx.net> wrote:

> On Sun, 11 Jul 2004 16:10:34 +0900, > > Hal Fulton <hal9000@hypermetrics.com> wrote:

[Robert]

"Jason Creighton" <androflux@softhome.net.remove.to.reply> schrieb im
Newsbeitrag
news:20040712105553.44b0cf99.androflux@softhome.net.remove.to.reply...

>
> "Jason Creighton" <androflux@softhome.net.remove.to.reply> schrieb im
> Newsbeitrag
> news:20040711153514.4b895d41.androflux@softhome.net.remove.to.reply...
> >
> > > 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

···

On Mon, 12 Jul 2004 15:47:41 +0200, > "Robert Klemme" <bob.news@gmx.net> wrote:
> > On Sun, 11 Jul 2004 16:10:34 +0900, > > > Hal Fulton <hal9000@hypermetrics.com> wrote: