A little algorithmic help requested...

[Jason Creighton]

Newsbeitrag

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

 

[Robert Klemme]

Newsbeitrag

Newsbeitrag

On Sun, 11 Jul 2004 16:10:34 +0900,

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

 

[Rob Partington]

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?

http://rjp.frottage.org/create_runs.txt

(uses only bash, not ruby, doesn't do any sorting at all,
copes with numbers from -1B to +1B)

Probably not ideal for your ruby program, though.