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

Groups > comp.lang.python > #89770 > unrolled thread

Throw the cat among the pigeons

Back to article view | Back to comp.lang.python

Contents

  Throw the cat among the pigeons Cecil Westerhof <Cecil@decebal.nl> - 2015-05-02 16:20 +0200
    Re: Throw the cat among the pigeons Cecil Westerhof <Cecil@decebal.nl> - 2015-05-03 17:12 +0200
      Re: Throw the cat among the pigeons Paul  Moore <p.f.moore@gmail.com> - 2015-05-05 08:47 -0700
        Re: Throw the cat among the pigeons Cecil Westerhof <Cecil@decebal.nl> - 2015-05-05 18:18 +0200
          Re: Throw the cat among the pigeons Dave Angel <davea@davea.name> - 2015-05-05 14:45 -0400
            Re: Throw the cat among the pigeons Cecil Westerhof <Cecil@decebal.nl> - 2015-05-05 21:42 +0200
              Re: Throw the cat among the pigeons Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-06 12:57 +1000
                Re: Throw the cat among the pigeons Chris Angelico <rosuav@gmail.com> - 2015-05-06 14:03 +1000
          Re: Throw the cat among the pigeons Ian Kelly <ian.g.kelly@gmail.com> - 2015-05-05 14:30 -0600
          Re: Throw the cat among the pigeons Terry Reedy <tjreedy@udel.edu> - 2015-05-05 16:46 -0400
            Re: Throw the cat among the pigeons Cecil Westerhof <Cecil@decebal.nl> - 2015-05-05 23:12 +0200
              Re: Throw the cat among the pigeons Terry Reedy <tjreedy@udel.edu> - 2015-05-05 19:22 -0400
          Re: Throw the cat among the pigeons Dave Angel <davea@davea.name> - 2015-05-05 17:00 -0400
          Re: Throw the cat among the pigeons Ian Kelly <ian.g.kelly@gmail.com> - 2015-05-05 15:23 -0600
            Re: Throw the cat among the pigeons Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-06 11:27 +1000
              Re: Throw the cat among the pigeons Ian Kelly <ian.g.kelly@gmail.com> - 2015-05-05 23:58 -0600
                Re: Throw the cat among the pigeons Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-06 17:08 +1000
                  Re: Throw the cat among the pigeons Ian Kelly <ian.g.kelly@gmail.com> - 2015-05-06 10:17 -0600
                  Re: Throw the cat among the pigeons Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-05-06 21:23 +0100
          Re: Throw the cat among the pigeons Ian Kelly <ian.g.kelly@gmail.com> - 2015-05-05 15:39 -0600
          Re: Throw the cat among the pigeons Dave Angel <davea@davea.name> - 2015-05-05 17:55 -0400
          Re: Throw the cat among the pigeons Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-06 12:19 +1000
    Re: Throw the cat among the pigeons Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-06 14:05 +1000
      Re: Throw the cat among the pigeons Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-05-06 16:26 +1000
        Re: Throw the cat among the pigeons Dave Angel <davea@davea.name> - 2015-05-06 09:12 -0400
          Re: Throw the cat among the pigeons Dan Sommers <dan@tombstonezero.net> - 2015-05-07 03:16 +0000
        Re: Throw the cat among the pigeons Chris Angelico <rosuav@gmail.com> - 2015-05-06 23:55 +1000
        Re: Throw the cat among the pigeons Dave Angel <davea@davea.name> - 2015-05-06 10:22 -0400
        Re: Throw the cat among the pigeons Paul Rubin <no.email@nospam.invalid> - 2015-05-06 08:12 -0700
          Re: Throw the cat among the pigeons Alain Ketterlin <alain@universite-de-strasbourg.fr.invalid> - 2015-05-06 17:36 +0200
            Re: Throw the cat among the pigeons Dave Angel <davea@davea.name> - 2015-05-06 16:23 -0400
              Re: Throw the cat among the pigeons Alain Ketterlin <alain@universite-de-strasbourg.fr.invalid> - 2015-05-07 11:14 +0200
                Re: Throw the cat among the pigeons Chris Angelico <rosuav@gmail.com> - 2015-05-07 19:38 +1000
          Re: Throw the cat among the pigeons Ian Kelly <ian.g.kelly@gmail.com> - 2015-05-06 09:47 -0600
            Re: Throw the cat among the pigeons Paul Rubin <no.email@nospam.invalid> - 2015-05-06 10:24 -0700

Page 1 of 2  [1] 2  Next page →

#89770 — Throw the cat among the pigeons

I am throwing the cat among the pigeons. ;-)

In another thread I mentioned that I liked to have tail recursion in
Python. To be clear not automatic, but asked for.

Looking at the replies I did hit a nerve. But I still want to
continue.

Some things are better expressed recursively for the people reading
the code. But there are two problems with that:
- You can get out of stack space
- It is less efficient

