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

Groups > comp.lang.c++ > #10613

Re: Iterate over the adjacent elements in a matix container

Show all headers | View raw

On Fri, 30 Sep 2011 06:24:12 +0000, Juha Nieminen wrote:

>> One problem with a depth-first search done this way is you will need a 
>> recursion depth equal to the maximum number of nodes that may need to be 
>> marked. A breadth first search, using a stack like structure to store 
>> the list of nodes to visit, may require less levels stored, and if using 
>> tail recursion optimization, doesn't actually need to use recursion.
> 
>   Btw, I didn't notice this at first, but now I see that you seem to be
> suggesting that it's much preferable to avoid recursion, even if it means
> using a more complicated (to implement) solution. Why?

One advantage of an explicit stack is that you're more likely to be able
to allocate a large heap block than a large stack. On Unix, any memory
allocated for the stack (RLIMIT_STACK) cannot be used for anything else,
which tends to result in it being somewhat smaller than the largest
possible heap block.

Also, you can detect malloc() failure (NULL return) more easily than a
stack overflow (SIGSEGV, which can only be caught if you have allocated an
alternate signal stack).

Finally, the amount of memory for each recursion level is likely to be
less when using a manual stack. Each frame on the program stack will
typically contain saved program counter, stack pointer and frame pointer
registers, as well as space for any temporary storage. This is all in
addition to space which is inherently required by the algorithm.

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

Thread

Iterate over the adjacent elements in a matix container Alexander <alvatov@gmail.com> - 2011-09-26 12:44 -0700
  Re: Iterate over the adjacent elements in a matix container Victor Bazarov <v.bazarov@comcast.invalid> - 2011-09-26 15:49 -0400
  Re: Iterate over the adjacent elements in a matix container puppi <fabricio.puppi@gmail.com> - 2011-09-26 15:30 -0700
  Re: Iterate over the adjacent elements in a matix container "Paul" <pchristor@yahoo.co.uk> - 2011-09-27 06:43 +0100
    Re: Iterate over the adjacent elements in a matix container Juha Nieminen <nospam@thanks.invalid> - 2011-09-27 07:12 +0000
      Re: Iterate over the adjacent elements in a matix container Richard Damon <news.x.richarddamon@xoxy.net> - 2011-09-27 11:10 -0400
        Re: Iterate over the adjacent elements in a matix container Juha Nieminen <nospam@thanks.invalid> - 2011-09-27 20:32 +0000
        Re: Iterate over the adjacent elements in a matix container Juha Nieminen <nospam@thanks.invalid> - 2011-09-30 06:24 +0000
          Re: Iterate over the adjacent elements in a matix container Nobody <nobody@nowhere.com> - 2011-09-30 20:55 +0100
          Re: Iterate over the adjacent elements in a matix container Richard Damon <news.x.richarddamon@xoxy.net> - 2011-09-30 17:07 -0400
  Re: Iterate over the adjacent elements in a matix container Krice <paulkp@mbnet.fi> - 2011-09-27 03:37 -0700
  Re: Iterate over the adjacent elements in a matix container Alexander <alvatov@gmail.com> - 2011-09-29 10:47 -0700
    Re: Iterate over the adjacent elements in a matix container "Paul" <pchristor@yahoo.co.uk> - 2011-09-30 01:28 +0100
    Re: Iterate over the adjacent elements in a matix container Juha Nieminen <nospam@thanks.invalid> - 2011-09-30 06:19 +0000
    Re: Iterate over the adjacent elements in a matix container "Paul" <pchristor@yahoo.co.uk> - 2011-10-02 05:16 +0100
      Re: Iterate over the adjacent elements in a matix container "Paul" <pchrist<nospam>or@yahoo.co.uk> - 2011-10-03 05:31 +0100
        Re: Iterate over the adjacent elements in a matix container "Paul" <pchrist<nospam>or@yahoo.co.uk> - 2011-10-03 05:47 +0100

csiph-web