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

Discussion in 'Python' started by Jean-Paul Calderone, Apr 16, 2008.

  1. On Wed, 16 Apr 2008 13:18:22 -0700 (PDT), 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
     
    Jean-Paul Calderone, Apr 16, 2008
    #1
    1. Advertising

  2. Jean-Paul Calderone

    Guest

    On Apr 16, 3:27 pm, Jean-Paul Calderone <> wrote:

    > 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!).
     
    , Apr 16, 2008
    #2
    1. Advertising

  3. En Wed, 16 Apr 2008 17:53:16 -0300, <> escribió:

    > On Apr 16, 3:27 pm, Jean-Paul Calderone <> wrote:
    >
    >> 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
     
    Gabriel Genellina, Apr 16, 2008
    #3
  4. Jean-Paul Calderone

    Robert Bossy Guest

    Gabriel Genellina wrote:
    > En Wed, 16 Apr 2008 17:53:16 -0300, <> escribió:
    >
    >
    >> On Apr 16, 3:27 pm, Jean-Paul Calderone <> wrote:
    >>
    >>
    >>> 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
     
    Robert Bossy, Apr 17, 2008
    #4
  5. Jean-Paul Calderone

    MRAB Guest

    On Apr 17, 9:39 am, Robert Bossy <> wrote:
    > Gabriel Genellina wrote:
    > > En Wed, 16 Apr 2008 17:53:16 -0300, <> escribió:

    >
    > >> On Apr 16, 3:27 pm, Jean-Paul Calderone <> wrote:

    >
    > >>> 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! :)
     
    MRAB, Apr 17, 2008
    #5
  6. Jean-Paul Calderone

    Terry Reedy Guest

    |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.
     
    Terry Reedy, Apr 17, 2008
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Andre Charbonneau

    XPath queries getting slower and slower...

    Andre Charbonneau, Feb 15, 2005, in forum: Java
    Replies:
    0
    Views:
    575
    Andre Charbonneau
    Feb 15, 2005
  2. CRON
    Replies:
    24
    Views:
    203,911
    Adrienne Boswell
    Jun 20, 2006
  3. Johnny
    Replies:
    3
    Views:
    486
    Robert Kern
    Aug 23, 2005
  4. Replies:
    1
    Views:
    268
    Terry Reedy
    Apr 17, 2008
  5. Leo Jay
    Replies:
    1
    Views:
    305
Loading...

Share This Page