Converting recursive algorithm to an iterative version

A

Ania

Hi,

Here is my problem:
I implemented recurive algorithm in c++ for a problem given below:

I have a list of items (only positive integers are allowed) and fixed
number of bins of identical capacity. I need to pack items (if
possible) so that elements in each bin sum up to given capacity.

I try to convert my recursive algorithm to an one. However, my
implementation with explicit stack doesn't work as I expected. I can't
pinpoint the place where I have made a mistake.

//items are sorted in decreasing order

Recursive:
bool backtrack(vector<int>& items, vector<Bin>& bins, unsigned
index,unsigned bin_capacity)
{
if (bin_capacity - items.front() < 0) return false;

if (index < items.size())
{
//try to put an item into all opened bins
for(unsigned i = 0; i < bins.size(); ++i)
{
if (bins.sum() + items[index] + items.back() <=
bin_capacity || bin_capacity - bins.sum() == items[index])
{
bins.add(items[index]);
return backtrack(items, bins, index + 1,
bin_capacity);

}
}
//put an item without exceeding maximum number of bins
if (bins.size() < BINS)
{
Bin new_bin = Bin();
bins.push_back(new_bin);
bins.back().add(items[index]);

return backtrack(items, bins, index + 1, bin_capacity);

}
}
else
{
//check if solution has been found
if (bins.size() == BINS )
{
for (unsigned i = 0; i <bins.size(); ++i)
{
packed_items.push_back(bins);
}

return true;
}
}
return false;

}

