Re: Python is not bad ;-)

2015-05-02 Thread Marko Rauhamaa
Cecil Westerhof ce...@decebal.nl:
 I find factorial a lot cleaner code as factorial_iterative, so here
 tail recursion would be beneficial.

I would just call math.factorial() and be done with it.

Note: Scheme is my favorite language and I use tail recursion all the
time. I also think eliminating tail recursion is such a low-hanging
fruit that even CPython should just pick it. However, I wouldn't use the
fibonacci sequence to justify anything at all about a programming
language.

It's not about performance (that's rarely a very useful argument when it
comes to Python). It's only that every now and then a very natural tail
recursion crops up and it's just silly to have to refactor perfectly
good code because of a stack overflow.


Marko
-- 
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-05-02 Thread Dave Angel

On 05/02/2015 05:58 AM, Marko Rauhamaa wrote:

Chris Angelico ros...@gmail.com:


Guido is against anything that disrupts tracebacks, and optimizing
tail recursion while maintaining traceback integrity is rather harder.


Tail recursion could be suppressed during debugging. Optimized code can
play all kinds of non-obvious tricks with the execution frame.


In the situations where it really is simple, you can always make the
change in your own code anyway. Often, the process of converting
recursion into tail recursion warps the code to the point where it's
abusing recursion to implement iteration anyway, so just make it
iterative.


While you shouldn't actively replace Python iteration with recursion, I
strongly disagree that naturally occurring tail recursion is abuse or
should be avoided in any manner.



When you strongly disagree, make sure you're disagreeing with what Chris 
actually said.  The key phrase in his message was

converting recursion into tail recursion

NOT  converting iteration into recursion
and NOT naturally occurring tail recursion


--
DaveA
--
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-05-02 Thread Gregory Ewing

Steven D'Aprano wrote:


People coming from functional languages like Lisp and Haskell often say
that, but how many recursive algorithms naturally take a tail-call form?
Not that many.


And the ones that do tend to be the ones that are
better expressed iteratively in Python. So Python
doesn't really need tail call optimisation.

Also, Guido has said that he doesn't like it,
because of the detrimental effect it has on stack
tracebacks.

--
Greg
--
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-05-02 Thread Chris Angelico
On Sat, May 2, 2015 at 8:22 PM, Dave Angel da...@davea.name wrote:
 On 05/02/2015 05:58 AM, Marko Rauhamaa wrote:

 Chris Angelico ros...@gmail.com:

 Guido is against anything that disrupts tracebacks, and optimizing
 tail recursion while maintaining traceback integrity is rather harder.


 Tail recursion could be suppressed during debugging. Optimized code can
 play all kinds of non-obvious tricks with the execution frame.

 In the situations where it really is simple, you can always make the
 change in your own code anyway. Often, the process of converting
 recursion into tail recursion warps the code to the point where it's
 abusing recursion to implement iteration anyway, so just make it
 iterative.


 While you shouldn't actively replace Python iteration with recursion, I
 strongly disagree that naturally occurring tail recursion is abuse or
 should be avoided in any manner.


 When you strongly disagree, make sure you're disagreeing with what Chris
 actually said.  The key phrase in his message was
 converting recursion into tail recursion

 NOT  converting iteration into recursion
 and NOT naturally occurring tail recursion

Indeed. I'll clarify my statement.

When a function needs to do further actions after the tail call, the
usual solution is to carry the information through parameters.

def stupid_sum_iter(x):
Calculate sum(range(x+1))
tot = 0
while x:
tot += x
x -= 1
return tot

def stupid_sum_recur(x):
return x and x + stupid_sum_recur(x - 1)

def stupid_sum_tail_recur(x, tot=0):
if not x: return tot
return stupid_sum_tail_recur(x - 1, tot + x)

Converting the recursive form into optimizable tail recursion requires
an accumulator parameter, which means it's virtually the same as the
iterative version. Naturally-occurring tail recursion does exist, but
it's far from all cases of recursion.

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-05-02 Thread Dave Angel

On 05/02/2015 05:33 AM, Cecil Westerhof wrote:

Please check your email settings.  Your messages that you type seem to 
be indented properly, but those that are quoting earlier messages (even 
your own) are not.  See below.  I suspect there's some problem with how 
your email program processes html messages.



Op Saturday 2 May 2015 10:26 CEST schreef Cecil Westerhof:


That is mostly because the tail recursion version starts multiplying
at the high end. I wrote a second version:
def factorial_tail_recursion2(x):
y = 1
z = 1
while True:
if x == z:
return y
y *= z
z += 1

This has almost the performance of the iterative version: 34 and 121
seconds.

So I made a new recursive version:
def factorial_recursive(x, y = 1, z = 1):
return y if x == z else factorial_recursive(x, x * y, z + 1)


Stupid me 'x == z' should be 'z  x'



I can't see how that is worth doing. The recursive version is already a 
distortion of the definition of factorial that I learned.  And to force 
it to be recursive and also contort it so it does the operations in the 
same order as the iterative version, just to gain performance?


If you want performance on factorial, write it iteratively, in as 
straightforward a way as possible.  Or just call the library function.


Recursion is a very useful tool in a developer's toolbox.  But the only 
reason I would use it for factorial is to provide a simple demonstration 
to introduce the concept to a beginner.



