Re: Translation from recursive to iterative

From: BQ (balulaz_at_libero_dot_it_at_libero.invalid)
Date: 03/22/05 

Date: Tue, 22 Mar 2005 19:12:47 +0100

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

Relevant Pages