Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Translation from recursive to iterative

Reply
Thread Tools

Translation from recursive to iterative

 
 
BQ
Guest
Posts: n/a
 
      03-22-2005
Due to a lack of resources, I have to translate the following recursive
function in its iterative form.
It's a kind of dichotomic search.

void SearchSlaves(unsigned long start_uid, unsigned long end_uid)
{
char ret;
//ping over a range of addresses (all slaves with uid in the range from
start_uid to end_uid will reply)
ret = PingSlave(start_uid,end_uid);

if (start_uid == end_uid) //single item
{
if (ret == VALID_PING_REPLY)
AddUidToSlaveList(start_uid);
return;
}
if (ret == VALID_PING_REPLY)
{
SearchSlaves( start_uid , ( (start_uid + end_uid + 1) >> 1) - 1 );
//left subtree
SearchSlaves( ( (start_uid + end_uid + 1) >> 1) , end_uid); //right
subtree
}
}

Any help will be greatly appreciated!
Regards,
Marco
 
Reply With Quote
 
 
 
 
Richard Bos
Guest
Posts: n/a
 
      03-22-2005
BQ <(E-Mail Removed)> wrote:

> Due to a lack of resources, I have to translate the following recursive
> function in its iterative form.
> It's a kind of dichotomic search.
>
> void SearchSlaves(unsigned long start_uid, unsigned long end_uid)
> {
> char ret;
> //ping over a range of addresses (all slaves with uid in the range from
> start_uid to end_uid will reply)
> ret = PingSlave(start_uid,end_uid);
>
> if (start_uid == end_uid) //single item
> {
> if (ret == VALID_PING_REPLY)
> AddUidToSlaveList(start_uid);
> return;
> }
> if (ret == VALID_PING_REPLY)
> {
> SearchSlaves( start_uid , ( (start_uid + end_uid + 1) >> 1) - 1 );
> //left subtree
> SearchSlaves( ( (start_uid + end_uid + 1) >> 1) , end_uid); //right
> subtree


[ BTW, using C++-style comments _and_ tabs in a newsgroup is not a good
idea. ]

> }
> }


First thought: get rid of the premature optimisation, get rid of the
unnecessary object (yes, I do see the irony):

void SearchSlaves(unsigned long start_uid, unsigned long end_uid)
{
if (PingSlave(start_uid,end_uid)==VALID_PING_REPLY) {
if (start_uid == end_uid) {
AddUidToSlaveList(start_uid);
return;
}
SearchSlaves(start_uid, (start_uid+end_uid+1)/2) - 1);
SearchSlaves((start_uid+end_uid+1)/2, end_uid);
}
}

Second thought: while this algorithm is efficient if slaves are very
sparse, or relatively sparse and clustered within the range, this is
probably an efficient algorithm. Every slave is pinged several times,
though (log2(end_uid-start_uid) times, circa), so if there are many
slaves, this is not efficient. Nor is it optimal if there are a
reasonable number of slaves peppered through the range. If you suspect
one of those may be the case, a straightforward linear search may beat
this algorithm.
In fact, if PingSlave uses the obvious, naive algorithm for searching
its range, this already _is_ a linear search - several times over. One
other possibility would be to improve PingSlave's efficiency, perhaps by
giving it a (resettable) memory.

Richard
 
Reply With Quote
 
 
 
 
BQ
Guest
Posts: n/a
 
      03-22-2005
Richard Bos wrote:

> [ BTW, using C++-style comments _and_ tabs in a newsgroup is not a good
> idea. ]


ehr, sorry....

>
> First thought: get rid of the premature optimisation, get rid of the
> unnecessary object (yes, I do see the irony):
>
> void SearchSlaves(unsigned long start_uid, unsigned long end_uid)
> {
> if (PingSlave(start_uid,end_uid)==VALID_PING_REPLY) {
> if (start_uid == end_uid) {
> AddUidToSlaveList(start_uid);
> return;
> }
> SearchSlaves(start_uid, (start_uid+end_uid+1)/2) - 1);
> SearchSlaves((start_uid+end_uid+1)/2, end_uid);
> }
> }
>
> Second thought: while this algorithm is efficient if slaves are very
> sparse,


-- and this is the case: max.20/30 'slaves', sparse over a range 2^16 wide

