443,718 Members | 1,840 Online Need help? Post your question and get tips & solutions from a community of 443,718 IT Pros & Developers. It's quick & easy.

 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? Nov 17 '05 #1
5 Replies

 P: n/a "songie D" 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. Nov 17 '05 #2

 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" 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? Nov 17 '05 #3

 P: n/a can you post a more detailed example? "Alexander Grigoriev" 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" 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? Nov 17 '05 #4

 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" wrote in message news:%2****************@TK2MSFTNGP09.phx.gbl... can you post a more detailed example? "Alexander Grigoriev" 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" 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). Nov 17 '05 #5

 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. Nov 17 '05 #6

### This discussion thread is closed

Replies have been disabled for this discussion. 