--
DaveA
--
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-05-02 Thread Cecil Westerhof
Op Saturday 2 May 2015 11:10 CEST schreef Marko Rauhamaa:

 Cecil Westerhof ce...@decebal.nl:
 I find factorial a lot cleaner code as factorial_iterative, so here
 tail recursion would be beneficial.

 I would just call math.factorial() and be done with it.

You missed the point. I did not need a factorial function, I wanted to
show that tail optimisation could be beneficial.

-- 
Cecil Westerhof
Senior Software Engineer
LinkedIn: http://www.linkedin.com/in/cecilwesterhof
-- 
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-05-02 Thread Chris Angelico
On Sat, May 2, 2015 at 9:07 PM, Christian Gollwitzer aurio...@gmx.de wrote:
 I need to add, I grew up with imperative programming, and as such got
 recursion as the solution to problems that are too complex for iteration,
 i.e. tree traversal and such, and exactly these are never tail-recursive.

Tree traversal can be forking-recursive:

def walk(func):
if self.left and self.left.walk(func): return 1
if func(self.payload): return 1
if self.right: return self.right.walk(func)

The left walk is non-tail-recursive, but the right walk is. This
particular style looks rather less clean with iteration:

def walk(func):
while True:
if self.left and self.left.walk(func): return 1
if func(self.payload): return 1
if not self.right: break
self = self.right

I'd call this an example of fairly natural tail recursion.

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-05-02 Thread Cecil Westerhof
Op Friday 1 May 2015 09:03 CEST schreef Steven D'Aprano:

 On Thu, 30 Apr 2015 09:30 pm, Cecil Westerhof wrote:

 Tail recursion would nice to have also.

 People coming from functional languages like Lisp and Haskell often
 say that, but how many recursive algorithms naturally take a
 tail-call form? Not that many.

One example:
def factorial(x, y = 1):
return y if x == 1 else factorial(x - 1, x * y)

def factorial_iterative(x):
result = 1
for i in range(2, x + 1):
result *= i
return result

Executing factorial(985) 100.000 times takes 54 seconds.
While executing factorial_iterative(985) takes 34 seconds.
Also you can not call factorial with a value that is much bigger
because of recursion depth. You can call factorial_iterative with
1.000.000.

I made also a version that simulates tail recursion:
def factorial_tail_recursion(x):
y = 1
while True:
if x == 1:
return y
y *= x
x -= 1

This is that a lot less efficient as the iterative version. It takes 43
seconds. But it is a lot better as the normal recursive version: about
25%. The iterative version is about 25% more efficient as the tail
recursion version.

With larger values it decreases. Calculating onetime for 5.000.000
takes 117 and 131 seconds. Just 10% faster.

That is mostly because the tail recursion version starts multiplying
at the high end. I wrote a second version:
def factorial_tail_recursion2(x):
y = 1
z = 1
while True:
if x == z:
return y
y *= z
z += 1

This has almost the performance of the iterative version: 34 and 121
seconds.

So I made a new recursive version:
def factorial_recursive(x, y = 1, z = 1):
return y if x == z else factorial_recursive(x, x * y, z + 1)

But this take almost the same tame as the other. Probably the
recursive calls are more important as the multiplications.


I find factorial a lot cleaner code as factorial_iterative, so here
tail recursion would be beneficial.

-- 
Cecil Westerhof
Senior Software Engineer
LinkedIn: http://www.linkedin.com/in/cecilwesterhof
-- 
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-05-02 Thread Marko Rauhamaa
Chris Angelico ros...@gmail.com:

 Guido is against anything that disrupts tracebacks, and optimizing
 tail recursion while maintaining traceback integrity is rather harder.

Tail recursion could be suppressed during debugging. Optimized code can
play all kinds of non-obvious tricks with the execution frame.

 In the situations where it really is simple, you can always make the
 change in your own code anyway. Often, the process of converting
 recursion into tail recursion warps the code to the point where it's
 abusing recursion to implement iteration anyway, so just make it
 iterative.

While you shouldn't actively replace Python iteration with recursion, I
strongly disagree that naturally occurring tail recursion is abuse or
should be avoided in any manner.


Marko
-- 
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-05-02 Thread Chris Angelico
On Sat, May 2, 2015 at 7:10 PM, Marko Rauhamaa ma...@pacujo.net wrote:
 Note: Scheme is my favorite language and I use tail recursion all the
 time. I also think eliminating tail recursion is such a low-hanging
 fruit that even CPython should just pick it. However, I wouldn't use the
 fibonacci sequence to justify anything at all about a programming
 language.

Actually, it isn't such low-hanging fruit. As has been mentioned in
this thread already, Guido is against anything that disrupts
tracebacks, and optimizing tail recursion while maintaining traceback
integrity is rather harder.