Most of the time the first problem is the most important.

When I write factorial (I know it is already written, but I use it as
an example to show a point), the recursive variant can not be called
with 1.000 without tail recursion. So for functions that could go very
deep, tail recursion would be a blessing.

By the way: I think that even if the recursion does not go further as
500, it is still a good idea to use tail recursion. Why use stack
space when it is not necessary?

But to my surprise tail recursion could even be more efficient. I
wrote two different versions of factorial with self implemented tail
recursion. For bigger values both are more efficient. And I expect
that if the tail recursion is done by the compiler instead of by hand,
it will be a little faster still.

This is the output a run of my code:
    15:05:50: Start with the time needed to calculate 100000 times
    15:05:50: Timing factorial_iterative         (985): 32.265420768002514
    15:06:22: Timing factorial_recursive         (985): 58.381072121992474
    15:07:21: Timing factorial_recursive_old     (985): 64.46238571999129
    15:08:25: Timing factorial_tail_recursion    (985): 40.43312480399618
    15:09:06: Timing factorial_tail_recursion_old(985): 39.70765891499468

    15:09:45: Start with the time needed to calculate 1 times
              No recursive, because without tail recursion you would run out of stack space
    15:09:45: Timing factorial_iterative         (100000): 3.9112528519763146
    15:09:49: Timing factorial_tail_recursion    (100000): 3.928693111985922
    15:09:53: Timing factorial_tail_recursion_old(100000): 4.305187558988109

    15:09:58: Timing factorial_iterative         (200000): 18.081113666004967
    15:10:16: Timing factorial_tail_recursion    (200000): 16.660855480993632
    15:10:32: Timing factorial_tail_recursion_old(200000): 18.169589380006073

    15:10:51: Timing factorial_iterative         (300000): 41.79109025900834
    15:11:32: Timing factorial_tail_recursion    (300000): 38.368264676013496
    15:12:11: Timing factorial_tail_recursion_old(300000): 41.646923307009274

    15:12:52: Timing factorial_iterative         (400000): 78.35287749301642
    15:14:11: Timing factorial_tail_recursion    (400000): 73.17889478098368
    15:15:24: Timing factorial_tail_recursion_old(400000): 89.64840986899799

    15:16:53: Timing factorial_iterative         (500000): 154.76221033901675
    15:19:28: Timing factorial_tail_recursion    (500000): 130.3837693700043
    15:21:39: Timing factorial_tail_recursion_old(500000): 131.41286378499353

    15:23:50: These result show that tail recursion can be interesting
              They show also that the way you use tail recursion is important

As said the most important reason is that code is often more elegant
when written recursively, but you cannot do that if it is possible
that the recursion can go very deep. But if recursively code would be
more elegant and faster, then it would really be interesting to have.

I would not opt for automatically using tail recursion, but only when
the programmer says so. And if it is not possible, that should be an
error.

To make sure it was not a fluke, I ran it again:
    16:01:30: Start with the time needed to calculate 100000 times
    16:01:30: Timing factorial_iterative         (985): 31.465190444985637
    16:02:01: Timing factorial_recursive         (985): 54.562154764978914
    16:02:56: Timing factorial_recursive_old     (985): 55.56128695001826
    16:03:52: Timing factorial_tail_recursion    (985): 36.27355203201296
    16:04:28: Timing factorial_tail_recursion_old(985): 40.36879472099827

    16:05:08: Start with the time needed to calculate 1 times
              No recursive, because without tail recursion you would run out of stack space
    16:05:08: Timing factorial_iterative         (100000): 3.764512833993649
    16:05:12: Timing factorial_tail_recursion    (100000): 3.8083034529990982
    16:05:16: Timing factorial_tail_recursion_old(100000): 4.107901128008962

    16:05:20: Timing factorial_iterative         (200000): 16.076719653996406
    16:05:36: Timing factorial_tail_recursion    (200000): 16.108007609989727
    16:05:52: Timing factorial_tail_recursion_old(200000): 17.71343147099833

    16:06:10: Timing factorial_iterative         (300000): 37.82596729800571
    16:06:48: Timing factorial_tail_recursion    (300000): 40.308226338995155
    16:07:28: Timing factorial_tail_recursion_old(300000): 41.254319412022596

    16:08:09: Timing factorial_iterative         (400000): 77.01277641401975
    16:09:26: Timing factorial_tail_recursion    (400000): 73.4060631209868
    16:10:40: Timing factorial_tail_recursion_old(400000): 80.26402168802451

    16:12:00: Timing factorial_iterative         (500000): 131.84731978402124
    16:14:12: Timing factorial_tail_recursion    (500000): 125.31950747498195
    16:16:17: Timing factorial_tail_recursion_old(500000): 133.39186109701404

    16:18:30: These result show that tail recursion can be interesting
              They show also that the way you use tail recursion is important


