[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Need help detecting overlapping ranges

Bryan Richardson

8/6/2008 6:49:00 PM

Hello all,

I am writing some code where I create a bunch of ranges, then at the end
I want to create new ranges out of any ranges that overlap one another.
For example, say I have the following ranges:

(1..5) (7..11) (22..29) (5..8)

Given the ranges above, I want to end up with the following ranges:

(1..11) (22..29)

Here is the code I've come up with so far (ranges is an array of ranges
similar to what I described above in my example):

ranges = @failed.outages
changes = true
while changes
changes = false
outages = ranges.collect { |range| range.to_a }
ranges.clear
while !outages.empty?
outage = outages.shift
outages.each do |n|
unless (outage & n).empty?
outage = (outage + n).uniq.sort
outages.delete(n)
changes = true
end
end
ranges << (outage.first..outage.last)
end
end
return ranges.sort { |a,b| a.first <=> b.first }

This code works, but it is *EXTREMELY* slow (my current array of ranges
is averaging out to ~24000 range elements). Anyone have an idea of how
to speed it up?

--
Thanks!
Bryan
--
Posted via http://www.ruby-....
17 Answers

Siep Korteling

8/6/2008 8:26:00 PM

0

Bryan Richardson wrote:
> Hello all,
>
> I am writing some code where I create a bunch of ranges, then at the end
> I want to create new ranges out of any ranges that overlap one another.
> For example, say I have the following ranges:
>
> (1..5) (7..11) (22..29) (5..8)
>
> Given the ranges above, I want to end up with the following ranges:
>
> (1..11) (22..29)
>
(...)
> This code works, but it is *EXTREMELY* slow (my current array of ranges
> is averaging out to ~24000 range elements). Anyone have an idea of how
> to speed it up?
>
> --
> Thanks!
> Bryan

Sets are usually much faster then large arrays and sets have a divide
method.

require 'set'
ranges=[(1..5),(7..11),(22..29),(5..8)]
set=Set.new
ranges.each do|range|
range.each do|el|
set<<el
end
end
sets = set.divide { |i,j| (i - j).abs == 1 } #straight from the
documentation!

p sets
#<Set: {#<Set: {27, 22, 28, 23, 29, 24, 25, 26}>, #<Set: {5, 11, 6, 1,
7, 2, 8, 3, 9, 4, 10}>}>

hth,

Siep

--
Posted via http://www.ruby-....

Stefan Lang

8/6/2008 8:40:00 PM

0

2008/8/6 Bryan Richardson <btrichardson@gmail.com>:
> Hello all,
>
> I am writing some code where I create a bunch of ranges, then at the end
> I want to create new ranges out of any ranges that overlap one another.
> For example, say I have the following ranges:
>
> (1..5) (7..11) (22..29) (5..8)
>
> Given the ranges above, I want to end up with the following ranges:
>
> (1..11) (22..29)
>
> Here is the code I've come up with so far (ranges is an array of ranges
> similar to what I described above in my example):
>
> ranges = @failed.outages
> changes = true
> while changes
> changes = false
> outages = ranges.collect { |range| range.to_a }
> ranges.clear
> while !outages.empty?
> outage = outages.shift
> outages.each do |n|
> unless (outage & n).empty?
> outage = (outage + n).uniq.sort
> outages.delete(n)
> changes = true
> end
> end
> ranges << (outage.first..outage.last)
> end
> end
> return ranges.sort { |a,b| a.first <=> b.first }
>
> This code works, but it is *EXTREMELY* slow (my current array of ranges
> is averaging out to ~24000 range elements). Anyone have an idea of how
> to speed it up?

I guess it's slow because it's doing many Range to Array conversions.
Here's a version that does no such conversions:

# Assumption: for every range: range.end >= range.begin
def overlap(ranges)
ranges = ranges.dup
new_ranges = []
until ranges.empty?
cur = ranges.pop
overlap = ranges.find { |range|
cur.member?(range.begin) || cur.member?(range.end) ||
range.member?(cur.begin) || range.member?(cur.end)
}
if overlap
new_begin = cur.begin < overlap.begin ? cur.begin : overlap.begin
new_end = cur.end > overlap.end ? cur.end : overlap.end
join = Range.new(new_begin, new_end)
ranges.map! { |range| range.equal?(overlap) ? join : range }
else
new_ranges << cur
end
end
new_ranges
end