> or relatively sparse and clustered within the range, this is
> probably an efficient algorithm. Every slave is pinged several times,
> though (log2(end_uid-start_uid) times, circa), so if there are many
> slaves, this is not efficient. Nor is it optimal if there are a
> reasonable number of slaves peppered through the range. If you suspect
> one of those may be the case, a straightforward linear search may beat
> this algorithm.


in my situation, a straightforward linear search can't be made.
Every ping has a 150ms timeout that can't be reduced, and the
searchspace is very large.

> In fact, if PingSlave uses the obvious, naive algorithm for searching
> its range, this already _is_ a linear search - several times over.


Slaves answer to the ping if their uid is start_uid<= uid <= end_uid.
So searching 10/20 slaves requires about 2-3 seconds at most

Anyway, this code is compiled against a microprocessor with very limited
resources and I have a problem with stack that pushes me toward
searching an iterative version of this algorithm: I can make at most 32
subroutine calls, and SearchSlave calls itself at least 16 times in a
2^16 space. Since SearchSlave is not at level 0, I sometime obtain a
stack overflow.

By the way, theory assures that a recursive algorithm can always be
rewritten in an iterative way. If anyone has an idea...

Regards,
Marco
 
Reply With Quote
 
CBFalconer
Guest
Posts: n/a
 
      03-22-2005
BQ wrote:
>
> Due to a lack of resources, I have to translate the following recursive
> function in its iterative form.
> It's a kind of dichotomic search.
>
> void SearchSlaves(unsigned long start_uid, unsigned long end_uid)
> {
> char ret;
> //ping over a range of addresses (all slaves with uid in the range from
> start_uid to end_uid will reply)
> ret = PingSlave(start_uid,end_uid);
>
> if (start_uid == end_uid) //single item
> {
> if (ret == VALID_PING_REPLY)
> AddUidToSlaveList(start_uid);
> return;
> }
> if (ret == VALID_PING_REPLY)
> {
> SearchSlaves( start_uid , ( (start_uid + end_uid + 1) >> 1) - 1 );
> //left subtree
> SearchSlaves( ( (start_uid + end_uid + 1) >> 1) , end_uid); //right
> subtree
> }
> }
>
> Any help will be greatly appreciated!
> Regards,
> Marco


You might start by making it easy for people to help you. 8 char
indents are excessive, // comments don't survive line wrapping
well, and any linelength over about 72 is likely to cause a problem
on newsgroups. Do not use tabs, use spaces. Include dummy
functions for the undefined things, so that people can compile it
immediately. As it is the SearchSlaves operation seems singularly
useless, since it returns nothing.

--
"I conclude that there are two ways of constructing a software
design: One way is to make it so simple that there are obviously
no deficiencies and the other way is to make it so complicated
that there are no obvious deficiencies." -- C. A. R. Hoare


 
Reply With Quote
 
Eric Sosman
Guest
Posts: n/a
 
      03-22-2005


BQ wrote:
> Richard Bos wrote:
>
>
>>[ BTW, using C++-style comments _and_ tabs in a newsgroup is not a good
>>idea. ]

>
>
> ehr, sorry....
>
>
>>First thought: get rid of the premature optimisation, get rid of the
>>unnecessary object (yes, I do see the irony):
>>
>> void SearchSlaves(unsigned long start_uid, unsigned long end_uid)
>> {
>> if (PingSlave(start_uid,end_uid)==VALID_PING_REPLY) {
>> if (start_uid == end_uid) {
>> AddUidToSlaveList(start_uid);
>> return;
>> }
>> SearchSlaves(start_uid, (start_uid+end_uid+1)/2) - 1);
>> SearchSlaves((start_uid+end_uid+1)/2, end_uid);
>> }
>> }
>>
>>Second thought: while this algorithm is efficient if slaves are very
>>sparse,

>
>
> -- and this is the case: max.20/30 'slaves', sparse over a range 2^16 wide
>
>
>>or relatively sparse and clustered within the range, this is
>>probably an efficient algorithm. Every slave is pinged several times,
>>though (log2(end_uid-start_uid) times, circa), so if there are many
>>slaves, this is not efficient. Nor is it optimal if there are a
>>reasonable number of slaves peppered through the range. If you suspect
>>one of those may be the case, a straightforward linear search may beat
>>this algorithm.