-- 
Cecil Westerhof
Senior Software Engineer
LinkedIn: http://www.linkedin.com/in/cecilwesterhof

[toc] | [next] | [standalone]

#89871

Op Saturday 2 May 2015 16:20 CEST schreef Cecil Westerhof:

> I am throwing the cat among the pigeons. ;-)
>
> In another thread I mentioned that I liked to have tail recursion in
> Python. To be clear not automatic, but asked for.
>
> Looking at the replies I did hit a nerve. But I still want to
> continue.
>
> Some things are better expressed recursively for the people reading
> the code. But there are two problems with that:
> - You can get out of stack space
> - It is less efficient
>
> Most of the time the first problem is the most important.
>
> When I write factorial (I know it is already written, but I use it
> as an example to show a point), the recursive variant can not be
> called with 1.000 without tail recursion. So for functions that
> could go very deep, tail recursion would be a blessing.
>
> By the way: I think that even if the recursion does not go further
> as 500, it is still a good idea to use tail recursion. Why use stack
> space when it is not necessary?

I pushed the example to GitHub:
    https://github.com/CecilWesterhof/PythonLibrary/blob/master/mathDecebal.py

-- 
Cecil Westerhof
Senior Software Engineer
LinkedIn: http://www.linkedin.com/in/cecilwesterhof

[toc] | [prev] | [next] | [standalone]

#89970

On Sunday, 3 May 2015 16:23:59 UTC+1, Cecil Westerhof  wrote:
> > By the way: I think that even if the recursion does not go further
> > as 500, it is still a good idea to use tail recursion. Why use stack
> > space when it is not necessary?
> 
> I pushed the example to GitHub:
>     https://github.com/CecilWesterhof/PythonLibrary/blob/master/mathDecebal.py

You already know this, as your code shows, but tail call recursion elimination is only possible when you have a *direct* tail call (one with the result of the tail call returned immediately to the caller). Even the standard trivial factorial example doesn't have a direct tail call, without rewriting to use an accumulator variable. Which is a non-intuitive transformation to anyone who's not familiar with recursive functional languages and their idioms.

If you're rewriting your recursive function *anyway*, it's not that much harder in many (most?) cases to rewrite it iteratively.

An example of a function that naturally uses direct tail call recursion, but which doesn't have a simple iterative rewrite, would be more compelling. Not particularly compelling (to me, anyway) even so, but still better than factorial or fibonnaci examples.

Paul

[toc] | [prev] | [next] | [standalone]

#89973

Op Tuesday 5 May 2015 17:47 CEST schreef Paul Moore:

> On Sunday, 3 May 2015 16:23:59 UTC+1, Cecil Westerhof  wrote:
>>> By the way: I think that even if the recursion does not go further
>>> as 500, it is still a good idea to use tail recursion. Why use
>>> stack space when it is not necessary?
>>
>> I pushed the example to GitHub:
>> https://github.com/CecilWesterhof/PythonLibrary/blob/master/mathDecebal.py
>
> You already know this, as your code shows, but tail call recursion
> elimination is only possible when you have a *direct* tail call (one
> with the result of the tail call returned immediately to the
> caller). Even the standard trivial factorial example doesn't have a
> direct tail call, without rewriting to use an accumulator variable.
> Which is a non-intuitive transformation to anyone who's not familiar
> with recursive functional languages and their idioms.
>
> If you're rewriting your recursive function *anyway*, it's not that
> much harder in many (most?) cases to rewrite it iteratively.
>
> An example of a function that naturally uses direct tail call
> recursion, but which doesn't have a simple iterative rewrite, would
> be more compelling. Not particularly compelling (to me, anyway) even
> so, but still better than factorial or fibonnaci examples.

Well, I did not write many tail recursive functions. But what surprised
me was that for large values the ‘tail recursive’ version was more
efficient as the iterative version. And that was with myself
implementing the tail recursion. I expect the code to be more
efficient when the compiler implements the tail recursion.

-- 
Cecil Westerhof
Senior Software Engineer
LinkedIn: http://www.linkedin.com/in/cecilwesterhof

[toc] | [prev] | [next] | [standalone]

#89990

On 05/05/2015 12:18 PM, Cecil Westerhof wrote:

>
> Well, I did not write many tail recursive functions. But what surprised
> me was that for large values the ‘tail recursive’ version was more
> efficient as the iterative version. And that was with myself
> implementing the tail recursion. I expect the code to be more
> efficient when the compiler implements the tail recursion.
>


You've said that repeatedly, so I finally took a look at your webpage
 
https://github.com/CecilWesterhof/PythonLibrary/blob/master/mathDecebal.py

I didn't have your framework to call the code, so I just extracted some 
functions and did some testing.  I do see some differences, where the 
so-called tail_recursive functions are sometimes faster, but I did some 
investigating to try to determine why.


