470,596 Members | 1,564 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 470,596 developers. It's quick & easy.

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

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
Jun 27 '08 #1
5 882
On Apr 16, 3:27 pm, Jean-Paul Calderone <exar...@divmod.comwrote:
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!).
Jun 27 '08 #2
En Wed, 16 Apr 2008 17:53:16 -0300, <s0****@gmail.comescribió:
On Apr 16, 3:27 pm, Jean-Paul Calderone <exar...@divmod.comwrote:
>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

Jun 27 '08 #3
Gabriel Genellina wrote:
En Wed, 16 Apr 2008 17:53:16 -0300, <s0****@gmail.comescribió:

>On Apr 16, 3:27 pm, Jean-Paul Calderone <exar...@divmod.comwrote:

>>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
Jun 27 '08 #4
On Apr 17, 9:39 am, Robert Bossy <Robert.Bo...@jouy.inra.frwrote:
Gabriel Genellina wrote:
En Wed, 16 Apr 2008 17:53:16 -0300, <s0s...@gmail.comescribió:
On Apr 16, 3:27 pm, Jean-Paul Calderone <exar...@divmod.comwrote:
>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! :-)
Jun 27 '08 #5

|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.

Jun 27 '08 #6

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

7 posts views Thread by aurora | last post: by
1 post views Thread by prathamesh | last post: by
3 posts views Thread by Davy | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.