-
Iteration and recursion
Hi,
I have to write a code with a iteration paradigm or with a recursion paradigm. I think that the first one is the best for performance even if it require more lines of code. But I don't know if I'm able to write a code that uses it.
I have a vector of variables and so I know its dimension. For every variable I have to do a loop. Each loop must be nested inside the previous one. I have to create the loop on the fly because I don't know the dimension of the vector at compile time i.e. the vector can have different dimension. How can I do it?
For instance
(vector [x,y,z] ->
for(x) {
for (y) {
for (z) { }
}
})
The language is C++
-
Re: Iteration and recursion
pass in the x,y,z sizes on the interface and generally you roll down and in
Code:
void SortVectors( vector [x,y,z], unsigned short xsize, unsigned short ysize, unsigned short zsize){
unsigned short x, y, z;
for (z = 0; z < zsize; z++) {
for (y = 0; y < ysize; y++) {
for (x = 0; x < xsize; x++) {
// do whatever with vector[x,y,z]
}
}
};
-
Re: Iteration and recursion
I'm sorry if my explanation is not good enough. I have to make an arbitrary number of nested loops. I would like to know if the only way is the recursion paradigm.
-
Re: Iteration and recursion
Perhaps you need to explain what you are trying to do there are any number of ways to recurse and all have pro's and con's
perhaps the simplist recursion is the factorial recurse
Code:
unsigned int factorial (unsigned int a)
{
if (a == 1) return 1;
else {
a *= factorial(a-1);
return a;
}
};
if you plug in a value the procedure calls itself over and over recursing downwards
Look at entering 4 in the above it loops thru itself 4 times
result = factorial(4) * factorial(3) *factoria(2) * factorial(1);
The function basically calls itself with its current value-1
Normal sorting is another example but usually we use something like quicksort which is a divid and conquer rather than a full blind manual recursion because of speed.
-
Re: Iteration and recursion
Extendending from the previous post what would a quick sort of vertex3D look like ..
Code:
/*-COORD_TYPE----------------------------------------------------------------
Units your 3d vertex points are in typically shorts, ints, or doubles.
---------------------------------------------------------------------------*/
typedef double COORD_TYPE; // For our example we are using doubles
/*-VERTEX3D------------------------------------------------------------------
3D vertix record structure defined
---------------------------------------------------------------------------*/
typedef struct Vertex3D {
COORD_TYPE x; // Vertex x co-ord
COORD_TYPE y; // Vertex y co-ord
COORD_TYPE z; // Vertex z co-ord
} VERTEX3D, *PVERTEX3D;
/*-Vswap3D---------------------------------------------------------------------
Swaps the two given 3D vertexes around v1 and v2
----------------------------------------------------------------------------*/
static void Vswap3D (PVERTEX3D* v1, PVERTEX3D *v2){
PVERTEX3D Temp;
Temp = *v1; // Hold current v1 vertex
*v1 = *v2; // Transfer v2 to v1
*v2 = Temp; // Set v2 to the held old v1 value
};
/*-partition3D_with_random------------------------------------------------------
Partitions the 3D vertex array with randomness
----------------------------------------------------------------------------*/
static short partition3D_with_random(PVERTEX3D list[], short l, short h){
short i;
short p; /* pivot element index */
short firsthigh; /* divider position for pivot element */
p = l + (short)(rand() % (int)(h - l + 1)); // Random partition point
Vswap3D(&list[p], &list[h]); // Swap the values
firsthigh = l; // Hold first high value
for (i = l; i < h; i++)
// This is what we are sorting based on
// .. the following line we are sorting based on vertex x value
if(list[i]->x < list[h]->x) { // Value at i is less than h
Vswap3D(&list[i], &list[firsthigh]); // So swap the value
firsthigh++; // Incement first high
}
Vswap3D(&list[h], &list[firsthigh]); // Swap h and first high values
return(firsthigh); // Return first high
}
/*-quicksort3D_random---------------------------------------------------------
Quick sort 3D veretex with random partition
----------------------------------------------------------------------------*/
static void quicksort3D_random(PVERTEX3D list[], short l, short h){
short p; /* index of partition */
if ((h - l) > 0) {
p = partition3D_with_random(list, l, h); // Partition list
quicksort3D_random(list, l, p - 1); // Sort lower partion
quicksort3D_random(list, p + 1, h); // Sort upper partition
};
};
The code itself is remarkable simple it partitions a list and sorts by calling iteself over and over.
The key two the code is we have a swap routine that swaps two vertex points.
The key to what we are sorting is given by the one line
// This is what we are sorting based on
// .. the following line we are sorting based on vertex x value
if(list[i]->x < list[h]->x)
As you can see the simple test above is based on just the x value of two vertexes so the sort will be done so the vertexes in the array will come out smallest x to largest x
You could have sorted on a euclidean distance for example based on some distance from point (P)
Code:
/*-Distance3D----------------------------------------------------------------
Return euclidian distance between the two vertex3D points
-------------------------------------------------------------------------------*/
double Distance3D(PVERTEX3D v1, PVERTEX3D v2){
double dx, dy, dz;
dx = v2->x - v1->x; // Diff x
dy = v2->y - v1->y; // Diff y
dz = v2->z - v1->z; // Diff z
if ((dx == 0.0) && (dy == 0.0) && (dz==0.0)) // If diff's are zero
return (0.0); // Distance is zero
return (sqrt(dx*dx + dy*dy + dz*dz)); // Calculate the 3D distance
};
// Now if we change the sort equality test to
if( Distance3D(list[i], P) < Distance3D(list[h], P))
What we will get is a sort of the array of vertexes based upon that which is closest to point P
Is that the sort of thing you are looking for?
-
Re: Iteration and recursion
Quote:
Originally Posted by
erotavlas
I'm sorry if my explanation is not good enough. I have to make an arbitrary number of nested loops. I would like to know if the only way is the recursion paradigm.
Recursion is never the only way. However, sometimes it may be the clearest.
When you use recursion, you're effectively using the runtime stack to maintain some state for you. If you want, you can create a stack explicitly for this purpose without using recursion.
-
Re: Iteration and recursion
Thank you for the answers.
I have read this article http://www.codeguru.com/cpp/cpp/algo...nt.php/c15111/ and now I think that first I will make a recursive version of the my algorithm and after I will try to convert it in compile time version (template form) to improve the performance.
As I said in the previous post, I have to scan a vector of variables v = [x,y,z] and for each variable I have to do a for loop. The number of nested loops are equal to the number of the variables. Inside the innermost loop I have to make some operation. A snippet of my algorithm is the following.
Code:
void Recurse(const vector<string>& variablesVector)
{
// terminate recursion
if (variablesVector.size() == 0)
{
// do some operations
return;
}
// loop for the variable in the data
for ()
{
// recursive step - remove the front variable
Recurse(variablesVector.erase(variablesVector.begin(), variablesVector.begin()+1));
}
}
void Do(const vector<string>& variablesVector)
{
Recurse(variablesVector);
}
Is this code doing the arbitrary nested loops as I want?
-
Re: Iteration and recursion
-
Re: Iteration and recursion
Quote:
I don't understand your problem and I doubt anyone else does too.
Lets assume you have exactly 3 "dimensions" known at compiletime. What would an iterative solution look like?
I repeat again that I don't know the dimension at compile time. If I knew the dimension I would make a sufficient number of nested loops. I have a vector of variables and its dimension is only known at runtime.
I would like to rewrite my recursive algorithm into the template version as specified here http://www.codeguru.com/cpp/cpp/algo...nt.php/c15111/, but this is a secondary problem related only to the performance.
Quote:
Removing elements at the front of a vector is expensive and should be avoided. If you need to do this use a queue instead.
The vector is not so big, it will be in worst case about 50 elements.
-
Re: Iteration and recursion
Quote:
Originally Posted by
erotavlas
The vector is not so big, it will be in worst case about 50 elements.
The admonition against removing elements from the front stands. You should test a std::deque which has a pop_front() and push_front() function but otherwise an essentially identical interface to std::vector, and see if you get better performance with that.
-
Re: Iteration and recursion
Quote:
Originally Posted by
erotavlas
I repeat again
There's no use in repeating yourself because it doesn't become any clearer exactly what your problem looks like. If you want help I suggest you instead present an iterative solution to your problem with a fixed "dimension" say 3. You don't have to put in any detailed calculations but the structure of the algorithm must be visible.
In principle it's very easy to turn a fixed number of nested loops into a variable number of nested loops using recursion. The recursive method performs one loop which is then called recursively down to the wanted neesting depth. But as I said, it's not very clear what your problem looks like.
Also note that you cannot use templates if you don't know the "dimension" at compiletime. Templates will allow you to parametrize the number of nested loops but you still have to decide how many loops you want at compiletime.
Finally if you don't have to remove elements from the vector in the iterative solution you don't have to do it in the recursive.
Quote:
The vector is not so big, it will be in worst case about 50 elements.
If this means your algorithm is going to have up to 50 nested loops then it's highly likely you're approaching the problem from the wrong angle. Even if the loops go from 0 to 1 only the innermost loop will run 2^50 times which is 10^15 approximately. Your program will run for years.
-
Re: Iteration and recursion
Quote:
Originally Posted by
erotavlas
See nuzzles remark about compile vs run time. The only way you can use templates would be to generate code for a set of possible recursion depths (e.g. from 1 to 50), which is likely to cause huge amounts of code bloat. I doubt this is worth the performance gain (if it would achieve any gain at all).
Quote:
Originally Posted by
erotavlas
Code:
void Recurse(const vector<string>& variablesVector)
{
// terminate recursion
if (variablesVector.size() == 0)
{
// do some operations
return;
}
// loop for the variable in the data
for ()
{
// recursive step - remove the front variable
Recurse(variablesVector.erase(variablesVector.begin(), variablesVector.begin()+1));
}
}
void Do(const vector<string>& variablesVector)
{
Recurse(variablesVector);
}
Is this code doing the arbitrary nested loops as I want?
The code no, because it won't compile. But the structure/algorithm looks ok to me. Note that you need to copy the function argument (or pass it by value) if you want to modify it. In the recursive call, you could also pass a temporary vector created using vector's range constructor (as an alternative to erasing the front element). Yet another possibility would be to pass a 'depth' index together with the vector, such that you only adjust the index and not the vector in the recursive calls.
What's not clear from your description is how you actually iterate. All your for loops are basically empty. How do you intend to store the 'indices' for each variable in the current iteration? Globally?
-
Re: Iteration and recursion
If you need an unknown number of nested loops at runtime then this is worth a look.
http://drdobbs.com/cpp/184403251
-
Re: Iteration and recursion
Quote:
Originally Posted by
JohnW@Wessex
Thank you for your answer. It's an other way to implement what I want.
-
Re: Iteration and recursion
Quote:
Originally Posted by
D_Drmmr
See nuzzles remark about compile vs run time. The only way you can use templates would be to generate code for a set of possible recursion depths (e.g. from 1 to 50), which is likely to cause huge amounts of code bloat. I doubt this is worth the performance gain (if it would achieve any gain at all).
The code no, because it won't compile. But the structure/algorithm looks ok to me. Note that you need to copy the function argument (or pass it by value) if you want to modify it. In the recursive call, you could also pass a temporary vector created using vector's range constructor (as an alternative to erasing the front element). Yet another possibility would be to pass a 'depth' index together with the vector, such that you only adjust the index and not the vector in the recursive calls.
What's not clear from your description is how you actually iterate. All your for loops are basically empty. How do you intend to store the 'indices' for each variable in the current iteration? Globally?
In the last two weeks I have thought a lot about the my problem. This is my code with some adjustments
Code:
void Recurse(const vector<string>& variablesVector, Data* data)
{
// terminate recursion
if (variablesVector.size() == 0)
{
// do some operations with the data
return;
}
// loop for the variable in the data
for (Data::const_iterator it = data->begin(); it != data->end(); ++it)
{
// recursive step - remove the front variable for the next iteration
Recurse(variablesVector.erase(variablesVector.begin(), variablesVector.begin()+1), &data);
}
}
My code does the following operations. Given the vector of the variables and the Data (domain of the variables), it takes the first variable, search inside the domain of values Data and executes the recursive step. Takes the second variable, search inside the domain of values Data and executes the recursive step and so on.
At last step when there are no any variable in the vector, the code executes some operations on the data (each data for each variable).
I think that it realizes the behaviour of nested loops.
Code:
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)
Now I know that the complexity can be intractable with only small number of variables and small number of different values for each variable.
You are right, I can't use the template version if I don't know at compile time the number of variables in the vector. My vector is read from a parser, and so I don't know it before run time. Do you have a suggestions about how can I do to reduce the complexity of huge number of recursive calls?
-
Re: Iteration and recursion
Quote:
Originally Posted by
erotavlas
I think that it realizes the behaviour of nested loops.
Code:
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.
Quote:
Originally Posted by
erotavlas
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.
-
Re: Iteration and recursion
Quote:
Originally Posted by
erotavlas
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.
-
Re: Iteration and recursion
Quote:
Originally Posted by
nuzzle
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.
-
Re: Iteration and recursion
Quote:
Originally Posted by
erotavlas
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?
-
Re: Iteration and recursion
Quote:
Originally Posted by
JohnW@Wessex
Are each of your loops separate or are they nested?
The loops are nested :(
-
Re: Iteration and recursion
Quote:
Originally Posted by
erotavlas
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.
Quote:
Originally Posted by
erotavlas
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.
Quote:
Originally Posted by
erotavlas
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
-
Re: Iteration and recursion
Quote:
Originally Posted by
erotavlas
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
-
Re: Iteration and recursion
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).
Code:
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?
Code:
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.
Code:
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&)
-
Re: Iteration and recursion
Quote:
Originally Posted by erotavlas
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.
-
Re: Iteration and recursion
Quote:
Originally Posted by
laserlight
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!
-
Re: Iteration and recursion
Quote:
Originally Posted by
erotavlas
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?
-
Re: Iteration and recursion
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.
Code:
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.
