Iteration and recursion

[D_Drmmr]

I think that it realizes the behaviour of nested loops.

Example:
For x For y For z -> variablesVector[x,y,z]
Domain for each variable -> Data
for x in subset(Data)
   for y in subset(Data)
      for z in subset (Data)
        do (x,y,z)

Not exactly, since what you've shown uses the same domain for each variable. IOW, 'Data' is the domain for all variables, not for each variable.

Do you have a suggestions about how can I do to reduce the complexity of huge number of recursive calls?

What do you mean with "complex"? The design suggested by JohnW is probably the least complex, since all the iteration logic is encapsulated and separate from the logic in the inner loop's body.

[nuzzle]

My code does the following operations.

Present the problem and your iterative solution instead.

Are you performing restructuring operations on "variablesVector" in the iterative solution? If not, as I've said, you don't have to do it in the recursive solution either since recursion here is introduced for the sole purpose of making the iterative solution more flexible. It's a completely mechanical procedure once the iterative solution is known.

If you want a fruitful discussion of your problem; How to arrive at a flexible solution; How to make the solution computationally less complex; You got to tell us what you're actually trying to do. As it stands you're in the way, obscuring the sight of people who could help you.

[erotavlas]

Present the problem and your iterative solution instead.

Are you performing restructuring operations on "variablesVector" in the iterative solution? If not, as I've said, you don't have to do it in the recursive solution either since recursion here is introduced for the sole purpose of making the iterative solution more flexible. It's a completely mechanical procedure once the iterative solution is known.

If you want a fruitful discussion of your problem; How to arrive at a flexible solution; How to make the solution computationally less complex; You got to tell us what you're actually trying to do. As it stands you're in the way, obscuring the sight of people who could help you.

My original problem is to evaluate a mathematical expression like "For each x, For each y ... For each z F(x,y,...,z)" where x,y,...,z are the variables while the F(x,y,...,z) is the function.
I know only at run time the number of variables because the expression is read from file. So I must do a recursive function, there is no another way.
I would like to know how can I get the best performance from my code, for this purpose I have posted a question in this forum.

[JohnW@Wessex]

I know only at run time the number of variables because the expression is read from file. So I must do a recursive function, there is no another way.

Are each of your loops separate or are they nested?

[erotavlas]

Are each of your loops separate or are they nested?

The loops are nested

[D_Drmmr]

My original problem is to evaluate a mathematical expression like "For each x, For each y ... For each z F(x,y,...,z)" where x,y,...,z are the variables while the F(x,y,...,z) is the function.

This description is more general than the algorithm you described. Specifically, in this description the domain of each variable is independent, whereas in your algorithm all variables have the same domain.

So I must do a recursive function, there is no another way.

Not true. See the link provided by JohnW earlier for a solution that doesn't involve recursive functions.

I would like to know how can I get the best performance from my code, for this purpose I have posted a question in this forum.

You should first try to find a solution that works. As it stands you don't have that, which means that talking about performance is quite useless.
Second, you should critically evaluate to what extend the performance of the loops matter. If F is a moderately complex function, then the time spend incrementing the loop counter is likely to be insignificant. On the other hand, if this is significant then it is likely that F is such a simple function that you can gain more by simplifying the entire code (i.e. working out some of the loops) than by focusing on code optimizations.

So my advice would be:
1. make something that works
2. measure the performance of the loops compared to the execution of the inner-loop function(s)
3. optimize where needed
4. (implied) verify that your optimized code is still correct

[JohnW@Wessex]

The loops are nested

Then the link I gave you would suffice, with no recursion.

If you want a templated version of the algorithm, with an example of use, I posted this a while ago.
http://www.codeguru.com/forum/showpo...48&postcount=9

[erotavlas]

have thought about the your templatized solution. It's a good idea, but I don't know if I can use in my case. I have to iterate through a set of data. Each variable gets a value from a set of data. The variables can get a subset of the values from the set of data. My set of data is compound by user defined type (strings plus value).

typedef struct {
string name;
float value;
} singleData;