In the situations where it really is simple, you can always make the
change in your own code anyway. Often, the process of converting
recursion into tail recursion warps the code to the point where it's
abusing recursion to implement iteration anyway, so just make it
iterative.

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-05-02 Thread Cecil Westerhof
Op Saturday 2 May 2015 10:26 CEST schreef Cecil Westerhof:

 Op Friday 1 May 2015 09:03 CEST schreef Steven D'Aprano:

 On Thu, 30 Apr 2015 09:30 pm, Cecil Westerhof wrote:

 Tail recursion would nice to have also.

 People coming from functional languages like Lisp and Haskell often
 say that, but how many recursive algorithms naturally take a
 tail-call form? Not that many.

 One example:
 def factorial(x, y = 1):
 return y if x == 1 else factorial(x - 1, x * y)

 def factorial_iterative(x):
 result = 1
 for i in range(2, x + 1):
 result *= i
 return result

 Executing factorial(985) 100.000 times takes 54 seconds.
 While executing factorial_iterative(985) takes 34 seconds.
 Also you can not call factorial with a value that is much bigger
 because of recursion depth. You can call factorial_iterative with
 1.000.000.

 I made also a version that simulates tail recursion:
 def factorial_tail_recursion(x):
 y = 1
 while True:
 if x == 1:
 return y
 y *= x
 x -= 1

 This is that a lot less efficient as the iterative version. It takes
 43 seconds. But it is a lot better as the normal recursive version:
 about 25%. The iterative version is about 25% more efficient as the
 tail recursion version.

 With larger values it decreases. Calculating onetime for 5.000.000
 takes 117 and 131 seconds. Just 10% faster.

 That is mostly because the tail recursion version starts multiplying
 at the high end. I wrote a second version:
 def factorial_tail_recursion2(x):
 y = 1
 z = 1
 while True:
 if x == z:
 return y
 y *= z
 z += 1

 This has almost the performance of the iterative version: 34 and 121
 seconds.

 So I made a new recursive version:
 def factorial_recursive(x, y = 1, z = 1):
 return y if x == z else factorial_recursive(x, x * y, z + 1)

Stupid me 'x == z' should be 'z  x'

-- 
Cecil Westerhof
Senior Software Engineer
LinkedIn: http://www.linkedin.com/in/cecilwesterhof
-- 
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-05-02 Thread Christian Gollwitzer

Am 02.05.15 um 11:58 schrieb Marko Rauhamaa:

Chris Angelico ros...@gmail.com:


Guido is against anything that disrupts tracebacks, and optimizing
tail recursion while maintaining traceback integrity is rather harder.


Tail recursion could be suppressed during debugging. Optimized code can
play all kinds of non-obvious tricks with the execution frame.


In the situations where it really is simple, you can always make the
change in your own code anyway. Often, the process of converting
recursion into tail recursion warps the code to the point where it's
abusing recursion to implement iteration anyway, so just make it
iterative.


While you shouldn't actively replace Python iteration with recursion, I
strongly disagree that naturally occurring tail recursion is abuse or
should be avoided in any manner.


Could you show me an example of naturally occuring tail recursion? I 
can't think of any. Or is it maybe one involving mutual recursion?


I need to add, I grew up with imperative programming, and as such got 
recursion as the solution to problems that are too complex for 
iteration, i.e. tree traversal and such, and exactly these are never 
tail-recursive.



Christian
--
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-05-02 Thread Marko Rauhamaa
Christian Gollwitzer aurio...@gmx.de:

 That's why I still think it is a microoptimization, which helps only
 in some specific cases.

It isn't done for performance. It's done to avoid a stack overflow
exception.


Marko
-- 
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-05-02 Thread Ian Kelly
On Sat, May 2, 2015 at 4:35 AM, Dave Angel da...@davea.name wrote:
 I can't see how that is worth doing. The recursive version is already a
 distortion of the definition of factorial that I learned.  And to force it
 to be recursive and also contort it so it does the operations in the same
 order as the iterative version, just to gain performance?

 If you want performance on factorial, write it iteratively, in as
 straightforward a way as possible.  Or just call the library function.

Or if you really want to write it functionally:

from functools import reduce
from operator import mul

def product(iterable):
return reduce(mul, iterable, 1)

def factorial(n):
return product(range(1, n+1))

For Python 2, delete the first import and replace range with xrange.
-- 
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-05-02 Thread Ian Kelly
On Sat, May 2, 2015 at 5:42 AM, Marko Rauhamaa ma...@pacujo.net wrote:
 Christian Gollwitzer aurio...@gmx.de:

 That's why I still think it is a microoptimization, which helps only
 in some specific cases.

 It isn't done for performance. It's done to avoid a stack overflow
 exception.

If your tree is balanced, then the number of items you would need to
have to get a stack overflow exception would be approximately 2 **
1000, which you can't possibly hope to fit into memory.

If your tree is unbalanced and you're getting a stack overflow
exception, then maybe you should think about balancing it.
-- 
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-05-02 Thread Cecil Westerhof
Op Saturday 2 May 2015 12:35 CEST schreef Dave Angel:

 On 05/02/2015 05:33 AM, Cecil Westerhof wrote:

 Please check your email settings. Your messages that you type seem
 to be indented properly, but those that are quoting earlier messages
 (even your own) are not. See below. I suspect there's some problem
 with how your email program processes html messages.

 Op Saturday 2 May 2015 10:26 CEST schreef Cecil Westerhof:

 That is mostly because the tail recursion version starts
 multiplying at the high end. I wrote a second version: def
 factorial_tail_recursion2(x): y = 1 z = 1 while True: if x == z:
 return y y *= z z += 1

 This has almost the performance of the iterative version: 34 and
 121 seconds.

 So I made a new recursive version:
 def factorial_recursive(x, y = 1, z = 1):
 return y if x == z else factorial_recursive(x, x * y, z + 1)

 Stupid me 'x == z' should be 'z  x'


 I can't see how that is worth doing. The recursive version is
 already a distortion of the definition of factorial that I learned.
 And to force it to be recursive and also contort it so it does the
 operations in the same order as the iterative version, just to gain
 performance?

 If you want performance on factorial, write it iteratively, in as
 straightforward a way as possible. Or just call the library
 function.

 Recursion is a very useful tool in a developer's toolbox. But the
 only reason I would use it for factorial is to provide a simple
 demonstration to introduce the concept to a beginner.

