High speed solution to cycle through all combinations of different variables with start step stop scheme (C++)

Question

I am looking for a high speed solution to cycle a function with all combinations of different variables with start step stop scheme. Only at run-time is it known which variables are activated for the combination. (use = false/true).

A possible Solution can using recursion or back-tracking but that is too "slow" for the application.

For me the challenge is:

• High Performance! No use of recursion or back-tracking. Maybe a fast iterative solution?
• handle double and int datatypes.
• handle that only at run-time is it known which variables are activated for the combination. (use = false/true)
• handle that only at run-time is it known start/step/stop for the combination.
• The funktion use the normal values (e.g. i1_value). During the cycles, the values are changed through the combinations (if use = true).

How could a solution look like?

In this Example, the possible combinations of all active variables is 10*11*21 = 2310 In real there are more Variables and much more possible combinations, maybe up to several millions (the reason for need a high performance solution).

int i1_use = true;
int i1_value = 1; // the normal value that the function use 
int i1_start_value = 1;
int i1_step_value = 2;
int i1_stop_value = 20;
// 1,3,5,7,9,11,13,15,17,19 
// -> gives 10 different values

int i2_use = false;
int i2_value = 100; // the normal value that the function use 
int i2_start_value = 1000;
int i2_step_value = 500;
int i2_stop_value = 3000;
// -> use = false! no combination!

double d1_use = true;
double d1_value = 1.234; // the normal value that the function use 
double d1_start_value = 0;
double d1_step_value = 0.02;
double d1_stop_value = 0.2;
// 0,0.02,0.04,0.06,0.08,0.1,0.12,0.14,0.16,0.18,0.2  
// -> gives 11 different values

double d2_use = true;
double d2_value = 10; // the normal value that the function use 
double d2_start_value = 10;
double d2_step_value = 0.5;
double d2_stop_value = 20;
// 10,10.5,11,11.5,12,12.5,13,13.5,14,14.5,15,15.5,16,16.5,17,17.5,18,18.5,19,19.5,20 
// -> gives 21 different values

// All combinations 10*11*21 = 2310

Answer 1

First of all it would be reasonable to combine the variables into a struct. But assuming the rest of the code stays as it is, I'd suggest to create a helper construct anyways:

// an interface to use in vector
class CombinatorInterface {
   public:
   virtual bool nextValue() = 0;
};

// and template implementation for different types (int, float, etc.)
template <typename T>
class Combinator: public CombinatorInterface {
    public:
    Combinator(bool inUse, T currentValue, T startValue, T stepValue, T stopValue) :
      _inUse{inUse},
      _currentValue{currentValue},
      _startValue{startValue},
      _stepValue{stepValue},
      _stopValue{stopValue}
    {}


    // Now this is overly simplified, as you might need better error checks and maybe different approaches for integral and float types
    bool nextValue() override {
        if (_inUse == false) {
            return false;
        }

        if (_currentValue < _stopValue) {
            _currentValue += _stepValue;
            return true;
        } else {
            return false;
        }
    }

    private:
    bool& _inUse;
    T& _currentValue;
    T& _startValue;
    T& _stepValue;
    T& _stopValue;
};

And you can use this construct then in a code like:

std::vector<CombinatorInterface*> v;
v.push_back(new Combinator<int>(i1_use , i1_value, i1_start_value, i1_step_value , i1_stop_value));
    // more like this
    v.push_back(new Combinator<double>(d2_use, d2_value, d2_start, d2_step_value, d2_stop_value));

    bool permutationAvailable = true;
    do {
        permutationAvailable = false;
        for (auto i: v) {
            if (i->nextValue()) {
                permutationAvailable = true;
                break;
            }
        // do your measurements for every iteration
        }
    } while(permutationAvailable);
    // do the part after there are no more iterations

Now this will use address_size * parameters * 5 memory, which can be eliminated if you use only one set of variables, i.e. use the same vector in the entire code.

Another overhead is the polymorphic base, which will cause an additional address lookup for every nextValue() call. Otherwise this will be a plain brute force iteration.

Answer 2

From what is mentioned in the questions and comments, I assume that calling the function will take rather long, i.e., longer than evaluating if-conditions or adding some ints/doubles. Also, if this would not be the case I don't see why it would be important to improve efficiecy for "just" million of calls.

For a brute force approach, you could first create a template struct to encapsulate start, stop and stepping parameters:

template<typename T>
struct loop_variables
{
    T Start;
    T Stop;
    T Stepping;
}

As already mentioned in the comments, you don't really need the bool variables. You can write for-loops over your parameters without them:

loop_variables<int> i1;
i1.Start = 1
i1.Stop = 20;
i1.Stepping = 2;

// if Stop == Start the loop will only be executed once for this value!
loop_variables<int> i2;
i2.Start = 5;
i2.Stop = 5;
i2.Stepping = 0;

// Similar initialization of double parameters ...

for (int i=i1.Start; i<=i1.Stop; i+=i1.Stepping)
{
    for (int j=i2.Start; j<=i2.Stop; j+=i2.Stepping)
    {
        for (double x=d1.Start; x<=d1.Stop; x+=d2.Stepping)
        {
            for (double y=d2.Start; y<=d2.Stop; y+=d2.Stepping)
            {
                 // call function and store the parameter set (i, j, x, y)
                 // if the result is larger than the previous result
             }
         }
     }
}

If you are unsure about the performance you could use either a profiling tool to check which part of your code is taking the most time, or you could use a debugger for that (link)

About your insistence on a brute force approach: while I can imagine a function where it is required for the integer parameters, I cannot see the same beeing true for your double parameters. Numerical optimization methods typically require a function to be smooth. Some of the methods (e.g., gradient decent) can only find local maxima and thus work best if your function only has one maximum. However there are also methods wich will find the global maximum in the presence of several other local maxima (e.g. Markov Chain Monte Carlo). So if your function has some smoothness in the double parameters (i.e., no (large) jumps between (slightly) different parameters you could use a hybrid approach where you go through you integer parameters with brute force but use an optimization algorithm for the double parameters. This could save you a lot of unnecessary function calls.

On the other hand, if your function is not smooth your brute force grid approach will most likely also fail, since the optimum could very well be at double parameters you did not try due to your stepping parameters.