Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #158285

Re: Recursion v Memoization

Show all headers | View raw

beej@beej.us (Beej) writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> For floodfill usually it's better to use a breadth-first traversal.
>
> Interesting.  Elaborate?

Here are two versions of a flood fill algorithm.  They are the
same except one treats the array s as a stack, the other as a
queue.  Don't worry about the "infinite" array, that will be
addressed following.  Please excuse the mixture of C and
pseudo-code.

    fill( fill-point, other stuff ){
        let s be a local array, "infinitely" large
        Index a = 0, b = 0;
        color fill-point the new color
        s[ b++ ] = fill-point
        while a < b {
            Point p = s[ --b ];
            for each neighbor, n, of p that has the old color {
                color n the new color
                s[ b++ ] = n
            }
        }
    }

    fill( fill-point, other stuff ){
        let s be a local array, "infinitely" large
        Index a = 0, b = 0;
        color fill-point the new color
        s[ b++ ] = fill-point
        while a < b {
            Point p = s[ a++ ];
            for each neighbor, n, of p that has the old color {
                color n the new color
                s[ b++ ] = n
            }
        }
    }

The queue version expands breadth first.  The stack version
expands depth first, and hence corresponds to recursion.

Of course we cannot have an "infinite" array.  In most cases a
fairly small array will suffice (a somewhat more sophisticated
algorithm helps reduce the size, but it's not important to
understand the details of that).  If the array is finite rather
than "infinite" then naturally the queue version needs to use
modulo arithmetic to keep a and b in range, but I'm sure you
can work that out so I won't go into any more detail on that.

However, with the array being finite, we need to be prepared for
the possibility that the array will fill up.  One way to do that
is have the array be allocated dynamically, using malloc/realloc
to grow the array as needed.  Another way is for fill() to call
itself recursively when s is full, with a small fixed-size array
at each level of recursion.

Which ever of the two approaches is taken, we can ask which version
(stack or queue) needs less memory resource.  It turns out that in
some pathological cases the queue version does a better job, and
AFAIK never does appreciably worse.  Also I believe (based on a
less than fully reliable memory) that the queue version does a bit
better in "typical" cases.  I don't have a reason to offer as to
why these results should be so, only that empirically that's what
I've seen.

Hopefully that is enough elaboration. :)

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Recursion v Memoization Real Troll <real.Troll@trolls.com> - 2020-12-29 16:30 -0500
  Re: Recursion v Memoization Bart <bc@freeuk.com> - 2020-12-29 22:17 +0000
    Re: Recursion v Memoization Ike Naar <ike@sdf.org> - 2020-12-30 05:47 +0000
      Re: Recursion v Memoization Bart <bc@freeuk.com> - 2020-12-30 11:55 +0000
  Re: Recursion v Memoization "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-12-29 21:51 -0800
  Re: Recursion v Memoization Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-12-31 00:46 -0800
    Re: Recursion v Memoization David Brown <david.brown@hesbynett.no> - 2020-12-31 16:12 +0100
      [OT] was: Recursion v Memoization Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-01-01 15:59 +0000
        Re: [OT] was: Recursion v Memoization David Brown <david.brown@hesbynett.no> - 2021-01-01 17:35 +0100
        Re: [OT] was: Recursion v Memoization Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-01-01 08:40 -0800
        Re: [OT] was: Recursion v Memoization Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-01-02 10:36 -0800
          Re: [OT] was: Recursion v Memoization "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-01-02 16:59 -0800
          Re: [OT] was: Recursion v Memoization "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-01-02 17:00 -0800
    Re: Recursion v Memoization Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2021-01-02 18:56 -0700
      Re: Recursion v Memoization Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-01-04 19:56 -0800
        Re: Recursion v Memoization beej@beej.us (Beej) - 2021-01-05 04:27 +0000
          Re: Recursion v Memoization Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-01-07 04:54 -0800
            Re: Recursion v Memoization beej@beej.us (Beej) - 2021-01-11 05:43 +0000
              Re: Recursion v Memoization Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-01-11 06:34 -0800
        Re: Recursion v Memoization Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2021-01-05 14:35 -0700
          Re: Recursion v Memoization Real Troll <real.troll@trolls.com> - 2021-01-05 16:45 -0500
            Re: Recursion v Memoization Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2021-01-05 15:33 -0700
          Re: Recursion v Memoization Jorgen Grahn <grahn+nntp@snipabacken.se> - 2021-01-06 09:40 +0000
            Re: Recursion v Memoization Jorgen Grahn <grahn+nntp@snipabacken.se> - 2021-01-06 17:09 +0000
          Re: Recursion v Memoization Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-01-07 06:37 -0800
  Re: Recursion v Memoization Andrey Tarasevich <andreytarasevich@hotmail.com> - 2020-12-31 02:33 -0800

csiph-web