And that was what I was doing here: showing that tail recursion can
have benefits.

By the way I have seen factorial mostly implemented recursive.

Also I am now testing with very large values. The version where I use
both tail recursion versions are faster as the iterative version.
Calculating 500.000:
iterative:  137 seconds
tail recursion optimised:   120 seconds
tail recursion simple:  130 seconds

You have to be careful that you do not fall into the trap that you are
sure your way is the best way. I have had the same on the Scala list.
I told there that for a certain function it was better to use an
iterative version as a tail recursive function. They did not want to
believe it at first.

-- 
Cecil Westerhof
Senior Software Engineer
LinkedIn: http://www.linkedin.com/in/cecilwesterhof
-- 
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-05-02 Thread Christian Gollwitzer

Am 02.05.15 um 13:21 schrieb Chris Angelico:

On Sat, May 2, 2015 at 9:07 PM, Christian Gollwitzer aurio...@gmx.de wrote:

I need to add, I grew up with imperative programming, and as such got
recursion as the solution to problems that are too complex for iteration,
i.e. tree traversal and such, and exactly these are never tail-recursive.


Tree traversal can be forking-recursive:

def walk(func):
 if self.left and self.left.walk(func): return 1
 if func(self.payload): return 1
 if self.right: return self.right.walk(func)

The left walk is non-tail-recursive, but the right walk is. This
particular style looks rather less clean with iteration:


Accepted. In case your tree is heavily imbalanced, i.e. it is a list 
pretending to be a tree, the tail-recursion can cut down the memory 
usage significantly. It does not help, though, in the general case of a 
balanced tree or if the tree leans to the left side. That's why I still 
think it is a microoptimization, which helps only in some specific cases.


Christian
--
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-05-02 Thread Chris Angelico
On Sun, May 3, 2015 at 1:45 AM, Ian Kelly ian.g.ke...@gmail.com wrote:
 On Sat, May 2, 2015 at 5:42 AM, Marko Rauhamaa ma...@pacujo.net wrote:
 Christian Gollwitzer aurio...@gmx.de:

 That's why I still think it is a microoptimization, which helps only
 in some specific cases.

 It isn't done for performance. It's done to avoid a stack overflow
 exception.

 If your tree is balanced, then the number of items you would need to
 have to get a stack overflow exception would be approximately 2 **
 1000, which you can't possibly hope to fit into memory.

 If your tree is unbalanced and you're getting a stack overflow
 exception, then maybe you should think about balancing it.

That's assuming it's a search tree, where you *can* just think about
balancing it. What if it's a parse tree? Let's say you're walking the
AST of a Python module, looking for all functions that contain 'yield'
or 'yield from' (ie generator functions). To do that, you need to walk
the entire depth of the tree, no matter how far that goes. I'm not
sure how complex a piece of code would have to be to hit 1000, but it
wouldn't be hard to have each level of tree cost you two or three
stack entries, so that could come down to just a few hundred.

However, while that _is_ more likely to produce an unbalanced tree,
it's also that much less capable of being converted into tail
recursion.

ChrisA
-- 
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-05-02 Thread Joonas Liik
I agree, stack overflow is literally the main issue that ive run in to
(tree traversal)
I've yet to refactor recursion to iterative for speed, but i have done so
to avoid hitting the stack size limit.

Tree traversal and similar problems in particular lend themselves well to
recursion and are not quite as trivial to do in an iterative fashion.

I've also found myself constructing an ad-hoc trampoline at least once just
to sneak past the stack limit.
(probably very evil but it worked and it wasn't nearly as ugly as it sounds
like so ill live with it..)


On 2 May 2015 at 14:42, Marko Rauhamaa ma...@pacujo.net wrote:

 Christian Gollwitzer aurio...@gmx.de:

  That's why I still think it is a microoptimization, which helps only
  in some specific cases.

 It isn't done for performance. It's done to avoid a stack overflow
 exception.


 Marko
 --
 https://mail.python.org/mailman/listinfo/python-list

-- 
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-05-02 Thread Ian Kelly
On Sat, May 2, 2015 at 9:53 AM, Joonas Liik liik.joo...@gmail.com wrote:

Top-posting is heavily frowned at on this list, so please don't do it.

 Balancing of trees is kind of irrelevant when tree means search space
 no?

I think it's relatively rare that DFS is truly the best algorithm for
such a search. For one thing, search space often means graph, not
tree. And for any other type of search, you'll want/need to
implement it iteratively rather than recursively anyway.

 And you definitely dont need to keep the entire tree in memory at the same
 time.

You could harness every single storage device on the planet and you
would still not have nearly enough capacity to fill a balanced search
tree to a depth of 1000.

 Also should not-running-out-of-call-stack really be the main reason to
 balance trees?
 That sounds like an optimisation to me ..