I came up with the conclusion that sometimes the multiply operation 
takes longer than other times.  And in particular, i can see more 
variation between the two following loops than between your two functions.


def factorial_iterative(x, simple=False):
     assert x >= 0
     result = 1
     j=2
     if not simple:
         for i in range(2, x + 1):
             result *= i
             j += 1
     else:
         for i in range(2, x + 1):
             result *= j
             j += 1
             pass

     return result

When the "simple" is True, the function takes noticeably and 
consistently longer.  For example, it might take 116 instead of 109 
seconds.  For the same counts, your code took 111.

I've looked at dis.dis(factorial_iterative), and can see no explicit 
reason for the difference.



-- 
DaveA

[toc] | [prev] | [next] | [standalone]

#89997

Op Tuesday 5 May 2015 20:45 CEST schreef Dave Angel:

> On 05/05/2015 12:18 PM, Cecil Westerhof wrote:
>
>>
>> Well, I did not write many tail recursive functions. But what
>> surprised me was that for large values the ‘tail recursive’ version
>> was more efficient as the iterative version. And that was with
>> myself implementing the tail recursion. I expect the code to be
>> more efficient when the compiler implements the tail recursion.
>>
>
>
> You've said that repeatedly, so I finally took a look at your
> webpage
>
> https://github.com/CecilWesterhof/PythonLibrary/blob/master/mathDecebal.py
>
> I didn't have your framework to call the code, so I just extracted
> some functions and did some testing.

I definitely need to take care of documentation.

It can be called with:
    python3 mathDecebal.py --factorial

The problem is that it will do correctness and speed test. I have to
split those in two different things. And use a different file for
both.

Maybe make a directory test and put a correctness_<function>.py and a
speed_<function>.py.



> I do see some differences,
> where the so-called tail_recursive functions are sometimes faster,
> but I did some investigating to try to determine why.
>
>
> I came up with the conclusion that sometimes the multiply operation
> takes longer than other times.  And in particular, i can see more
> variation between the two following loops than between your two
> functions.
>
>
> def factorial_iterative(x, simple=False):
> assert x >= 0
> result = 1
> j=2
> if not simple:
> for i in range(2, x + 1):
> result *= i
> j += 1
> else:
> for i in range(2, x + 1):
> result *= j
> j += 1
> pass
>
> return result
>
> When the "simple" is True, the function takes noticeably and
> consistently longer.  For example, it might take 116 instead of 109
> seconds.  For the same counts, your code took 111.
>
> I've looked at dis.dis(factorial_iterative), and can see no explicit
> reason for the difference.

I would say that a variable that is filled by a range is different as
a normal variable. Do not ask me why. ;-)

Even if you (general not personal you) think that the tail recursion
is a waist of time, this is an interesting result I think.

-- 
Cecil Westerhof
Senior Software Engineer
LinkedIn: http://www.linkedin.com/in/cecilwesterhof

[toc] | [prev] | [next] | [standalone]

#90022

On Wed, 6 May 2015 05:42 am, Cecil Westerhof wrote:

> I would say that a variable that is filled by a range is different as
> a normal variable. Do not ask me why. ;-)


I would say that you are wrong. If I have understood you correctly, that
cannot possibly be the case in Python, all Python variables work the same
way[1], and none of them can remember where they came from.






[1] Well, technically local variables and global variables are implemented
differently, locals inside a function use a C array and globals use a dict,
but apart from a few implementation details like that, any two variables in
the same scope[2] operate identically.

[2] Anyone who raises the issue of exec() or import * inside a function body
in Python 2 will be slapped with a halibut.

-- 
Steven

[toc] | [prev] | [next] | [standalone]

#90024

On Wed, May 6, 2015 at 12:57 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> On Wed, 6 May 2015 05:42 am, Cecil Westerhof wrote:
>
>> I would say that a variable that is filled by a range is different as
>> a normal variable. Do not ask me why. ;-)
>
>
> I would say that you are wrong. If I have understood you correctly, that
> cannot possibly be the case in Python, all Python variables work the same
> way[1], and none of them can remember where they came from.

My reading of the code was that one had two variables and the other
had just one. Could be the noise in the numbers came from cache
locality differences.

No difference between the variables, just a peculiarity of CPUs and
how they use memory.

ChrisA

[toc] | [prev] | [next] | [standalone]

#89999

On Tue, May 5, 2015 at 12:45 PM, Dave Angel <davea@davea.name> wrote:
> When the "simple" is True, the function takes noticeably and consistently
> longer.  For example, it might take 116 instead of 109 seconds.  For the
> same counts, your code took 111.

I can't replicate this. What version of Python is it, and what value
of x are you testing with?

> I've looked at dis.dis(factorial_iterative), and can see no explicit reason
> for the difference.

