CODEWITHSUNDEEP
c++calgorithmif-statement
SKPS
SKPS

Reputation: 5855

Need advice on Algorithm

I have a code where I use two different functions for 2D and 3D. In a for loop over the list of coordinates, I would like call the functions respectively by checking the dimensions. However, checking the dimension with if for every coordinate is very inefficient, since dimension check is only once needed (at the beginning of the code).

For your info, the 2D / 3D functions are in separate file and then list of coordinates are in a separate file.

Can anyone suggest a efficient way to call the appropriate function, by using only one check at the beginning of code for dimensions?

Pseudocode: file1.cpp

readcoordinates();  //store the coordinates info;
for(number of coordinates)
   checkfunction(coordinates[i]); //function in file2.cpp

file2.cpp

checkfunction(coordinates[i]){
   //requires dimension info here for complicated checking,
   // which cannot be explained here.
   // Since entire list of coordinates is same dimension, multiple if checks can be avoided here

}

Upvotes: 0

Views: 106

Answers (3)

Zac Howland
Zac Howland

Reputation: 15870

In addition to the other suggestions (and assuming you are using these for some sort of 2D vs 3D math), you could also just treat everything as a 3D vector (the 2D vectors would just have a 0 for the Z-coordinate). Then you are just implementing a single function, regardless of how many coordinates you have in your structure.

Upvotes: 0

Ben Voigt
Ben Voigt

Reputation: 283783

Make the number of dimensions a template parameter. This allows you to avoid code duplication, but the compiler will get rid of ALL the dimension checks, creating a version of the code for 2-D and a separate one for 3-D, both getting fully optimized.

You can't provide template parameters at runtime, so then you need a dispatch function that dynamically checks the dimension, once, and calls either the 2-D or 3-D template instance.

An alternative to if-else or switch in the dispatch function, is to use virtual dispatch (each virtual implementation then calls the right template instantiation to do the actual work).

Upvotes: 3

Edwin Buck
Edwin Buck

Reputation: 70949

In most situations like this, the key is to stop accessing your items through the List of all items. Lists don't maintain order, and that limits you to a lot of checking location to see if the item needs processing.

You could, for example use a tree of items, and then zero in on the first item within the desired range in the X axis, and the last item within the desired range on that X axis, and process all items "in between". With such a solution, you could maintain two ordered trees, on for the the X axis and one for the Y axis.

Or, you could build a data structure based on Geo-Hashing techniques.

In either case, you could filter out the items by coordinate quickly, and then pass them to other routines that don't do any coordinate based filtering (trusting that the filtering from outside is correct).

Upvotes: 1

Related Questions