>
>
> in my situation, a straightforward linear search can't be made.
> Every ping has a 150ms timeout that can't be reduced, and the
> searchspace is very large.
>
>
>>In fact, if PingSlave uses the obvious, naive algorithm for searching
>>its range, this already _is_ a linear search - several times over.

>
>
> Slaves answer to the ping if their uid is start_uid<= uid <= end_uid.
> So searching 10/20 slaves requires about 2-3 seconds at most
>
> Anyway, this code is compiled against a microprocessor with very limited
> resources and I have a problem with stack that pushes me toward
> searching an iterative version of this algorithm: I can make at most 32
> subroutine calls, and SearchSlave calls itself at least 16 times in a
> 2^16 space. Since SearchSlave is not at level 0, I sometime obtain a
> stack overflow.
>
> By the way, theory assures that a recursive algorithm can always be
> rewritten in an iterative way. If anyone has an idea...


If you're sure this is the algorithm you want to use,
go ahead and implement it with an explicit stack of your own:
a local array of start/end pairs plus an index indicating
where the stack top is.

#include <limits.h>
#define STACK_MAX (sizeof(unsigned long) * CHAR_BIT)
/* ... or perhaps less if you know something about
* the possible range of inputs.
*/

void SearchSlaves(unsigned long start, unsigned long end) {
struct { unsigned long start, end; } stack[STACK_MAX];
int depth;

/* Begin by pushing the whole range as one pair */
stack[0].start = start;
stack[0].end = end;
depth = 1;

/* Keep looping as long as the stack still contains
* unexplored ranges
*/
while (--depth >= 0) {

/* Pop a range from the stack */
start = stack[depth].start;
end = stack[depth].end;

/* Do the test */
if (PingSlave(start, end) == VALID_PING_REPLY) {
if (start == end) {
/* Base case: a trivial range */
AddUidToSlaveList(start);
}
else {
/* "Recursive" case: split the range and
* push the two halves
*/
unsigned long mid = (start + end + 1) / 2;
stack[depth].start = start;
stack[depth++].end = mid - 1;
stack[depth].start = mid;
stack[depth++].end = end;
}
}
}
}

This could be cleaned up a bit to eliminate about half of the
stack pushes and pops; I've written it this way to show the
essentials of the transformation. Also, with some cleverness
you might be able to stack just one endpoint of each range.

--
http://www.velocityreviews.com/forums/(E-Mail Removed)

 
Reply With Quote
 
BQ
Guest
Posts: n/a
 
      03-22-2005
CBFalconer wrote:

> You might start by making it easy for people to help you. 8 char
> indents are excessive, // comments don't survive line wrapping
> well, and any linelength over about 72 is likely to cause a problem
> on newsgroups. Do not use tabs, use spaces. Include dummy
> functions for the undefined things, so that people can compile it
> immediately. As it is the SearchSlaves operation seems singularly
> useless, since it returns nothing.
>


Thanks CBFalconer, I'll keep it in mind when I'll write a post next time.
Regards,
Marco
 
Reply With Quote
 
BQ
Guest
Posts: n/a
 
      03-22-2005
Eric Sosman wrote:

>
> If you're sure this is the algorithm you want to use,
> go ahead and implement it with an explicit stack of your own:
> a local array of start/end pairs plus an index indicating
> where the stack top is.


[CUT]

Eric, your post was very useful and teached my this new (new for me) use
of a stack. Thank you very much!!
Regards,
Marco
 
Reply With Quote
 
CBFalconer
Guest
Posts: n/a
 
      03-23-2005
BQ wrote:
> CBFalconer wrote:
>
>> You might start by making it easy for people to help you. 8 char
>> indents are excessive, // comments don't survive line wrapping
>> well, and any linelength over about 72 is likely to cause a problem
>> on newsgroups. Do not use tabs, use spaces. Include dummy
>> functions for the undefined things, so that people can compile it
>> immediately. As it is the SearchSlaves operation seems singularly
>> useless, since it returns nothing.

>
> Thanks CBFalconer, I'll keep it in mind when I'll write a post next
> time.


