P: n/a

I am looking to write a very fast algorithm to merge ranges.
e.g. if it was input the following ranges (1,3), (4,6), (9, 12)
it should return exactly the same thing.
However if it's passed (1, 5), (3, 8), (10, 12) then it should return (1, 8), (10, 12).
for this i'm looking to load a big array onto the heap, use memset to
set the ranges, then read it back.
Technically, I would only need 1 bit for each valid number in the range (the maximum
any number in any range can be will be known). But in practice, I'm going to have to have
at least a byte, as it would remove the need for code to do individual bit settings.
So, would it be quicker to have bytes, or longs?  
Share this Question
P: n/a

"songie D" <an*******@discussions.microsoft.com> wrote in message
news:AE**********************************@microsof t.com... I am looking to write a very fast algorithm to merge ranges. e.g. if it was input the following ranges (1,3), (4,6), (9, 12) it should return exactly the same thing. However if it's passed (1, 5), (3, 8), (10, 12) then it should return (1,
8), (10, 12). for this i'm looking to load a big array onto the heap, use memset to set the ranges, then read it back. Technically, I would only need 1 bit for each valid number in the range
(the maximum any number in any range can be will be known). But in practice, I'm going
to have to have at least a byte, as it would remove the need for code to do individual bit
settings. So, would it be quicker to have bytes, or longs?
Who knows? On the one hand with bytes you have fewer memory accesses and
more cache hits, but on the other hand if there are nonaligned accesses of
the bytes then it might be slower.
Why not just typedef the numeric type and use that, then profile with
different types. For that matter, templatize the algorithm on the numeric
type.
S.  
P: n/a

This algorithm will be very suboptimal, with O(n) complexity, where 'n' is
total length of ranges or max span.
Better algorithm over a sorted sequence has O(m)*log(m) complexity (m*log(m)
is sort cost), where m is number of ranges, and doesn't depend on the range
length.
"songie D" <an*******@discussions.microsoft.com> wrote in message
news:AE**********************************@microsof t.com... I am looking to write a very fast algorithm to merge ranges. e.g. if it was input the following ranges (1,3), (4,6), (9, 12) it should return exactly the same thing. However if it's passed (1, 5), (3, 8), (10, 12) then it should return (1,
8), (10, 12). for this i'm looking to load a big array onto the heap, use memset to set the ranges, then read it back. Technically, I would only need 1 bit for each valid number in the range
(the maximum any number in any range can be will be known). But in practice, I'm going
to have to have at least a byte, as it would remove the need for code to do individual bit
settings. So, would it be quicker to have bytes, or longs?  
P: n/a

can you post a more detailed example?
"Alexander Grigoriev" <al***@earthlink.net> wrote in message
news:ek**************@TK2MSFTNGP11.phx.gbl... This algorithm will be very suboptimal, with O(n) complexity, where 'n' is total length of ranges or max span.
Better algorithm over a sorted sequence has O(m)*log(m) complexity
(m*log(m) is sort cost), where m is number of ranges, and doesn't depend on the
range length.
"songie D" <an*******@discussions.microsoft.com> wrote in message news:AE**********************************@microsof t.com... I am looking to write a very fast algorithm to merge ranges. e.g. if it was input the following ranges (1,3), (4,6), (9, 12) it should return exactly the same thing. However if it's passed (1, 5), (3, 8), (10, 12) then it should return
(1, 8), (10, 12). for this i'm looking to load a big array onto the heap, use memset to set the ranges, then read it back. Technically, I would only need 1 bit for each valid number in the range (the maximum any number in any range can be will be known). But in practice, I'm
going to have to have at least a byte, as it would remove the need for code to do individual
bit settings. So, would it be quicker to have bytes, or longs?
 
P: n/a

Well, think about it. How did you convert (1, 5), (3, 8), (10, 12) into (1,
8), (10, 12)? Did you take a piece of paper and make 12 boxes, then fill in
through 5, then 3 through 8, then 10 through 12, and then convert the boxes
back into ranges? Probably not. You probably used some brain shortcuts.
Convert those shortcuts into an algorithm.
"songie D" <so****@d.com> wrote in message
news:%2****************@TK2MSFTNGP09.phx.gbl... can you post a more detailed example?
"Alexander Grigoriev" <al***@earthlink.net> wrote in message news:ek**************@TK2MSFTNGP11.phx.gbl... This algorithm will be very suboptimal, with O(n) complexity, where 'n'
is total length of ranges or max span.
Better algorithm over a sorted sequence has O(m)*log(m) complexity (m*log(m) is sort cost), where m is number of ranges, and doesn't depend on the range length.
"songie D" <an*******@discussions.microsoft.com> wrote in message news:AE**********************************@microsof t.com... I am looking to write a very fast algorithm to merge ranges. e.g. if it was input the following ranges (1,3), (4,6), (9, 12) it should return exactly the same thing. However if it's passed (1, 5), (3, 8), (10, 12) then it should return (1, 8), (10, 12).  
P: n/a

In article <#D**************@TK2MSFTNGP09.phx.gbl>, so****@d.com
says... can you post a more detailed example?
How about a more detailed description instead?
Sort the ranges in order.
Step through the ranges, and if the end of one range is right before
the beginning of the next, merge the two. Repeat until end of
ranges.
If merging is slow, you may want to delay doing a merge until you
find a range this is not contiguous (e.g. if you find the first four
ranges are contiguous, the new range is the beginning of the first
and the end of the fourth).

Later,
Jerry.
The universe is a figment of its own imagination.   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 1320
 replies: 5
 date asked: Nov 17 '05