It is. My point was that if your unbalanced search tree is getting to
a depth of 1000, then it's probably long past time for you to start
thinking about optimizing it *anyway*.
-- 
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-05-02 Thread Joonas Liik
Balancing of trees is kind of irrelevant when tree means search space
no?
And you definitely dont need to keep the entire tree in memory at the same
time.

By cropping unsuitable branches early (and not keeping the entire tree in
memory)
it is quite easy to have more than 1000 of call stack and still have
reasonable
preformance. (some/many nodes have 0 or 1 children)

Also should not-running-out-of-call-stack really be the main reason to
balance trees?
That sounds like an optimisation to me ..

On 2 May 2015 at 18:45, Ian Kelly ian.g.ke...@gmail.com wrote:

 On Sat, May 2, 2015 at 5:42 AM, Marko Rauhamaa ma...@pacujo.net wrote:
  Christian Gollwitzer aurio...@gmx.de:
 
  That's why I still think it is a microoptimization, which helps only
  in some specific cases.
 
  It isn't done for performance. It's done to avoid a stack overflow
  exception.

 If your tree is balanced, then the number of items you would need to
 have to get a stack overflow exception would be approximately 2 **
 1000, which you can't possibly hope to fit into memory.

 If your tree is unbalanced and you're getting a stack overflow
 exception, then maybe you should think about balancing it.
 --
 https://mail.python.org/mailman/listinfo/python-list

-- 
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-05-02 Thread Ian Kelly
On Sat, May 2, 2015 at 9:55 AM, Chris Angelico ros...@gmail.com wrote:
 On Sun, May 3, 2015 at 1:45 AM, Ian Kelly ian.g.ke...@gmail.com wrote:
 On Sat, May 2, 2015 at 5:42 AM, Marko Rauhamaa ma...@pacujo.net wrote:
 Christian Gollwitzer aurio...@gmx.de:

 That's why I still think it is a microoptimization, which helps only
 in some specific cases.

 It isn't done for performance. It's done to avoid a stack overflow
 exception.

 If your tree is balanced, then the number of items you would need to
 have to get a stack overflow exception would be approximately 2 **
 1000, which you can't possibly hope to fit into memory.

 If your tree is unbalanced and you're getting a stack overflow
 exception, then maybe you should think about balancing it.

 That's assuming it's a search tree, where you *can* just think about
 balancing it. What if it's a parse tree? Let's say you're walking the
 AST of a Python module, looking for all functions that contain 'yield'
 or 'yield from' (ie generator functions). To do that, you need to walk
 the entire depth of the tree, no matter how far that goes. I'm not
 sure how complex a piece of code would have to be to hit 1000, but it
 wouldn't be hard to have each level of tree cost you two or three
 stack entries, so that could come down to just a few hundred.

Or you just iterate over the ast.walk generator, which uses a deque
rather than recursion.
-- 
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-05-02 Thread Mark Lawrence

On 02/05/2015 14:50, Joonas Liik wrote:

[top posting fixed]



On 2 May 2015 at 14:42, Marko Rauhamaa ma...@pacujo.net wrote:


Christian Gollwitzer aurio...@gmx.de:


That's why I still think it is a microoptimization, which helps only
in some specific cases.


It isn't done for performance. It's done to avoid a stack overflow
exception.


Marko
--
https://mail.python.org/mailman/listinfo/python-list


I agree, stack overflow is literally the main issue that ive run in to
(tree traversal)
I've yet to refactor recursion to iterative for speed, but i have done so
to avoid hitting the stack size limit.

Tree traversal and similar problems in particular lend themselves well to
recursion and are not quite as trivial to do in an iterative fashion.

I've also found myself constructing an ad-hoc trampoline at least once just
to sneak past the stack limit.
(probably very evil but it worked and it wasn't nearly as ugly as it sounds
like so ill live with it..)




Please do not top post on this list.  Some of the threads get very long 
and are difficult if not impossible to follow when replies are top 
posted.  Interspersing your replies is the preferred method here, 
failing that simply reply at the bottom, thanks.


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

Mark Lawrence

--
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-05-01 Thread Steven D'Aprano
On Thu, 30 Apr 2015 08:16 pm, Marko Rauhamaa wrote:

 Still, Python has features that defy effective optimization. Most
 notably, Python's dot notation translates into a hash table lookup -- or
 worse.


Effective optimization may be difficult, but it isn't impossible. PyPy has a
very effective Just In Time optimizer.

http://speed.pypy.org/

PyPy currently ranges from approximately 1.25 times to 50 times faster than
CPython, with an average of over 7 times faster.

And now PyPy also has a version that runs without the GIL:

http://morepypy.blogspot.com.au/2015/03/pypy-stm-251-released.html


-- 
Steven

-- 
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-05-01 Thread Steven D'Aprano
On Thu, 30 Apr 2015 09:30 pm, Cecil Westerhof wrote:

 Tail recursion would nice to have also.

People coming from functional languages like Lisp and Haskell often say
that, but how many recursive algorithms naturally take a tail-call form?
Not that many.

I suppose that it would be nice if Python let you optionally use tail-call
optimization, but that might be tricky in practice.



-- 
Steven

-- 
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-05-01 Thread Christian Gollwitzer

Am 01.05.15 um 09:03 schrieb Steven D'Aprano:

On Thu, 30 Apr 2015 09:30 pm, Cecil Westerhof wrote:


Tail recursion would nice to have also.


People coming from functional languages like Lisp and Haskell often say
that, but how many recursive algorithms naturally take a tail-call form?
Not that many.


