|We don't bite newbies here... much|
Re: Optimizing a double loopby moritz (Cardinal)
|on Jun 03, 2010 at 12:17 UTC||Need Help??|
The best way to speed up this loop is not to execute it.
Yes, I'm serious. Depending on your actual problem, there might be a way around it.
If you read abut inversion lists, you find that this idea can be generalized to overlapping lists.
Assume you have the ranges 10-50 and 20-100; You mark each start of a range with a positive number, and each end of range by a negative number. So 1-50 and 20-100 would translate to
That way you only store two integers for a large range.
If you want to know how many ranges overlap at a given point, say at 30, you just traverse the array from left to right up to abs($_) <= 30, and count how many positive and how many negative numbers you have encountered; the difference is the number of overlapping ranges.
You can also cache such numbers as long as the array doesn't change, to avoid having it to iterate it from the beginning every time.