My first thought is that maybe it's a result of the branch. Have you
tried swapping the branches, or reimplementing as separate functions
and comparing?

[toc] | [prev] | [next] | [standalone]

#90000

On 5/5/2015 12:18 PM, Cecil Westerhof wrote:
> Op Tuesday 5 May 2015 17:47 CEST schreef Paul Moore:
>
>> On Sunday, 3 May 2015 16:23:59 UTC+1, Cecil Westerhof  wrote:
>>>> By the way: I think that even if the recursion does not go further
>>>> as 500, it is still a good idea to use tail recursion. Why use
>>>> stack space when it is not necessary?
>>>
>>> I pushed the example to GitHub:
>>> https://github.com/CecilWesterhof/PythonLibrary/blob/master/mathDecebal.py
>>
>> You already know this, as your code shows, but tail call recursion
>> elimination is only possible when you have a *direct* tail call (one

An 'indirect tail call' would not be a tail call.

>> with the result of the tail call returned immediately to the
>> caller). Even the standard trivial factorial example doesn't have a
>> direct tail call,  without rewriting to use an accumulator variable.
>> Which is a non-intuitive transformation to anyone who's not familiar
>> with recursive functional languages and their idioms.
>>
>> If you're rewriting your recursive function *anyway*, it's not that
>> much harder in many (most?) cases to rewrite it iteratively.

For count functions, the main change between tail recursion and while 
iteration is replacing 'if' with 'while' and converting the tail call to 
assignment.  (One may have to reverse the if-else first to put the tail 
call in the if branch.)

from math import factorial as fac
print(fac(0), fac(1), fac(2), fac(6))

def fac_rt(n, i=2, res=1):
     if i <= n:
         return fac_rt(n, i+1, res*i)
     else:
         return res

def fac_iw(n):
     i = 2
     res = 1
     while i <= n:
         i, res = i+1, res*i
     return res

for i in (0, 1, 2, 6):
     print(fac(i) == fac_rt(i) == fac_iw(i))

 >>>
1 1 2 720
True
True
True
True

For collection functions that process each item once, 'for item in 
collection: ...' is nearly always easier to write in the first place.

>> An example of a function that naturally uses direct tail call
>> recursion, but which doesn't have a simple iterative rewrite, would
>> be more compelling.

Simple, easily converted functions like the above, with one recursive 
call in one branch of an if-else, are the most common.  Something with 
multiple mutually exclusive tail calls, like the following

def f_rt1(*args):
   if nonbase1:
     return f(*revised-args1)
   elif base_condition:
     return base(args)
   else:
     return f(*revised-args2)

must be converted to if-else with all tail calls in the if branch.

def f_rt2(*args):
   if not base_condition:
     if nonbase1:
       return f(*revised-args1)
     else:
       return f(*revised-args2)
   else:
     return base(args)

Conversion would then be simple.  The complication is that the 
'base_condition' in the original version might not really be the base 
condition due to a dependence on nonbase1 being false.  This is a 
generic problem with reordering if-elif statements.

For non-linear (branching) recursion, in which multiple recursive calls 
may be made for one function call, the last recursive call may be a tail 
call.  An example is in-place quick sort.  Eliminating just the tail 
call may not be simple, but it also does not eliminate the possibility 
of blowing the call stack.  To do that, one must eliminate all recursive 
calls by adding explicit stacks.

> Well, I did not write many tail recursive functions. But what surprised
> me was that for large values the ‘tail recursive’ version was more
> efficient as the iterative version.

In your first thread, what you mislabelled 'tail recursive version' was 
an iterative while loop version while the 'iterative version' was an 
iterative for loop version.  In this thread, you just posted timings 
without code. I will not believe your claim until I see one file that I 
can run myself with an actual tail recursive function, as above, that 
beats the equivalent while or for loop version.

-- 
Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]

#90003

Op Tuesday 5 May 2015 22:46 CEST schreef Terry Reedy:

>> Well, I did not write many tail recursive functions. But what
>> surprised me was that for large values the ‘tail recursive’ version
>> was more efficient as the iterative version.
>
> In your first thread, what you mislabelled 'tail recursive version'
> was an iterative while loop version

That is because Python has no tail recursion, so I needed to program
the tail recursion myself. Tail recursion would do under the hood what
I did there manually.


> while the 'iterative version'
> was an iterative for loop version. In this thread, you just posted
> timings without code. I will not believe your claim until I see one
> file that I can run myself with an actual tail recursive function,
> as above, that beats the equivalent while or for loop version.

https://github.com/CecilWesterhof/PythonLibrary/blob/master/mathDecebal.py

-- 
Cecil Westerhof
Senior Software Engineer
LinkedIn: http://www.linkedin.com/in/cecilwesterhof

[toc] | [prev] | [next] | [standalone]

#90010