Well, I thought you would post back with a cleaned up version. The
first and obvious thing is to remove the tail recursion. That can
automatically (with a choice of which half to recurse to) cut the
maximum recursion depth to log2(n) with practically zero effort.
After that there are straight forward mechanical methods for
replacing recursion with a local stack.

--
"I conclude that there are two ways of constructing a software
design: One way is to make it so simple that there are obviously
no deficiencies and the other way is to make it so complicated
that there are no obvious deficiencies." -- C. A. R. Hoare


 
Reply With Quote
 
E. Robert Tisdale
Guest
Posts: n/a
 
      03-23-2005
BQ wrote:

> Due to a lack of resources,
> I have to translate the following recursive function in its iterative form.
> It's a kind of dichotomic search.
>
> void SearchSlaves(unsigned long start_uid, unsigned long end_uid) {
> char ret;
> //ping over a range of addresses
> //(all slaves with uid in the range
> // from start_uid to end_uid will reply)
> ret = PingSlave(start_uid,end_uid);
>
> if (start_uid == end_uid) //single item {
> if (ret == VALID_PING_REPLY)
> AddUidToSlaveList(start_uid);
> return;
> }
> if (ret == VALID_PING_REPLY) {
> // left subtree
> SearchSlaves(start_uid, ((start_uid + end_uid + 1) >> 1) - 1);
> // right subtree
> SearchSlaves(((start_uid + end_uid + 1) >> 1), end_uid);
> }
> }
>
> Any help will be greatly appreciated!


I don't think that I can help you with your immediate problem
but you should keep in mind that
many C compilers will optimize [tail-]recursion for you.
For example:

> cat factorial.c

unsigned int
factorial1(unsigned int n, unsigned int accumulator) {
if (n == 0)
return accumulator;
else
return factorial1(n - 1, n*accumulator);
}

unsigned int
factorial(unsigned int n) {
return factorial1(n, 1);
}

> gcc -Wall -std=c99 -pedantic -O2 -S factorial.c
> cat factorial.s

.file "factorial.c"
.text
.p2align 4,,15
.globl factorial1
.type factorial1, @function
factorial1:
pushl %ebp
movl %esp, %ebp
movl 8(%ebp), %edx
movl 12(%ebp), %eax
jmp .L4
.p2align 4,,7
.L7:
imull %edx, %eax
decl %edx
.L4:
testl %edx, %edx
jne .L7
popl %ebp
ret
.size factorial1, .-factorial1
.p2align 4,,15
.globl factorial
.type factorial, @function
factorial:
pushl %ebp
movl $1, %eax
movl %esp, %ebp
subl $8, %esp
movl %eax, 4(%esp)
movl 8(%ebp), %eax
movl %eax, (%esp)
call factorial1
leave
ret
.size factorial, .-factorial
.section .note.GNU-stack,"",@progbits
.ident "GCC: (GNU) 3.4.1"
 
Reply With Quote
 
BQ
Guest
Posts: n/a
 
      03-23-2005
CBFalconer wrote:

> Well, I thought you would post back with a cleaned up version.


Sorry, I didn't do that because Eric had already answered my question.
Anyway, here is the cleaned up version:

void SearchSlaves(unsigned long start_uid, unsigned long end_uid)
{
if (PingSlave(start_uid,end_uid)==VALID_PING_REPLY) {
if (start_uid == end_uid) {
AddUidToSlaveList(start_uid);
return;
}
SearchSlaves(start_uid, (start_uid+end_uid+1)/2) - 1);
SearchSlaves((start_uid+end_uid+1)/2, end_uid);
}
}

> The
> first and obvious thing is to remove the tail recursion.


[CUT]

> After that there are straight forward mechanical methods for
> replacing recursion with a local stack.
>


I agree with you and I think this will be the solution I'll chose, and
I'll use Eric's function.
Thank you all very much.
Regards,
Marco
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Converting recursive algorithm to an iterative version Ania C++ 15 12-11-2011 10:26 PM
DNS Question: Recursive vs. Iterative SWE MCSE 20 04-08-2011 06:29 PM
Iterative vs. Recursive coding Baba Python 42 09-06-2010 04:17 PM
My understanding of iterative vs. recursive DNS Spin Computer Support 2 06-26-2009 10:55 AM
converting recursive function to iterative V C Programming 4 05-13-2008 02:08 PM



Advertisments