Converting recursive algorithm to an iterative version

[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]);

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.

 

[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.

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.

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

 

[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]);

                   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.

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?

 

[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.

 

[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.

[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])

This looks suspicious to me:

( <=bin_capacity

Are you sure you've posted code that compiles?

-regards,
Larry

 

[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.

[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])

This looks suspicious to me:

  ( <=bin_capacity

Are you sure you've posted code that compiles?

-regards,
Larry

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;

}

 

[Juha Nieminen]

I try to convert my recursive algorithm to an [iterative] one.

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.)

 

[88888 Dihedral]

I try to convert my recursive algorithm to an [iterative] one.

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.)

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.

 

[Juha Nieminen]

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.

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).

 

[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).

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.

 

[Juha Nieminen]

There are very limited cases for recursive functions to be used in C.

You don't understand my point.

The quick sort in the c lib is notorious to be choked quite often.

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

 

[88888 Dihedral]

You don't understand my point.


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

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

 

[88888 Dihedral]

There was not my problem. That was a problem for non-professionals.

 

[Tobias Müller]

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).

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

 

[Joe keane]

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

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?

 

[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.