Iterative( not working properly)
bool backtrack(vector<int>& items, vector<Bin>& bins, unsigned index,
unsigned bin_capacity)
{
stack<Node> stack;
Node node, child_node;
Bin new_bin;
//init the stack
node.bins.add(new_bin);
node.bins.back().add(items[item_index]);
stack.push(node);
item_index++;

while(!stack.empty())
{
node = stack.top();
stack.pop();

if (item_index < items.size())
{
if (node.bins.size() < BINS)
{
child_node = node;
Bin empty;
child_node.bins.add(empty);
child_node.bins.back().add(items[item_index]);
stack.push(child_node);
}

int last_index = node.bins.size() - 1;
for (unsigned i = 0; i <= last_index; i++)
{
if (node.bins[last_index - i]->get_sum()
+items[item_index]+ items.back( <=bin_capacity || bin_capacity -
node.bins[last_index - i]->get_sum() ==items[item_index])
{
child_node = node;
child_node.bins[last_index - i]-
push_back(items[item_index]);
Click to expand...

stack.push(child_node);
}
}
item_index++;
}
else
{
if (node.bins() == BINS)
{
//copy solution
bins = node.bins;
return true;
}
}
}
return false;

}

Any help would be highly appreciated.
 
V

Victor Bazarov

Here is my problem:
I implemented recurive algorithm in c++ for a problem given below:

I have a list of items (only positive integers are allowed) and fixed
number of bins of identical capacity. I need to pack items (if
possible) so that elements in each bin sum up to given capacity.

I try to convert my recursive algorithm to an one. However, my
implementation with explicit stack doesn't work as I expected.
Click to expand...

What does that mean? What did you expect? What does it do? Do you
think we should be guessing or dusting off our crystal ball?
I can't
pinpoint the place where I have made a mistake.
Click to expand...

Have you tried using a "debugger" and step through your code? Do you
have a test case? Do you know what values of your objects need to be on
every step of your algorithm? If you do, just fire off that debugger
(whichever you got, all pretty much work when you know what you're
doing) and execute your test program step by step, and verify that the
values of the objects as they need to be. If they aren't make changes
to the code.

If you don't have a test case, get yourself one. If you don't know what
values of your objects should be at every point in your program... did
you actually write your program yourself? If you did, you should. Do
you know how to use a debugger? If you don't, it looks like it's time
to learn.

Bite the bullet and fix your own program. Otherwise, find a different
field to develop your skills.

V
 
N

Nick Keighley

Hi,

Here is my problem:
I implemented recurive algorithm in c++ for a problem given below:

I have a list of items (only positive integers are allowed) and fixed
number of bins of identical capacity. I need to pack items (if
possible) so that elements in each bin sum up to given capacity.

I try to convert my recursive algorithm to an one. However, my
implementation with explicit stack doesn't work as I expected. I can't
pinpoint the place where I have made a mistake.

//items are sorted in decreasing order

Recursive:
bool backtrack(vector<int>& items, vector<Bin>& bins, unsigned
index,unsigned bin_capacity)
{
    if (bin_capacity - items.front() < 0) return false;

    if (index < items.size())
    {
        //try to put an item into all opened bins
        for(unsigned i = 0; i < bins.size(); ++i)
        {
            if (bins.sum() + items[index] + items.back() <=
bin_capacity || bin_capacity - bins.sum() == items[index])
            {
                bins.add(items[index]);
                return backtrack(items, bins, index + 1,
bin_capacity);

            }
        }
        //put an item without exceeding maximum number of bins
        if (bins.size() < BINS)
        {
            Bin new_bin = Bin();
            bins.push_back(new_bin);
            bins.back().add(items[index]);

            return backtrack(items, bins, index + 1, bin_capacity);

        }
    }
    else
    {
        //check if solution has been found
        if  (bins.size() == BINS )
        {
            for (unsigned i = 0; i <bins.size(); ++i)
            {
                packed_items.push_back(bins);
            }

            return true;
        }
    }
    return false;

}

Iterative( not working properly)
bool backtrack(vector<int>& items, vector<Bin>& bins, unsigned index,
unsigned bin_capacity)
{
      stack<Node> stack;
      Node node, child_node;
      Bin new_bin;
      //init the stack
      node.bins.add(new_bin);
      node.bins.back().add(items[item_index]);
      stack.push(node);
      item_index++;

      while(!stack.empty())
      {
        node = stack.top();
        stack.pop();

        if (item_index < items.size())
        {
            if (node.bins.size() < BINS)
            {
               child_node = node;
               Bin empty;
               child_node.bins.add(empty);
               child_node.bins.back().add(items[item_index]);
               stack.push(child_node);
            }

            int last_index = node.bins.size() - 1;
            for (unsigned i = 0; i <= last_index; i++)
            {
                if (node.bins[last_index - i]->get_sum()
+items[item_index]+ items.back( <=bin_capacity || bin_capacity -
node.bins[last_index - i]->get_sum() ==items[item_index])
               {
                   child_node = node;
                   child_node.bins[last_index - i]-
push_back(items[item_index]);
Click to expand...

                   stack.push(child_node);
                }
            }
            item_index++;
            }
        else
        {
           if (node.bins() == BINS)
           {
               //copy solution
               bins = node.bins;
               return true;
           }
       }
   }
    return false;

}

Any help would be highly appreciated.
Click to expand...


build in some sort of trace facility. By seeing what gets called with
what parameters should enable you to compare the recursive with the
iterative and fix one or the other.

Why are you doing this?
 
A

Ania

@Nick Keighley I'm trying to implement an iterative version just
because of stack overflows for large datasets in recursive approach,

Thanks for your suggestions, I'll try to use debugger.
 
L

Larry Evans

On 12/07/11 17:48, Ania wrote:
[snip]
I try to convert my recursive algorithm to an one. However, my
implementation with explicit stack doesn't work as I expected. I can't
pinpoint the place where I have made a mistake.
Click to expand...
[snip]

In the iterative code, there's:
int last_index = node.bins.size() - 1;
for (unsigned i = 0; i <= last_index; i++)
{
if (node.bins[last_index - i]->get_sum()
+items[item_index]+ items.back( <=bin_capacity || bin_capacity -
node.bins[last_index - i]->get_sum() ==items[item_index])
Click to expand...
This looks suspicious to me:

( <=bin_capacity

Are you sure you've posted code that compiles?

-regards,
Larry
 
A

Ania

On 12/07/11 17:48, Ania wrote:
[snip]> I try to convert my recursive algorithm to an one. However, my
implementation with explicit stack doesn't work as I expected. I can't
pinpoint the place where I have made a mistake.
Click to expand...

[snip]

In the iterative code, there's:
            int last_index = node.bins.size() - 1;
            for (unsigned i = 0; i <= last_index; i++)
            {
                if (node.bins[last_index - i]->get_sum()
+items[item_index]+ items.back( <=bin_capacity || bin_capacity -
node.bins[last_index - i]->get_sum() ==items[item_index])
Click to expand...

This looks suspicious to me:

  ( <=bin_capacity

Are you sure you've posted code that compiles?

-regards,
Larry
Click to expand...

Finally, I found a place where I made a mistake. I messed with
pointers(shallow copies) and that was the main problem. Now it works
great.

Thanks for inspiring me.

I'm sorry but the code posted was not ready to compile, it was high
level pseudocode.
Here is code ready to compile (I don't use pointers here, just to make
it simpler).

class Bin
{
public:
Bin() { _sum = 0;}
int get_sum(){ return _sum; }
int size() {return bin.size(); }
bool isFull() { return _sum == bin.size(); }
void add(int item)
{
bin.push_back(item);
_sum += item;
}
//for testing output
void print(){
for(unsigned i = 0; i < bin.size(); ++i)
{
cout<< bin<<endl;
}
}
private:
vector<unsigned> bin;
unsigned _sum;
};

struct Node
{
vector<Bin> bins;
};

BINS = 3; //just example value

bool backtrack(vector<unsigned>& items, vector<Bin>& bins, unsigned
index,unsigned bin_capacity)
{
if (bin_capacity - items.front() < 0) return false;

if (index < items.size())
{
//try to put an item into all opened bins
for(unsigned i = 0; i < bins.size(); ++i)
{
if (bins.get_sum() + items[index] + items.back() <=
bin_capacity || bin_capacity - bins.get_sum() == items[index])
{
bins.add(items[index]);
return backtrack(items, bins, index + 1,
bin_capacity);

}
}
//put an item without exceeding maximum number of bins
if (bins.size() < BINS)
{
Bin new_bin = Bin();
bins.push_back(new_bin);
bins.back().add(items[index]);

return backtrack(items, bins, index + 1, bin_capacity);

}
}
else
{
if (bins.size() == BINS )
{
return true;
}
}
return false;

}


bool backtrack2(vector<unsigned>& items, vector<Bin>& bins, unsigned
item_index, unsigned bin_capacity)
{
stack<Node> stack;
Node node, child_node;
Bin new_bin;
//init the stack
node.bins.push_back(new_bin);
node.bins.back().add(items[item_index]);
stack.push(node);
item_index++;

while(!stack.empty())
{
node = stack.top();
stack.pop();

if (item_index < items.size())
{
if (node.bins.size() < BINS)
{
child_node = node;
Bin empty;
child_node.bins.push_back(empty);
child_node.bins.back().add(items[item_index]);
stack.push(child_node);
}

int last_index = node.bins.size() - 1;
for (unsigned i = 0; i <= last_index; i++)
{
if (node.bins[last_index - i].get_sum()
+items[item_index]+ items.back() <=bin_capacity || bin_capacity -
node.bins[last_index - i].get_sum() ==items[item_index])
{
child_node = node;
child_node.bins[last_index -
i].add(items[item_index]);

stack.push(child_node);
}
}
item_index++;
}
else
{
if (node.bins.size() == BINS)
{
//copy solution
bins = node.bins;
return true;
}
}
}
return false;

}
 
J

Juha Nieminen

Ania said:
I try to convert my recursive algorithm to an [iterative] one.
Click to expand...

May I ask why?

I think that unless there's a good reason for that, this is a true case
of premature optimization (in the most negative sense). It is often the
case that if an algorithm is recursive in nature, trying to implement it
iteratively (especially if you need an explicit stack) only produces
significantly longer and more complicated code. If the amount of recursion
in the original algorithm is less-than-linear (eg. O(log n) recursions),
then any possible overhead caused by the recursive calls is insignificant.

Thus, in such a case, the iterative version will be longer, more
complicated and with little to no speed benefit. (Hence why it's true
premature optimization.)
 
8

88888 Dihedral

Ania said:
I try to convert my recursive algorithm to an [iterative] one.
Click to expand...

May I ask why?

I think that unless there's a good reason for that, this is a true case
of premature optimization (in the most negative sense). It is often the
case that if an algorithm is recursive in nature, trying to implement it
iteratively (especially if you need an explicit stack) only produces
significantly longer and more complicated code. If the amount of recursion
in the original algorithm is less-than-linear (eg. O(log n) recursions),
then any possible overhead caused by the recursive calls is insignificant.

Thus, in such a case, the iterative version will be longer, more
complicated and with little to no speed benefit. (Hence why it's true
premature optimization.)
Click to expand...

If you are writing programs to be run infrequently for trivial jobs,
I have to say that in this kind of trivial cases there is no need for any optimization or improvement for this kind of programming.

But in my experience, codes fine-tued for speed requirements are not low paid
programmers' jobs in the industry.
 
J

Juha Nieminen

88888 Dihedral said:
If you are writing programs to be run infrequently for trivial jobs,
I have to say that in this kind of trivial cases there is no need for any optimization or improvement for this kind of programming.
Click to expand...

And my point is that *regardless* of where the code might be used,
converting a naturally recursive algorithm into an iterative form that
avoids the recursive function call is usually premature optimization of
the bad kind (makes the code significantly more complicated for little
to no benefit).
 
8

88888 Dihedral

And my point is that *regardless* of where the code might be used,
converting a naturally recursive algorithm into an iterative form that
avoids the recursive function call is usually premature optimization of
the bad kind (makes the code significantly more complicated for little
to no benefit).
Click to expand...

There are very limited cases for recursive functions to be used in C.
The quick sort in the c lib is notorious to be choked quite often.
Tree visiting of 30K nodes or less in C is too simple to be modified for speeds.
 
J

Juha Nieminen

88888 Dihedral said:
There are very limited cases for recursive functions to be used in C.
Click to expand...

You don't understand my point.
The quick sort in the c lib is notorious to be choked quite often.
Click to expand...

qsort() is not slow because of the recursion. std::sort() uses recursion
as well. So what?
 
8

88888 Dihedral

You don't understand my point.


qsort() is not slow because of the recursion. std::sort() uses recursion
as well. So what?
Click to expand...

There was not my problem. That was problems for non-professionals.
 
T

Tobias Müller

Juha Nieminen said:
And my point is that *regardless* of where the code might be used,
converting a naturally recursive algorithm into an iterative form that
avoids the recursive function call is usually premature optimization of
the bad kind (makes the code significantly more complicated for little
to no benefit).
Click to expand...

One can argue if it is an optimization at all, but why do you always call
it premature? In my understanding, premature optimization is optimization
that is done before knowing if it is really worth it. Bad quality alone
doesn't qualify an optimization as premature.

The OP has already said that he has encountered stack overflows, so I
really would not call that premature if he wants to do fix that.
You cannot always control the stack size awailable to a function especially
if you are writing a library and not an executable.

Tobi
 
J

Joe keane

Increasing the stack size should be relatively harmless unless the app has
many threads.
Click to expand...

That's what gets you...

Stack on multi-thread apps is demanding.

Even if some memory is needed for a short time, (heap is what the
threads need at the same time, stack is what all the threads need some
of the time) the heap allocation may be -faster- (because it uses memory
efficiently).

Also running out of stack is ungraceful... If you call malloc and it
returns NULL (oh wait this C++ you know what mean) you can try to
restore some semblance of order. Out of stack, blam! Your files,
shared memory??

I echo some other posters that we don't know the context of program.
Some app you only run yourself? Quasi-real-time where some people die
if it fails?
 
A

Ania

This app is just for my personal use and it works quite fast for data
sets < 50 000 items. However, for larger data sets I encountered stack
overflows and I was wondering if changing it to an iterative version
would solve the problem.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Implementing Many Stacks in the Same Program 1
[newbie] Recursive algorithm - review 5
converting recursive function to iterative 4
Chatbot 0
[newbie] Recursive algorithm - review 5
Optimize a discovery algorithm 15
Dijkstra Algorithm Help 4
Translation from recursive to iterative 14

Members online

Total: 56 (members: 3, guests: 53)
Robots: 339

Forum statistics

Threads
473,982
Messages
2,570,185
Members
46,738
Latest member
JinaMacvit

Latest Threads

Top