Re: Profiling, recursive func slower than imperative, normal?

[Jean-Paul Calderone]

On Wed, 16 Apr 2008 13:18:22 -0700 (PDT), sk*******@yahoo.se wrote:

>the 0.409 vs 0.095 is the total times right?
so the imperative function is >4 times faster than the recursive.
or what does tottime stand for?

is this always the case that the recursive function is slower?
the gain is less code?

are some functions only implementable recursively?

Function calls (recursive or otherwise) are more expensive than
for loops, so the version that replaces recursion with a loop is
faster.

Any function can be implemented without recursion, although it isn't
always easy or fun.

Jean-Paul

[s0suk3]

On Apr 16, 3:27 pm, Jean-Paul Calderone <[e-mail]:

Any function can be implemented without recursion, although it isn't
always easy or fun.

Jean-Paul

Really? I'm curious about that, I can't figure out how that would
work. Could give an example? Say, for example, the typical: walking
through the file system hierarchy (without using os.walk(), which uses
recursion anyway!).

[Gabriel Genellina]

En Wed, 16 Apr 2008 17:53:16 -0300, <s0****@gmail.comescribió:

On Apr 16, 3:27 pm, Jean-Paul Calderone <[e-mail]:

>Any function can be implemented without recursion, although it isn't
always easy or fun.

Really? I'm curious about that, I can't figure out how that would
work. Could give an example? Say, for example, the typical: walking
through the file system hierarchy (without using os.walk(), which uses
recursion anyway!).

Use a queue of pending directories to visit:

start with empty queue
queue.put(starting dir)
while queue is not empty:
dir = queue.get()
list names in dir
for each name:
if is subdirectory: queue.put(name)
else: process file

--
Gabriel Genellina

[Robert Bossy]

Gabriel Genellina wrote:

En Wed, 16 Apr 2008 17:53:16 -0300, <s0****@gmail.comescribió:

>On Apr 16, 3:27 pm, Jean-Paul Calderone <[e-mail]:

>>Any function can be implemented without recursion, although it isn't
always easy or fun.

Really? I'm curious about that, I can't figure out how that would
work. Could give an example? Say, for example, the typical: walking
through the file system hierarchy (without using os.walk(), which uses
recursion anyway!).

Use a queue of pending directories to visit:

start with empty queue
queue.put(starting dir)
while queue is not empty:
dir = queue.get()
list names in dir
for each name:
if is subdirectory: queue.put(name)
else: process file

Hi,

In that case, I'm not sure you get any performance gain since the queue
has basically the same role as the stack in the recursive version. A
definitive answer calls for an actual test, though.

Anyway if you want to process the tree depth-first, the queue version
falls in the "not fun" category.

Cheers,
RB

[MRAB]

On Apr 17, 9:39 am, Robert Bossy <[e-mail]:

Gabriel Genellina wrote:

En Wed, 16 Apr 2008 17:53:16 -0300, <[e-mail]ó:

On Apr 16, 3:27 pm, Jean-Paul Calderone <[e-mail]:

>Any function can be implemented without recursion, although it isn't
always easy or fun.

Really? I'm curious about that, I can't figure out how that would
work. Could give an example? Say, for example, the typical: walking
through the file system hierarchy (without using os.walk(), which uses
recursion anyway!).

Use a queue of pending directories to visit:

start with empty queue
queue.put(starting dir)
while queue is not empty:
dir = queue.get()
list names in dir
for each name:
if is subdirectory: queue.put(name)
else: process file

Hi,

In that case, I'm not sure you get any performance gain since the queue
has basically the same role as the stack in the recursive version. A
definitive answer calls for an actual test, though.

Anyway if you want to process the tree depth-first, the queue version
falls in the "not fun" category.

If you store the folders in a queue (push onto one end and pop from
the other end) the search is breadth-first; if you store the folders
in a stack (push onto one end and pop from the same end) the search is
depth-first. Simple really! :-)

[Terry Reedy]

|In that case, I'm not sure you get any performance gain since the queue
|has basically the same role as the stack in the recursive version. A
|definitive answer calls for an actual test, though.

The potential gain comes from not incurring function call overhead and only
queueing or stacking the exact data needed.