By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
443,718 Members | 1,840 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 443,718 IT Pros & Developers. It's quick & easy.

Loading a big array on the heap

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
Share this Question
Share on Google+
5 Replies


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.
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" <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?

Nov 17 '05 #3

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?


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" <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).

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.