That is because tailcall optimization is used in functional languages 
mainly as a replacement for loops. IOW, in non-functional languages you 
can simply use an infinite loop to do the same (in most cases).



I suppose that it would be nice if Python let you optionally use tail-call
optimization, but that might be tricky in practice.



In Tcl 8.6 there is an explicit tailcall something command which calls 
something without creating a new stack frame, i.e. it returns to the 
caller after something returns. Useful sometimes, but more a 
micro-optimization than a vital feature.


Christian
--
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-05-01 Thread Cecil Westerhof
Op Friday 1 May 2015 09:03 CEST schreef Steven D'Aprano:

 On Thu, 30 Apr 2015 09:30 pm, Cecil Westerhof wrote:

 Tail recursion would nice to have also.

 People coming from functional languages like Lisp and Haskell often
 say that, but how many recursive algorithms naturally take a
 tail-call form? Not that many.

When I was playing with Scala there where a few cases where tail
recursion made a significant performance boost.

Is some time ago, so I do not remember which.


 I suppose that it would be nice if Python let you optionally use
 tail-call optimization, but that might be tricky in practice.

That is the difference between Scala and Clojure. Scala does it
silently, while by Clojure you have to say you want it. When a chance
breaks tail recursion Scala just compiles, but your code becomes
slower, Clojure does not compile. I prefer the Clojure variant.

-- 
Cecil Westerhof
Senior Software Engineer
LinkedIn: http://www.linkedin.com/in/cecilwesterhof
-- 
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-04-30 Thread Ben Finney
Cecil Westerhof ce...@decebal.nl writes:

 I am coding with Python again.

Great to know!

 I like it that the code is concise and clear. But also that the
 performance is not bad.

The former is a property of Python, which is a programming language. I
agree with your assessment :-)

The latter is not a property of Python; a programming language doesn't
have runtime performance. Rather, runtime performance is a property of
some specific *implementation* — that is, the runtime Python machine.

There are numerous Python runtimes, and they have different performance
characteristics on different hardware and operating systems.

URL:https://wiki.python.org/moin/PythonImplementations

You might be talking about performance on CPython. But you might not! I
don't know.

Have you looked at PyPy – Python implemented in Python – and compared
its performance?