(And in case Gmail messes up the formating:
http://pastecode.com/?show...)

So I've tried it only with the one example you've given and
I didn't actually benchmark it.

Stefan

ara.t.howard

8/6/2008 8:42:00 PM

0


On Aug 6, 2008, at 12:48 PM, Bryan Richardson wrote:

> Hello all,
>
> I am writing some code where I create a bunch of ranges, then at the
> end
> I want to create new ranges out of any ranges that overlap one
> another.
> For example, say I have the following ranges:
>
> (1..5) (7..11) (22..29) (5..8)
>
> Given the ranges above, I want to end up with the following ranges:
>
> (1..11) (22..29)
>
> Here is the code I've come up with so far (ranges is an array of
> ranges
> similar to what I described above in my example):
>
> ranges = @failed.outages
> changes = true
> while changes
> changes = false
> outages = ranges.collect { |range| range.to_a }
> ranges.clear
> while !outages.empty?
> outage = outages.shift
> outages.each do |n|
> unless (outage & n).empty?
> outage = (outage + n).uniq.sort
> outages.delete(n)
> changes = true
> end
> end
> ranges << (outage.first..outage.last)
> end
> end
> return ranges.sort { |a,b| a.first <=> b.first }
>
> This code works, but it is *EXTREMELY* slow (my current array of
> ranges
> is averaging out to ~24000 range elements). Anyone have an idea of
> how
> to speed it up?
>
> --
> Thanks!
> Bryan
> --
> Posted via http://www.ruby-....
>

this should be quite fast with a few constraints. the main thing is
that you do not have to convert ranges to detect the overlap nor to do
the merge.




cfp:~ > cat a.rb
def collapse_inclusive_integer *ranges
ranges.flatten!
ranges.compact!

ranges.each do |r|
raise ArgumentError, "exclusive range #{ range.inspect }" if
r.exclude_end?
raise ArgumentError, "non-integer range #{ range.inspect }" unless
Integer === r.begin and Integer === r.end
end

overlaps = lambda do |i,j|
a, b = ranges[i], ranges[j]
a.begin <= b.end and b.begin <= a.end
end

merge = lambda do |i,j|
a, b = ranges[i], ranges[j]
values = a.begin, a.end, b.begin, b.end
min, max = values.min, values.max
range = min .. max
src, dst = i < j ? [i,j] : [j,i]
ranges[src] = range
ranges.delete_at dst
range
end

loop {
catch('start over'){
size = ranges.size
size.times do |i|
size.times do |j|
next if i == j
if overlaps[i,j]
merge[i,j]
throw 'start over'
end
end
end
return ranges
}
}
end

ranges = 1..5, 7..11, 22..29, 5..8

p ranges
p collapse_inclusive_integer(ranges)





cfp:~ > ruby a.rb
[1..5, 7..11, 22..29, 5..8]
[1..11, 22..29]


a @ http://codeforp...
--
we can deny everything, except that we have the possibility of being
better. simply reflect on that.
h.h. the 14th dalai lama

Martin DeMello

8/6/2008 9:02:00 PM

0

On Wed, Aug 6, 2008 at 11:48 AM, Bryan Richardson
<btrichardson@gmail.com> wrote:
> Hello all,
>
> I am writing some code where I create a bunch of ranges, then at the end
> I want to create new ranges out of any ranges that overlap one another.
> For example, say I have the following ranges:
>
> (1..5) (7..11) (22..29) (5..8)
>
> Given the ranges above, I want to end up with the following ranges:
>
> (1..11) (22..29)

Bit busy at work, so I don't have time to play with code, but mostly
your algorithm is slow. This one should work better:

1. sort the array of ranges by startpoint
2. compare the first two ranges. if they overlap, merge them by
setting the second range equal to the merged range and the first to
nil
3. repeat with the next pair, and so on
4. compact the array

in action:

1..5, 5..8, 7..11, 22..29
nil, 1..8, 7..11, 22..29
nil, nil, 1..11, 22..29
no change
1..11, 22..29

Might be some corner cases I haven't taken care of but the basic
algorithm is O(n) and involves no range conversions.

martin

Bryan Richardson

8/6/2008 9:48:00 PM

0

Thanks to all who replied! I took the main advice of all of your posts
to be "don't convert ranges to arrays stupid!!!" and also "don't do this
recursively stupid!". :)

With that in mind, here's what I came up with (I didn't want to just
copy someone's code... I don't learn anything that way!) -- it seems to
be much faster:

def merge_outages
ranges = @failed.outages.sort { |a,b| a.first <=> b.first }
outages = Array.new
while !ranges.empty?
range = ranges.shift
loop do
if ranges.empty?
break
else
if (range.last + 1) >= ranges.first.first
range = (range.first..ranges.first.last)
ranges.shift
else
break
end
end
end
outages << range
end
return outages
end

What do you guys think of this approach? Am I overlooking something
that you guys suggested?

--
Thanks!
Bryan
--
Posted via http://www.ruby-....

David A. Black

8/6/2008 10:06:00 PM

0

Hi --

On Thu, 7 Aug 2008, Bryan Richardson wrote:

> Thanks to all who replied! I took the main advice of all of your posts
> to be "don't convert ranges to arrays stupid!!!" and also "don't do this
> recursively stupid!". :)
>
> With that in mind, here's what I came up with (I didn't want to just
> copy someone's code... I don't learn anything that way!) -- it seems to
> be much faster:
>
> def merge_outages
> ranges = @failed.outages.sort { |a,b| a.first <=> b.first }
> outages = Array.new
> while !ranges.empty?
> range = ranges.shift
> loop do
> if ranges.empty?
> break
> else
> if (range.last + 1) >= ranges.first.first
> range = (range.first..ranges.first.last)
> ranges.shift
> else
> break
> end
> end
> end
> outages << range
> end
> return outages
> end

I did something similar in trying to implement Martin's algorithm. I
haven't tested it beyond eyeballing the results for this one run:

ranges = [(1..5), (7..11), (22..29), (5..8)].sort_by {|r| r.first }
outages = [ranges.shift]

ranges.each do |r|
if outages[-1].include?(r.first)
outages[-1] = Range.new(outages[-1].first, r.last)
else
outages.push(r)
end
end

p outages


David

--
Rails training from David A. Black and Ruby Power and Light:
* Advancing With Rails August 18-21 Edison, NJ
* Co-taught by D.A. Black and Erik Kastner
See http://www.r... for details and updates!

Stefan Lang

8/6/2008 10:10:00 PM

0

2008/8/6 Martin DeMello <martindemello@gmail.com>:
> On Wed, Aug 6, 2008 at 11:48 AM, Bryan Richardson
> <btrichardson@gmail.com> wrote:
>> Hello all,
>>
>> I am writing some code where I create a bunch of ranges, then at the end
>> I want to create new ranges out of any ranges that overlap one another.
>> For example, say I have the following ranges:
>>
>> (1..5) (7..11) (22..29) (5..8)
>>
>> Given the ranges above, I want to end up with the following ranges:
>>
>> (1..11) (22..29)
>
> Bit busy at work, so I don't have time to play with code, but mostly
> your algorithm is slow. This one should work better:
>
> 1. sort the array of ranges by startpoint
> 2. compare the first two ranges. if they overlap, merge them by
> setting the second range equal to the merged range and the first to
> nil
> 3. repeat with the next pair, and so on
> 4. compact the array
>
> in action:
>
> 1..5, 5..8, 7..11, 22..29
> nil, 1..8, 7..11, 22..29
> nil, nil, 1..11, 22..29
> no change
> 1..11, 22..29
>
> Might be some corner cases I haven't taken care of but the basic
> algorithm is O(n) and involves no range conversions.

It's O(n), but only if you write a radix sort to sort the ranges ;-)

Stefan

Martin DeMello

8/6/2008 10:21:00 PM

0

On Wed, Aug 6, 2008 at 3:09 PM, Stefan Lang
<perfectly.normal.hacker@gmail.com> wrote:
> 2008/8/6 Martin DeMello <martindemello@gmail.com>:
>>
>> Might be some corner cases I haven't taken care of but the basic
>> algorithm is O(n) and involves no range conversions.
>
> It's O(n), but only if you write a radix sort to sort the ranges ;-)

Doh :)

m.

Bryan Richardson

8/6/2008 10:25:00 PM

0

Hi David,

I like the conciseness of your code, but I think it only works for when
the end of one range is the same as the beginning of another. I need to
also handle the times when ranges overlap more than that (i.e. 1..5,
3..6 -> 1..6). Thanks for thinking about this!

--
Thanks!
Bryan

David A. Black wrote:
> Hi --
>
> On Thu, 7 Aug 2008, Bryan Richardson wrote:
>
>> outages = Array.new
>> break
>> end
>> end
>> end
>> outages << range
>> end
>> return outages
>> end
>
> I did something similar in trying to implement Martin's algorithm. I
> haven't tested it beyond eyeballing the results for this one run:
>
> ranges = [(1..5), (7..11), (22..29), (5..8)].sort_by {|r| r.first }
> outages = [ranges.shift]
>
> ranges.each do |r|
> if outages[-1].include?(r.first)
> outages[-1] = Range.new(outages[-1].first, r.last)
> else
> outages.push(r)
> end
> end
>
> p outages
>
>
> David

--
Posted via http://www.ruby-....

ara.t.howard

8/6/2008 10:27:00 PM

0


On Aug 6, 2008, at 3:47 PM, Bryan Richardson wrote:

> Am I overlooking something
> that you guys suggested?


this_will_break_it = 0 ... 42


a @ http://codeforp...
--
we can deny everything, except that we have the possibility of being
better. simply reflect on that.
h.h. the 14th dalai lama