My set of data is compound by a map<string, vector<singleData> >. Where string is the name of subset and the vector<singleData> is the vector of the elements.
The my nested loops (for x, for y, for z) can get the values from different subsets depending on their domain membership.
How can I control the subset of the data in which I would like to scan. How can I do it?

void Iterate(vector<pair<string, string> > variablesVector, map<string, vector<singleData> >* data) 
{

// for each variables
for (variablesVector::const_iterator it = variablesVector.begin(); it != variablesVector.end(); ++i)
{
	// the first element is the name of the variables, the second is the domain
	pair<string, string> element = *it;
	
	// get the subset of the data	
	vector<singleData> temp = data->GetVector(element.second);

	// how can I create the Multiloop??? Multiloop<vector<singleData> >
		
}

}

The code is not tested and so doesn't compile.

PS
I have copied and pasted your code. But I get a problem with all the statements throw exception.

error: no matching function for call to ‘std::exception::exception(const char [53])’
note: candidates are: std::exception::exception()
                      std::exception::exception(const std::exception&)

[laserlight]

I have copied and pasted your code. But I get a problem with all the statements throw exception.

Rather unfortunately, it looks like JohnW@Wessex's code relies on an extension to the standard library: the constructor of std::exception does not have the parameter that JohnW@Wessex's code assumes it does. Luckily, there is an easy fix: #include <stdexcept> and change the use of std::exception to std::logic_error, std::runtime_error, or some other more specific exception derived from one of those two.

[JohnW@Wessex]

Rather unfortunately, it looks like JohnW@Wessex's code relies on an extension to the standard library: the constructor of std::exception does not have the parameter that JohnW@Wessex's code assumes it does.

I didn't know that!

[nuzzle]

for this purpose I have posted a question in this forum.

Sure but since you're playing this "quess my problem" game no one can help you for real.

For the umpty-umpth time. Post your iterative solution for a limited number of variables, say F(x,y,z), and you'll get help.

What's holding you back? You have no iterative solution or is it some big secret?

[erotavlas]

Hi,

I have not a secret, but only a difficult problem. I don't know how can I use the templatized nested loops version for my problem.
I have read a book about data and algorithms and I have found a method to enumerate all the elements in a set. This is the same of my problem where instead a nested loops, I have only one (yes only one) loop and at each step I compute the values for each variable.

This is my code and it works. Now I don't know how can I convert it into nested loops...but it is not a big problem even if the nested loops version is more elegant.

std::vector<std::pair<std::string, int> > variablesVector;

    std::pair<std::string, int> element1("x", 2);
    std::pair<std::string, int> element2("y", 2);
    std::pair<std::string, int> element3("z", 2);

    variablesVector.push_back(element1);
    variablesVector.push_back(element2);
    variablesVector.push_back(element3);


    unsigned long dimension = 1;

    for (std::vector<std::pair<std::string, int> >::const_iterator it = variablesVector.begin(); it != variablesVector.end(); ++it)
    {
        dimension *= it->second;
    }

    // reverse the order of the vector of the variables
    reverse(variablesVector.begin(), variablesVector.end());
   
    for (unsigned long i = 0; i < dimension; ++i)
    {
        std::vector<std::pair<std::string, int> > variablesIndex;
        int temp = 0;

        // loop over the vector of the variable
        for (int j = 0; j < variablesVector.size(); ++j)
        {
            if (j == 0)
            {
                // first variable, initialization
                variablesIndex.push_back(std::pair<std::string, int> (variablesVector[j].first, i % variablesVector[j].second));
                temp = i / variablesVector[j].second;

            }
            else if (j < variablesVector.size())
            {
                variablesIndex.push_back(std::pair<std::string, int> (variablesVector[j].first, temp % variablesVector[j].second));
                temp = temp / variablesVector[j].second;
            }
           
            if (i == 0)
            {
                std::cout << variablesVector[j].first << " ";
            }

        }

        if (i == 0)
            std::cout << std::endl;

        for (int k = 0; k < variablesIndex.size(); ++k)
        {
            std::cout << variablesIndex[k].second << " ";
        }
        std::cout << std::endl;
	// now here I can use the variables index to the second step of my problem
			      
    }

The second step is to use the variablesIndex vector to search inside the data map<string, vector<singleData> >* data and evaluate the function.