On 5/5/2015 5:12 PM, Cecil Westerhof wrote:
> Op Tuesday 5 May 2015 22:46 CEST schreef Terry Reedy:
>
>>> Well, I did not write many tail recursive functions. But what
>>> surprised me was that for large values the ‘tail recursive’ version
>>> was more efficient as the iterative version.
>>
>> In your first thread, what you mislabelled 'tail recursive version'
>> was an iterative while loop version
>
> That is because Python has no tail recursion,

Yes is does. Please stop using 'tail recursion' to refer to the absence 
of recursion or the process of removing recursion. I wrote a tail 
recursive function, and I believe you did too.

What Python does not have is automatic tail call optimization, or 
specifically, tail recursion *elimination*. Both possibilities, the 
general and specific, have been considered and rejected for excellent 
reasons. I hinted at some of them in my post.

See https://en.wikipedia.org/wiki/Tail_call
for 'tail recursion' and 'tail call elimination'

What I believe you showed is that a while loop can be faster than a more 
or less equivalent for loop that produces the same result by a slightly 
different method.  That is not surprising.  Relative timings for CPython 
vary a few percent between different combinations of Python version, C 
compiler and settings, operating system, and cpu and other hardware.

-- 
Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]

#90001

On 05/05/2015 04:30 PM, Ian Kelly wrote:
> On Tue, May 5, 2015 at 12:45 PM, Dave Angel <davea@davea.name> wrote:
>> When the "simple" is True, the function takes noticeably and consistently
>> longer.  For example, it might take 116 instead of 109 seconds.  For the
>> same counts, your code took 111.
>
> I can't replicate this. What version of Python is it, and what value
> of x are you testing with?
>
>> I've looked at dis.dis(factorial_iterative), and can see no explicit reason
>> for the difference.
>
> My first thought is that maybe it's a result of the branch. Have you
> tried swapping the branches, or reimplementing as separate functions
> and comparing?
>

Logic is quite simple:


def factorial_iterative(x, simple=False):
     assert x >= 0
     result = 1
     j=2
     if not simple:
         for i in range(2, x + 1):
             #print("range value is of type", type(i), "and value", i)
             #print("ordinary value is of type", type(j), "and value", j)
             result *= i
             j += 1
     else:
         for i in range(2, x + 1):
             result *= j
             j += 1

     return result

def loop(func, funcname, arg):
     start = time.time()
     for i in range(repeats):
         func(arg, True)
     print("{0}({1}) took {2:7.4}".format(funcname, arg, time.time()-start))

     start = time.time()
     for i in range(repeats):
         func(arg)
     print("{0}({1}) took {2:7.4}".format(funcname, arg, time.time()-start))

repeats = 1

and arg is 10**4
     loop(factorial_iterative,      "factorial_iterative      ", arg)

My actual program does the same thing with other versions of the 
function, including Cecil's factorial_tail_recursion, and my optimized 
version of that.


Python 3.4.0 (default, Apr 11 2014, 13:05:11)
[GCC 4.8.2] on linux

factorial_iterative      (100000) took   3.807
factorial_iterative      (100000) took   3.664

factorial_iterative      (200000) took   17.07
factorial_iterative      (200000) took    15.3

factorial_iterative      (300000) took   38.93
factorial_iterative      (300000) took   36.01


Note that I test them in the opposite order of where they appear in the 
function.  That's because I was originally using the simple flag to test 
an empty loop.  The empty loop is much quicker either way, so it's not 
the issue.  (But if it were, the for-range version is much quicker).

I think I'll take your last suggestion and write separate functions.



-- 
DaveA

[toc] | [prev] | [next] | [standalone]

#90002

On Tue, May 5, 2015 at 3:00 PM, Dave Angel <davea@davea.name> wrote:
> def loop(func, funcname, arg):
>     start = time.time()
>     for i in range(repeats):
>         func(arg, True)
>     print("{0}({1}) took {2:7.4}".format(funcname, arg, time.time()-start))
>
>     start = time.time()
>     for i in range(repeats):
>         func(arg)
>     print("{0}({1}) took {2:7.4}".format(funcname, arg, time.time()-start))

Note that you're explicitly passing True in one case but leaving the
default in the other. I don't know whether that might be responsible
for the difference you're seeing.

Also, it's best to use the timeit module for timing code, e.g.:

>>> from timeit import Timer
>>> t1 = Timer("factorial_iterative(100000, False)", "from __main__ import factorial_iterative")
>>> t1.repeat(10, number=1)
[3.8517245299881324, 3.7571076710009947, 3.7780062559759244,
3.848508063936606, 3.7627131739864126, 3.8278848479967564,
3.776115525048226, 3.83024005102925, 3.8322679550619796,
3.8195601429324597]
>>> min(_), sum(_) / len(_)
(3.7571076710009947, 3.8084128216956743)
>>> t2 = Timer("factorial_iterative(100000, True)", "from __main__ import factorial_iterative")
>>> t2.repeat(10, number=1)
[3.8363616950809956, 3.753201302024536, 3.7838632150087506,
3.7670978900277987, 3.805312803015113, 3.7682680500438437,
3.856655619922094, 3.796431727008894, 3.8224815409630537,
3.765664782957174]
>>> min(_), sum(_) / len(_)
(3.753201302024536, 3.7955338626052253)

