CODEWITHSUNDEEP
calgorithm
highlander
highlander

Reputation: 9

Optimizing Array processing loop

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

Upvotes: 0

Views: 300

Answers (3)

Eiko
Eiko

Reputation: 25642

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;
}

Upvotes: 4

mcdowella
mcdowella

Reputation: 19621

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.

Upvotes: 0

Bwmat
Bwmat

Reputation: 4694

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.

Upvotes: 2

Related Questions