Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Iterate over the adjacent elements in a matix container

Reply
Thread Tools

Iterate over the adjacent elements in a matix container

 
 
Nobody
Guest
Posts: n/a
 
      09-30-2011
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.

 
Reply With Quote
 
 
 
 
Richard Damon
Guest
Posts: n/a
 
      09-30-2011
On 9/30/11 2:24 AM, Juha Nieminen wrote:
> Richard Damon<(E-Mail Removed)> 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?
>
> Note that by using a stack you are not really saving any memory. You
> will still be storing O(n) amount of data (where n is the number of nodes
> that have to be marked). In fact, depending a bit on the situation, the
> breadth-first search may end up storing more data than the depth-first
> search (although it's true that in some cases it may be the other way
> around).
>
> Anyways, your concern seems to not be the amount of data needed to
> perform the task, but the recursion. Why? What exactly is the problem?



Note that there are a couple of issues here. One is that a level of
recursion cost a lot more memory space than saving a few locations to
iterate in a program controlled resource than a recursive call. Remember
that a level of recursion is going to create new copies of every
automatic variable used in the function, as opposed to just what is
needed to keep track locations to be filled.

A second issue is that recursion grows the program stack space, and
there is no way (portably) of checking for program stack overflow, while
you can check for running out of memory in the heap or program defined
memory structure. (Not every program runs on machines with gigabytes of
RAM).

Also, in typical worse case type configurations, a depth first path is
going to trace down to a significantly higher depth than a breadth first
search, as after you run out to what would seem to be a maximum distance
away, the depth first search will turn around and come back and
eventually hit most of the open cells in a deep path, it may
occasionally trap it self, but after it backs out a few steps, it will
find the deeper path. For a 200x200 flood file, I would expect it to get
at least 30,000 levels deep. On the other hand, a breadth first search
will tend to generate an expanding ring only a couple of cells thick,
needing maybe 1600 locations recorded at a given time for the same area.
The key here is that breadth first limits itself to first looking near
where it has done work, and finishes cells, so we don't need to revisit
them. Depth first can't tell that a later path will get to a cell at a
shorted depth. This is a common issue with traversing highly connected
paths.

There is nothing inherently wrong with recursion, but it isn't always
the right tool, and often is a somewhat heavy handed one. An important
thing when using recursion is to make sure that it does terminate, and
in a reasonable number of levels. Removing recursion and replacing it
with iteration is a common optimization. (For an extreme case compare
recursive and iterative version of factorial or Fibonacci calculations).
 
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
number of distinct elements in a const container and iterating over the distinct elements Hicham Mouline C++ 1 04-11-2010 10:56 AM
2 dimensional parity matix, pattern qty? Trs80 Cisco 0 06-21-2009 02:06 AM
How do you iterate over a List and remove elements? Knute Johnson Java 16 08-31-2007 05:28 AM
freeing a matix Michael Goerz C Programming 10 12-04-2006 06:41 AM
Copy elements from one STL container to another STL container Marko.Cain.23@gmail.com C++ 4 02-16-2006 05:03 PM



Advertisments