-- 
 \ “I went camping and borrowed a circus tent by mistake. I didn't |
  `\  notice until I got it set up. People complained because they |
_o__)   couldn't see the lake.” —Steven Wright |
Ben Finney

-- 
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-04-30 Thread Chris Angelico
On Thu, Apr 30, 2015 at 8:16 PM, Marko Rauhamaa ma...@pacujo.net wrote:
 Ben Finney ben+pyt...@benfinney.id.au:

 The latter is not a property of Python; a programming language doesn't
 have runtime performance. Rather, runtime performance is a property of
 some specific *implementation* — that is, the runtime Python machine.

 There are numerous Python runtimes, and they have different
 performance characteristics on different hardware and operating
 systems.

 Still, Python has features that defy effective optimization. Most
 notably, Python's dot notation translates into a hash table lookup -- or
 worse.

 I currently carry three clubs in my professional golf bag: bash, python
 and C. Java is a great programming language, but Python and C manage
 everything Java would be useful for.

(I carry a lot more clubs in my bag. The Ace of Clubs for me is Pike,
but Python comes in a close second; both are decently high
performance, quick to write code in, and come with extensive standard
libraries. Any bash script that grows to more than a page or so of
code usually finds itself rewritten in Python or Pike; C is mainly for
writing high level programming languages in.)

Most of the programs that I write spend their time on work far more
serious than looking up names in dictionaries. For instance, one of my
programs [1] shells out to avconv and sox to do a bunch of big file
conversions, doing its best to fill up my hard disk (eighty-odd gig of
intermediate files is a good start), and ultimately producing one
hefty video file. Another that I contribute heavily to [2] uses lame
to manipulate a bunch of .MP3 files and, ultimately, stream them down
an internet connection. A third [3] sleeps its entire life away,
either making network requests and waiting for the responses, or
outright sleep()ing until it needs to go do something again. If the
cost of run-time lookups of dotted names were to increase by an order
of magnitude, not one of them would materially change in performance.
Sure, you can do microbenchmarks that show that Python takes X times
longer to parse x.y.z than Java does, but if that's seriously
impacting your real-world code, what are you doing?

About the only time when Python performance makes a real difference is
on startup. Mercurial, for instance, has to be invoked, initialized,
and shut down, for every command. (That's why git tends to outdo it in
a lot of ways, thanks to being written mainly in C and Perl.) So yes,
there are efforts every now and then to cut the startup time, where
however-many modules all have to get imported and set up. In the most
micro of microbenchmarks, here's what it takes to do nothing in
several languages:

rosuav@sikorsky:~$ cat repeat.sh
for i in {1..100}; do $@; done

rosuav@sikorsky:~$ time bash repeat.sh pike -e ';'

real 0m8.504s
user 0m7.928s
sys 0m0.436s
rosuav@sikorsky:~$ time bash repeat.sh python3 -c pass

real 0m3.094s
user 0m2.400s
sys 0m0.424s
rosuav@sikorsky:~$ time bash repeat.sh python2 -c pass

real 0m1.843s
user 0m1.136s
sys 0m0.488s

rosuav@sikorsky:~$ echo 'int main() {return 0;}' |gcc -x c -
rosuav@sikorsky:~$ time bash repeat.sh ./a.out

real 0m0.076s
user 0m0.004s
sys 0m0.012s

So, yeah. Pike's a poor choice and C's superb if you want to start up
and shut down real fast. Great. But as soon as those figures get
dwarfed by real work, nothing else matters. It's a rare situation
where you really need to start a program in less than 0.085 seconds.

ChrisA

[1] https://github.com/Rosuav/FrozenOST
[2] https://github.com/MikeiLL/appension
[3] https://github.com/Rosuav/LetMeKnow
-- 
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-04-30 Thread Marko Rauhamaa
Ben Finney ben+pyt...@benfinney.id.au:

 The latter is not a property of Python; a programming language doesn't
 have runtime performance. Rather, runtime performance is a property of
 some specific *implementation* — that is, the runtime Python machine.

 There are numerous Python runtimes, and they have different
 performance characteristics on different hardware and operating
 systems.

Still, Python has features that defy effective optimization. Most
notably, Python's dot notation translates into a hash table lookup -- or
worse.

I currently carry three clubs in my professional golf bag: bash, python
and C. Java is a great programming language, but Python and C manage
everything Java would be useful for.


Marko
-- 
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-04-30 Thread Cecil Westerhof
Op Thursday 30 Apr 2015 12:16 CEST schreef Marko Rauhamaa:

 Ben Finney ben+pyt...@benfinney.id.au:

 The latter is not a property of Python; a programming language
 doesn't have runtime performance. Rather, runtime performance is a
 property of some specific *implementation* — that is, the runtime
 Python machine.

 There are numerous Python runtimes, and they have different
 performance characteristics on different hardware and operating
 systems.

 Still, Python has features that defy effective optimization. Most
 notably, Python's dot notation translates into a hash table lookup
 -- or worse.

Tail recursion would nice to have also.

 I currently carry three clubs in my professional golf bag: bash,

I published a Bash library:
https://github.com/CecilWesterhof/BashLibrary

Maybe there is something useful in it for you. And if you need
something: let me know. No guarantees, but I could write it for you.

-- 
Cecil Westerhof
Senior Software Engineer
LinkedIn: http://www.linkedin.com/in/cecilwesterhof
-- 
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-04-30 Thread Cecil Westerhof
Op Thursday 30 Apr 2015 11:10 CEST schreef Ben Finney:

 I like it that the code is concise and clear. But also that the
 performance is not bad.

 The former is a property of Python, which is a programming language.
 I agree with your assessment :-)

 The latter is not a property of Python; a programming language
 doesn't have runtime performance. Rather, runtime performance is a
 property of some specific *implementation* — that is, the runtime
 Python machine.

 There are numerous Python runtimes, and they have different
 performance characteristics on different hardware and operating
 systems.

 URL:https://wiki.python.org/moin/PythonImplementations

 You might be talking about performance on CPython. But you might
 not! I don't know.

I understood when you did not explicitly mention it, it normally is
CPython. And in my case it is.

I should try it also in Jython, because Clojure runs in de JVM.


 Have you looked at PyPy – Python implemented in Python – and
 compared its performance?

Not yet. Busy hacking away. :-D

-- 
Cecil Westerhof
Senior Software Engineer
LinkedIn: http://www.linkedin.com/in/cecilwesterhof
-- 
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-04-30 Thread Cecil Westerhof
Op Thursday 30 Apr 2015 16:03 CEST schreef Michael Torrie:

 On 04/30/2015 01:07 AM, Cecil Westerhof wrote:
 When I do that the computer is freezed a few times. That is a
 little less nice. Does not happen with Clojure when it gets an out
 of memory.

 A system freeze is probably due to thrashing by your operating
 system as a process (in this case Python) uses more and more memory,
 causing massive swapping. Clojure's heap, being a JVM-based
 language, is based on JVM settings, so it may be maxing out at just
 a couple of GB. Whereas Python will happily max out your swap if
 your program demands the memory.

I just posted a message about that. This gets the problem also:
l = range(int(1E9))

The problem is that after this other processes are swapped out and
have a bad performance. There is nothing that can be done about it?

So there is a positive point for working with the JVM. :-D

-- 
Cecil Westerhof
Senior Software Engineer
LinkedIn: http://www.linkedin.com/in/cecilwesterhof
-- 
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-04-30 Thread Christian Gollwitzer

Am 30.04.15 um 18:11 schrieb Cecil Westerhof:

Op Thursday 30 Apr 2015 16:03 CEST schreef Michael Torrie:


On 04/30/2015 01:07 AM, Cecil Westerhof wrote:

When I do that the computer is freezed a few times. That is a
little less nice. Does not happen with Clojure when it gets an out
of memory.


A system freeze is probably due to thrashing by your operating
system as a process (in this case Python) uses more and more memory,
causing massive swapping. Clojure's heap, being a JVM-based
language, is based on JVM settings, so it may be maxing out at just
a couple of GB. Whereas Python will happily max out your swap if
your program demands the memory.


I just posted a message about that. This gets the problem also:
 l = range(int(1E9))

The problem is that after this other processes are swapped out and
have a bad performance. There is nothing that can be done about it?

So there is a positive point for working with the JVM. :-D



No, you understood this the wrong way. The JVM has a limit on the max 
memory size on startup, which you can give by the -Xmx option on the 
Oracle machine, so for instance


java -Xmx512M -jar myjar.jar

limits the memory that your program may consume to 512 megs, until the 
JVM kills it. The standard limit is usually fairly low and probably 
below your real memory, so the java program does not have the chance to 
max out your memory and make your computer swap.


CPython, au contraire, uses all memory it can get from the OS. The OS 
kills it if it uses too much. On Linux, you can set this limit yourself 
using ulimit. The analogue to the java call would therefore be something 
like


ulimit -m 512M
python mypython.py

If you set the ulimit to something smaller than your physical memory 
size, you also cause the program to be killed before it can use up all 
the memory and introduce swapping. For a fair comparison, you should set 
both limits to the same value and see how far you can get.


Christian
--
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-04-30 Thread Cecil Westerhof
Op Thursday 30 Apr 2015 19:59 CEST schreef Christian Gollwitzer:

 Am 30.04.15 um 18:11 schrieb Cecil Westerhof:
 Op Thursday 30 Apr 2015 16:03 CEST schreef Michael Torrie:

 On 04/30/2015 01:07 AM, Cecil Westerhof wrote:
 When I do that the computer is freezed a few times. That is a
 little less nice. Does not happen with Clojure when it gets an
 out of memory.

 A system freeze is probably due to thrashing by your operating
 system as a process (in this case Python) uses more and more
 memory, causing massive swapping. Clojure's heap, being a
 JVM-based language, is based on JVM settings, so it may be maxing
 out at just a couple of GB. Whereas Python will happily max out
 your swap if your program demands the memory.

 I just posted a message about that. This gets the problem also:
 l = range(int(1E9))

 The problem is that after this other processes are swapped out and
 have a bad performance. There is nothing that can be done about it?

 So there is a positive point for working with the JVM. :-D


 No, you understood this the wrong way. The JVM has a limit on the
 max memory size on startup, which you can give by the -Xmx option on
 the Oracle machine, so for instance

 java -Xmx512M -jar myjar.jar

 limits the memory that your program may consume to 512 megs, until
 the JVM kills it. The standard limit is usually fairly low and
 probably below your real memory, so the java program does not have
 the chance to max out your memory and make your computer swap.

Well, I did play a little with that. My experience is that this is to
high. For example by lowering it, a certain program did not swap
anymore. Sound counter intuitive, but not that strange if you know the
inner workings of the JVM.


 CPython, au contraire, uses all memory it can get from the OS. The
 OS kills it if it uses too much. On Linux, you can set this limit
 yourself using ulimit. The analogue to the java call would therefore
 be something like

 ulimit -m 512M
 python mypython.py

I use startup scripts for the different Java (or Scala, or Clojure)
programs to set the memory size. I should do that also for my (or
anothers) Python scripts.


 If you set the ulimit to something smaller than your physical memory
 size, you also cause the program to be killed before it can use up

Nope, the program gets a MemoryError and will not be killed. Much
better I think.


 should set both limits to the same value and see how far you can
 get.

You are right.

-- 
Cecil Westerhof
Senior Software Engineer
LinkedIn: http://www.linkedin.com/in/cecilwesterhof
-- 
https://mail.python.org/mailman/listinfo/python-list


Re: Python is not bad ;-)

2015-04-30 Thread Michael Torrie
On 04/30/2015 01:07 AM, Cecil Westerhof wrote:
 When I do that the computer is freezed a few times. That is a little
 less nice. Does not happen with Clojure when it gets an out of memory.

A system freeze is probably due to thrashing by your operating system as
a process (in this case Python) uses more and more memory, causing
massive swapping.  Clojure's heap, being a JVM-based language, is based
on JVM settings, so it may be maxing out at just a couple of GB.
Whereas Python will happily max out your swap if your program demands
the memory.

-- 
https://mail.python.org/mailman/listinfo/python-list


Re: Python 2.4.3 Documentation: Bad link

2006-04-02 Thread Tim Parkin
[EMAIL PROTECTED] wrote:
 Now, it works well... I really don't know why it before report 404 Not
 Found... I was tested it 5x... I'm sorry for unwanted false bug report.

Hi Bones, It really was a bug!! I'd seen it reported on the bug tracker
and made a quick fix which is why I hadn't closed the issue in the bug
tracker (it was you that reported it?).

Thanks

Tim

-- 
http://mail.python.org/mailman/listinfo/python-list


Re: Python 2.4.3 Documentation: Bad link

2006-04-01 Thread Terry Reedy

[EMAIL PROTECTED] wrote in message 
news:[EMAIL PROTECTED]
 Hi everybody,
 I found bug in link to download Python 2.4.3 documentation,
 http://docs.python.org/download.html. All links is to
 http://docs.python.org/ftp/python/doc/2.4.3/* . It does not works. It
 works only with http://python.org/ftp/python/doc/2.4.3/* .
 Bones

I tried a couple and they worked fine.  Bad 4/1 joke?

tjr



-- 
http://mail.python.org/mailman/listinfo/python-list


Re: Python 2.4.3 Documentation: Bad link

2006-04-01 Thread bones17
Now, it works well... I really don't know why it before report 404 Not
Found... I was tested it 5x... I'm sorry for unwanted false bug report.

-- 
http://mail.python.org/mailman/listinfo/python-list