As you can see, in my testing the True case was actually marginally
(probably not significantly) faster in both the min and the average.

[toc] | [prev] | [next] | [standalone]

#90020

On Wed, 6 May 2015 07:23 am, Ian Kelly wrote:

> On Tue, May 5, 2015 at 3:00 PM, Dave Angel <davea@davea.name> wrote:
>> def loop(func, funcname, arg):
>>     start = time.time()
>>     for i in range(repeats):
>>         func(arg, True)
>>     print("{0}({1}) took {2:7.4}".format(funcname, arg,
>>     time.time()-start))
>>
>>     start = time.time()
>>     for i in range(repeats):
>>         func(arg)
>>     print("{0}({1}) took {2:7.4}".format(funcname, arg,
>>     time.time()-start))
> 
> Note that you're explicitly passing True in one case but leaving the
> default in the other. I don't know whether that might be responsible
> for the difference you're seeing.

It will be responsible for *some* difference, it is certainly faster to pass
one argument than two, but likely an entirely trivial amount compared to
the time to iterate some large number of times.


> Also, it's best to use the timeit module for timing code, e.g.:
> 
>>>> from timeit import Timer
>>>> t1 = Timer("factorial_iterative(100000, False)", "from __main__ import
>>>> factorial_iterative") t1.repeat(10, number=1)
> [3.8517245299881324, 3.7571076710009947, 3.7780062559759244,
> 3.848508063936606, 3.7627131739864126, 3.8278848479967564,
> 3.776115525048226, 3.83024005102925, 3.8322679550619796,
> 3.8195601429324597]
>>>> min(_), sum(_) / len(_)
> (3.7571076710009947, 3.8084128216956743)

Only the minimum is statistically useful.

The reason is that every timing measurement has an error, due to random
fluctuations of the OS, CPU pipelining, caches, etc, but that error is
always positive. The noise always makes the code take longer to run, not
faster!

So we can imagine every measurement is made up of the "true" value T, plus
an error, where T = the perfectly repeatable timing that the function would
take to run if we could somehow eliminate every possible source of noise
and error in the system. We can't, of course, but we would like to estimate
T as closely as possible.

Without loss of generality, suppose we collect five timings:

times = [T+ε1, T+ε2, T+ε3, T+ε4, T+ε5]

where the epsilons ε are unknown errors due to noise. We don't know the
distribution of the errors, except that no epsilon can be less than zero.

We want an estimate for T, something which comes as close as possible to T.
It should be obvious that the following relationships hold:

mean(times) = T + mean([ε1, ε2, ε3, ε4, ε5])

min(times) = T + min([ε1, ε2, ε3, ε4, ε5])


in other words, both the mean of the timings and the minimum of the timings
are equivalent to the "true" timing, plus an error. It should also be
obvious that the mean of the epsilons must be larger than the smallest of
the errors (except in the miraculous case where all the epsilons are
exactly the same).

So the statistic with the minimum error is the minimum. Any other stat,
whether you use the mean, geometric mean, harmonic mean, mode, median, or
anything else, will have a larger error and be a worse estimate for
the "true" value T.

All because the errors are one-sided: they always make the timing take
longer, never less time.



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#90029

On Tue, May 5, 2015 at 7:27 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> Only the minimum is statistically useful.

I disagree. The minimum tells you how fast the code *can* run, under
optimal circumstances. The mean tells you how fast it *realistically*
runs, under typical load. Both can be useful to measure.

[toc] | [prev] | [next] | [standalone]

#90036

On Wednesday 06 May 2015 15:58, Ian Kelly wrote:

> On Tue, May 5, 2015 at 7:27 PM, Steven D'Aprano
> <steve+comp.lang.python@pearwood.info> wrote:
>> Only the minimum is statistically useful.
> 
> I disagree. The minimum tells you how fast the code *can* run, under
> optimal circumstances. The mean tells you how fast it *realistically*
> runs, under typical load. Both can be useful to measure.

Er, not even close. Running code using timeit is in no way the same as 
running code "for real" under realistic circumstances. The fact that you are 
running the function or code snippet in isolation, in its own scope, via 
exec, rather than as part of some larger script or application, should be a 
hint. timeit itself has overhead, so you cannot measure the time taken by 
the operation alone, you can only measure the time taken by the operation 
within the timeit environment. We have no reason to think that the 
distribution of noise under timeit will be even vaguely similar to the noise 
when running in production.

The purpose of timeit is to compare individual algorithms, in as close as 
possible to an equal footing with as little noise as possible. If you want 
to profile code used in a realistic application, use a profiler, not timeit. 
And even that doesn't tell you how fast the code would be alone, because the 
profiler adds overhead.

Besides, "typical load" is a myth -- there is no such thing. A high-end 
Windows web server getting ten thousand hits a minute, a virtual machine 
starved for RAM, a Mac laptop, a Linux server idling away with a load of 0.1 
all day... any of those machines could run your code. How can you *possibly* 
say what is typical? The very idea is absurd.



-- 
Steve

[toc] | [prev] | [next] | [standalone]

#90063

On Wed, May 6, 2015 at 1:08 AM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> On Wednesday 06 May 2015 15:58, Ian Kelly wrote:
>
>> On Tue, May 5, 2015 at 7:27 PM, Steven D'Aprano
>> <steve+comp.lang.python@pearwood.info> wrote:
>>> Only the minimum is statistically useful.
>>
>> I disagree. The minimum tells you how fast the code *can* run, under
>> optimal circumstances. The mean tells you how fast it *realistically*
>> runs, under typical load. Both can be useful to measure.
>
> Er, not even close. Running code using timeit is in no way the same as
> running code "for real" under realistic circumstances. The fact that you are
> running the function or code snippet in isolation, in its own scope, via
> exec, rather than as part of some larger script or application, should be a
> hint. timeit itself has overhead, so you cannot measure the time taken by
> the operation alone, you can only measure the time taken by the operation
> within the timeit environment. We have no reason to think that the
> distribution of noise under timeit will be even vaguely similar to the noise
> when running in production.

You also can't be sure that the base time taken by the operation in
your development environment will be comparable to the time taken in
production; different system architectures may produce different
results, and what is faster on your workstation may be slower on a
server.

Also, different algorithms may react to load differently. For example,
an algorithm that goes to different parts of memory frequently may
start thrashing sooner than an algorithm with better spatial locality
if the system is paging a lot. I'll grant that just computing the
means on a workstation that is not under a controlled load is not the
best way to measure this -- but a difference in mean that is not
simply proportional to the difference in min is still potentially
useful information.

> The purpose of timeit is to compare individual algorithms, in as close as
> possible to an equal footing with as little noise as possible. If you want
> to profile code used in a realistic application, use a profiler, not timeit.
> And even that doesn't tell you how fast the code would be alone, because the
> profiler adds overhead.
>
> Besides, "typical load" is a myth -- there is no such thing. A high-end
> Windows web server getting ten thousand hits a minute, a virtual machine
> starved for RAM, a Mac laptop, a Linux server idling away with a load of 0.1
> all day... any of those machines could run your code. How can you *possibly*
> say what is typical? The very idea is absurd.

Agreed.

[toc] | [prev] | [next] | [standalone]

#90072

On 06/05/2015 17:17, Ian Kelly wrote:
> On Wed, May 6, 2015 at 1:08 AM, Steven D'Aprano
>>
>> Besides, "typical load" is a myth -- there is no such thing. A high-end
>> Windows web server getting ten thousand hits a minute, a virtual machine
>> starved for RAM, a Mac laptop, a Linux server idling away with a load of 0.1
>> all day... any of those machines could run your code. How can you *possibly*
>> say what is typical? The very idea is absurd.
>
> Agreed.
>

I must disagree with this, on the grounds that a "typical load" of old 
cobblers are frequently spouted on this list.  Practicality beats purity 
any day of the week.  But no, this '=' is misused, it should have been 
':='.  Who really cares, if you don't like the language, pick another 
one, there's thousands of them to choose from.  Ah, another chance for 
me to plug the virtues of CORAL 66 and CORAL 250.  Capability violation 
anybody?

-- 
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence

[toc] | [prev] | [next] | [standalone]

#90004

On Tue, May 5, 2015 at 3:23 PM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
> On Tue, May 5, 2015 at 3:00 PM, Dave Angel <davea@davea.name> wrote:
>> def loop(func, funcname, arg):
>>     start = time.time()
>>     for i in range(repeats):
>>         func(arg, True)
>>     print("{0}({1}) took {2:7.4}".format(funcname, arg, time.time()-start))
>>
>>     start = time.time()
>>     for i in range(repeats):
>>         func(arg)
>>     print("{0}({1}) took {2:7.4}".format(funcname, arg, time.time()-start))
>
> Note that you're explicitly passing True in one case but leaving the
> default in the other. I don't know whether that might be responsible
> for the difference you're seeing.

I don't think that's the cause, but I do think that it has something
to do with the way the timing is being run. When I run your loop
function, I do observe the difference. If I reverse the order so that
the False case is tested first, I observe the opposite. That is, the
slower case is consistently the one that is timed *first* in the loop
function, regardless of which case that is.

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.python

csiph-web