Optimizing Array processing loop

Question

I am working a programming puzzle and I am a little baffled. The problem is count the number of intersections of disks on a 2 dimensional plan. x is always 0 and y is index into the array. The radius is the element is stored in the array element. Performance is fine with the number of elements a small number of elements, but with a large number of elements like 10,000,000 performance is bad. I am currently using 2 nested for loop to process the arrays.

I would appreciate any help someone might give. I am tied to data structures given to me and can not change them. The calculation if the disk intersects another since I am dealing with integers and the center points are on the same y axis.

Below is the code:

int number_of_intersections ( int A[], int n ) 
{
 int base = 0;
 int inc = 0;
 int intersect = 0;
 int maxrad = 0;
 int x;

 if (n>1)
 { 
  for (base=0;base<(n-1);base++)
  {
   inc = base+1;
   do
   { 
    if ( inc - base <= (A[base] + A[inc]))  
    {                                    
     intersect ++;
     if (!(intersect^10000000))   
     {
      return -1;
     }
    }
    inc ++;
   } while (inc < n);
  }
 }

 return intersect;
}

Thank you for your time

For starters, don't write if (!(intersect ^ 1000000)). Just write if (intersect == 10000000). It's way clearer. Also, can you provide some more context and examples here? What have you tried? Why didn't it work? — templatetypedef
– templatetypedef, Commented Jan 9, 2011 at 6:01
If x always equals 0 then its a 1-dimensional plane... sort of — Joe Phillips
– Joe Phillips, Commented Jan 9, 2011 at 6:10
your do-while loop is much more readable as for(inc=base+1; inc<n; ++inc) — Philip Potter
– Philip Potter, Commented Jan 9, 2011 at 6:44
I don't get that obfuscated code. :-) And what's the deal with that ^10000000? — Eiko
– Eiko, Commented Jan 9, 2011 at 8:33
Please improve the quality of your problem description. This is completely incomprehensible. First your problem seems just to be a problem of intervals on the real line if x is always 0. But even then how does a 1-dim array A transport the necessary information about tuples of y and radius? Is A supposed to be sorted in some way? If you really want to get rid of a quadratic algorithm you have to get things clean, specification and code. Don't use int as an all purpose data type. Indices should be size_t radii probably double or so. — Jens Gustedt
– Jens Gustedt, Commented Jan 9, 2011 at 9:17

Eiko · Accepted Answer · 2011-01-09 09:12:24Z

Your code smells like premature optimization.

Get rid of the outer if statement, as it won't help you much anyway (the outer loop won't get executed with n <= 1).

Remove that magic constant (10000000) in there and the (I suppose) bit-fiddling trick. It's difficult to read, not flexible at all (should at least be a constant variable), and the logic is poorly expressed by using xor instead of ==.

Maybe exchange your do-while loop with an easier to read for-loop. (as suggested by @Philip Potter)

Now your code would look much clearer while not being slower. Maybe you realize that now you already have saved some lines of code and some parenthesis, and you could probably remove some more.

Now with readable code you are finally open to the bigger optimization that was hidden before - please see other posts for that.

Note: Don't do clever optimization tricks early. They won't do you any good.

Edit: To make the point clear ;-)

int number_of_intersections (int A[], int n) 
{
     int intersect = 0;
     const int maxIntersections = 10000000;    

     for (int base = 0; base <  n-1; base++)
     {
        for(int inc = base+1; inc < n; inc++)
        { 
           if (inc - base <= A[base] + A[inc])  
           {                                    
              intersect ++;
              if (intersect == maxIntersections) return -1;
           }
        }
     }

     return intersect;
}

Bwmat · Accepted Answer · 2011-01-09 06:12:17Z

2

your approach is O(n^2) since you are testing each pair of discs, hence the bad speed with large numbers of discs.

I can't think of a way to get asymptotically better performance off the top of my head, but there is one optimization you can make.

say you are at element p, which has radius m. obviously, every disc located at p - m <= y <= p + m has its center covered by the disc at y = m. Therefore you only need to do any work for discs farther away than that.

answered Jan 9, 2011 at 6:12

Bwmat

4,7243 gold badges30 silver badges51 bronze badges

Comments

mcdowella · Accepted Answer · 2011-01-09 06:42:17Z

As pointed out in the comments, this is really a 1-dimensional problem. In fact, it is a problem about intersecting intervals, where the intervals [x, y] correspond to the lowest and highest x coordinates in a disk x = centre - radius and y = centre + radius.

Think about moving along the x and y points from left to right. You can do this without sorting by keeping two pointers to the disks, one for the x point and one for the y point. Use a data structure to keep track of disks under the current pointer. When you see an x point, recognise an intersection between than point's disk and all the current disks, and then make it a current disk. When you see a y point, remove that point's disk from the current disks.

Collectives™ on Stack Overflow

Optimizing Array processing loop

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related