Language Shootout
Ben
MegaHurts
set of benchmarks.
Now, if the rest of us can be thoughtful
as well in our USE of this information...
e.g., understanding: that "fast enough" is
enough; that speed and flexibility of
development is often more important than
whether a language has raw speed; that read-
ability and maintainability is often an im-
portant consideration; that the existance of
rich libraries and third-party functional
modules can be vastly more important than
running the Sieve of Eratosthenes 100 times
faster.
Finding a way, however subjective, to rate
THESE considerations would be an important
addition to any "language shootout," so
important as to be a necessity, I believe.
That said, I still enjoy reading benchmarks!
----- Original Message -----
From: Ben <b.e.n.@.r.e.h.a.m.e...c.o.m>
Newsgroups: comp.lang.python
Sent: Tuesday, July 03, 2001 3:42 PM
Subject: Language Shootout
|
| http://www.bagley.org/~doug/shootout/
Ben <b.e.n.@.r.e.h.a.m.e...c.o.m> wrote in message
news:ldi4ktoc90c8kbeqq...@4ax.com...
|
| http://www.bagley.org/~doug/shootout/
Magnus Lie Hetland
it seems :-|
--
Magnus Lie Hetland http://www.hetland.org
"Reality is that which, when you stop believing in
it, doesn't go away." -- Philip K. Dick
Alan Miller
>"Ben" <b.e.n.@.r.e.h.a.m.e...c.o.m> wrote in message
>news:ldi4ktoc90c8kbeqq...@4ax.com...
>>
>> http://www.bagley.org/~doug/shootout/
>it seems :-|
The creator of the page had it hosted on a home(?) box with a traffic
cap. He got Slashdotted, so he changed the dynamic DNS entries to point
back to Slashdot instead.
ajm
SoloCDM
>
> http://www.bagley.org/~doug/shootout/
I'm not bashing Python, I'm only commenting on what I saw. The tests,
from my previous experience, are legitimate; therefore, the tests
raised many unanswered questions.
Theses numbers produced at this URL site are very real to me. I
noticed a balanced and small memory and cpu usage for most of the
Python tests, but C/C++ out weighed most other languages. Would
anyone care to comment?
--
Note: When you reply to this message, please include the mailing
list/newsgroup address and my email address in To:.
*********************************************************************
Signed,
SoloCDM
Roman Suzi
>Ben stated the following:
>>
>> http://www.bagley.org/~doug/shootout/
>
>I'm not bashing Python, I'm only commenting on what I saw. The tests,
>from my previous experience, are legitimate; therefore, the tests
>raised many unanswered questions.
>
>Theses numbers produced at this URL site are very real to me. I
>noticed a balanced and small memory and cpu usage for most of the
>Python tests, but C/C++ out weighed most other languages. Would
>anyone care to comment?
Have you tried to tweak weights?
If you put nonzero into "number of lines" category, you will get
the picture where Python and some other languages are winners.
There are other analyses (Lutz Prechelt's, for example) which show that
overall program efficiency depends largely on programmer's abilities.
Poor C/C++ programmer could make programs much worse than average Python
programmer!
One more point about shootout. If I understood correctly, advanced
features are banned. You can't change
k = []
for i in list:
k.append(f(i)
into:
k = [f(i) for i in list]
Sincerely yours, Roman Suzi
--
_/ Russia _/ Karelia _/ Petrozavodsk _/ r...@onego.ru _/
_/ Monday, July 09, 2001 _/ Powered by Linux RedHat 6.2 _/
_/ "Useless Invention: Motorcycle seat-belts." _/
Paul Winkler
> One more point about shootout. If I understood correctly, advanced
> features are banned.
Not only that, but a number of the tests are explicitly testing how the
languages fare at doing a task "The Same Way". The site made a lot more sense to
me once I noticed that. For example,
http://www.bagley.org/~doug/shootout/bench/fibo/
doesn't just compute fibonacci numbers; the implementation must be *recursive*.
So this is really a test of how the languages fare at recursion. In python,
there's usually a more idiomatic way to solve a problem. In this case, if all
you really wanted was to compute fibonacci numbers, recursion is not the best
approach; performance degrades exponentially with the size of the series. Doing
it iteratively is much, much faster.
So basically what that benchmark tells me is: "Don't write recursively in Python
if performance is an issue".
--
................... paul winkler ....................
custom calendars & printing: http://www.calendargalaxy.com
A member of ARMS: http://www.reacharms.com
home page: http://www.slinkp.com
James Logajan
> So basically what that benchmark tells me is: "Don't write recursively in Python
> if performance is an issue".
Well yes, this is what benchmarks are useful for.
Paul Winkler
Right. I didn't know that before I looked at the site, so I'm glad I did.
I just wanted to prevent other people from making my initial mistake - assuming
that the tests only had to produce the same result. I was surprised how far down
the list python was on the fibonacci test until I started playing around with
alternative implementations and realized it was the recursion that was slowing
it down.
Fredrik Lundh
> Doing it iteratively is much, much faster.
does your fastest iterative solution beat this one?
import sys
def fib(n):
if n < 2:
return 1
return fib(n-2) + fib(n-1)
def fib(n, fib=fib, memo={}):
v = memo.get(n)
if v is None:
v = memo[n] = fib(n)
return v
def main():
N = int(sys.argv[1])
print fib(N)
</F>
Robin Becker
<fre...@pythonware.com> writes
--
Robin Becker
Bengt Richter
wrote:
>James Logajan wrote:
>>
>> Paul Winkler wrote:
>> > So basically what that benchmark tells me is: "Don't write recursively in Python
>> > if performance is an issue".
>>
>> Well yes, this is what benchmarks are useful for.
>
>Right. I didn't know that before I looked at the site, so I'm glad I did.
>
>I just wanted to prevent other people from making my initial mistake - assuming
>that the tests only had to produce the same result. I was surprised how far down
>the list python was on the fibonacci test until I started playing around with
>alternative implementations and realized it was the recursion that was slowing
>it down.
>
I just had a look at the site with the fibonacci
results. N=32 in 19.78 seconds. Python can do
better while still doing it recursively ;-)
I just did a python recursive fib(100000) in
just over 15 seconds, including startup and
printing to screen, by my watch. (Not a typo,
that was 100k). Of course, it might not be the
usual recursive solution (see below) ;-)
(300mhz P2, 320MB ram, NT4sp3)
Python 2.1 (#15, Apr 16 2001, 18:25:49) [MSC 32 bit (Intel)] on win32
Simple iteration using
def fib(x):
if x < 3:
return 1
f,fm1 = 1L,1L
for i in xrange(2,x):
f,fm1 = f+fm1,f
return f
took over 30 seconds ;-)
I haven't fine tuned this. It's a close translation of
a scheme version I came up with about five years ago.
Dave Ulrich may remember. He pointed out that the next to
last version wasn't doing what I thought. So he helped
nudge it into being. Never did establish what wheel I was
reinventing, but apparently there is something related.
___________________________________________________________
# ffibp.py - fast recursive fibonacci algorithm using pairs
# Copyright (c) 2001, Bengt Richter. All rights reserved.
# Use is governed by the GNU GENERAL PUBLIC LICENSE -- see
http://gnu.org
# NO WARRANTY EXPRESS OR IMPLIED IS GIVEN AS TO CORRECTNESS
# OR SUITABLILITY FOR ANY PURPOSE. USE AT YOUR OWN RISK.
#
import sys
def pfib(n):
if n < 2: return 1L,1L
if n == 2: return 1L,2L
k = n / 2L
fk,fkp1 = pfib(k) # recursion here
fkm1 = fkp1 - fk
if n&1:
return fkp1*fkp1 + fk*fk, fkp1*( fkp1+fk+fk)
else:
return fk*(fk+fkm1+fkm1), fkp1*fkp1 + fk*fk
def ffib(x):
if x < 3:
return 1
else:
fxm2,fxm1 = pfib( x - 2L )
return fxm2+fxm1
def main():
if len(sys.argv) != 2:
sys.stderr.write("usage: %s number\n" % sys.argv[0])
sys.exit(2)
print 'fib(',sys.argv[1],') = ', ffib( long(sys.argv[1]) )
if __name__ == "__main__":
main()
_____________________________________________________________--
Bengt Richter
<fre...@pythonware.com> wrote:
>Paul Winkler wrote:
>> Doing it iteratively is much, much faster.
Not necessarily. See my other post ;-)
>
>does your fastest iterative solution beat this one?
>
>import sys
>
>def fib(n):
> if n < 2:
> return 1
> return fib(n-2) + fib(n-1)
>
>def fib(n, fib=fib, memo={}):
> v = memo.get(n)
> if v is None:
> v = memo[n] = fib(n)
> return v
>
>def main():
> N = int(sys.argv[1])
> print fib(N)
>
></F>
>
>
My algorithm will beat this easily when
n gets big. But I like the memo thing.
That could improve mine too.
Paul Winkler
>
> Paul Winkler wrote:
> > Doing it iteratively is much, much faster.
>
> does your fastest iterative solution beat this one?
That's pretty fast, once I got it to work... but still not as fast as my best
one.
Yours iis definitely interesting, largely because I don't understand what the
hell it does. If I rename one of the fibs and change the appropriate call to use
the new name, it still computes fibonacci numbers but performance goes way down
as N rises. So you're somehow relying on the duplicated names for speed. That's
a pretty weird optimization technique.
Here's my version:
#!/usr/bin/env python
def fib5(n):
a, b = 0L, 1L
for i in range(n):
a, b = b, a + b
return b
def main():
N = int(sys.argv[1])
print fib5(N)
main()
# end of script
Now let's try them...
first mine:
$ time fibo.py 1000
70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501
real 0m0.083s
user 0m0.070s
sys 0m0.010s
Now let's try yours.
$ time fibo_effbot.py 1000
(long traceback snipped)
RuntimeError: maximum recursion depth exceeded
real 0m0.621s
user 0m0.160s
sys 0m0.070s
Not only is mine faster, it computes a result, too. :p
But seriously, let's try yours again, using sys.setrecursionlimit(99999999)
... whoops, now we get OverflowError: integer addition ...
OK, now I've fixed that too like so:
def fib(n):
if n < 2:
return 1L # the rest is unchanged...
Let me know if you think there's a better way to let your version handle large
values of N.
Anyway, trying it again with those modifications:
$ time fibo_effbot.py 1000
70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501
real 0m0.113s
user 0m0.090s
sys 0m0.020s
So that's 33 ms slower than mine for N=1000.
OK, let's try larger values.
$ time fibo.py 10000
(result snipped)
real 0m0.375s
user 0m0.350s
sys 0m0.020s
$ time fibo_effbot.py 10000
(result snipped)
real 0m0.789s
user 0m0.670s
sys 0m0.120s
$ time fibo.py 100000
(result snipped)
real 0m24.663s
user 0m24.370s
sys 0m0.020s
$ time fibo_effbot.py 100000
Segmentation fault (core dumped)
Paul Winkler
fibo.py is mine, ffib.py is yours.
Note that yours computes what is (according to mine and Frederik's scripts)
fibonacci of N-1 rather than fibonacci of N.
Other than that, you've kicked my butt!
Now is the time for me to strategically retreat and declare that what really
matters is readability. Who cares about speed? Not me! Never did, no sir.
$ time ffib.py 1001
fib( 1001 ) =
70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501
real 0m0.073s
user 0m0.060s
sys 0m0.010s
$ time fibo.py 1000
70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501
real 0m0.080s
user 0m0.050s
sys 0m0.020s
$ time ffib.py 10001
real 0m0.154s
user 0m0.140s
sys 0m0.020s
$ time fibo.py 10000
real 0m0.384s
user 0m0.370s
sys 0m0.020s
$ time ffib.py 100001
real 0m6.598s
user 0m6.550s
sys 0m0.030s
$ time fibo.py 100000
real 0m24.433s
user 0m24.370s
sys 0m0.020s
Bengt Richter
wrote:
>I just did a python recursive fib(100000) in
>just over 15 seconds, including startup and
>printing to screen, by my watch. (Not a typo,
>that was 100k). Of course, it might not be the
>usual recursive solution (see below) ;-)
>I haven't fine tuned this. It's a close translation of
- That 15 seconds was mostly conversion for printing.
Actual calculation time was more like 0.8 sec ;-)
- I should have eliminated an expression
Changes
---
#eliminated this > fkm1 = fkp1 - fk
> if n&1:
> return fkp1*fkp1 + fk*fk, fkp1*( fkp1+fk+fk)
> else:
#changed this > return fk*(fk+fkm1+fkm1), fkp1*fkp1 + fk*fk
return fk*(fkp1+fkp1-fk), fkp1*fkp1 + fk*fk
---
Sheesh. I also changed the a+a things above to a<<1 but it's in the
noise. Wonder if a**2 is much different from a*a for big longs...
I put in a clock() timer for calculation and printing. This gives
about 380 microseconds +- a few for N=32, and for N=100000:
That took 0.796213 seconds to calculate, and 15.226808 to print.
That took 0.797725 seconds to calculate, and 15.006354 to print.
That took 0.804495 seconds to calculate, and 14.893308 to print.
That took 0.800631 seconds to calculate, and 14.624085 to print.
is representative, again on
(300mhz P2, 320MB ram, NT4sp3)
Python 2.1 (#15, Apr 16 2001, 18:25:49) [MSC 32 bit (Intel)] on win32
Given the print time, apparently this recursion beat iteration by
0.8 vs about 15 seconds ((~32 hand timed load, calc, print) -15).
Never say never ;-)
Revised version:
______________________________________________________________
# fibpx.py - fast recursive fibonacci algorithm using pairs
# Copyright (c) 2001, Bengt Richter. All rights reserved.
# Use is governed by the GNU GENERAL PUBLIC LICENSE -- see
http://gnu.org
# NO WARRANTY EXPRESS OR IMPLIED IS GIVEN AS TO CORRECTNESS
# OR SUITABLILITY FOR ANY PURPOSE. USE AT YOUR OWN RISK.
#
# Updated 2001-07-09 bokr
#
import sys
def pfib(n):
if n < 2: return 1L,1L
if n == 2: return 1L,2L
k = n / 2L # this makes the log effect
fk,fkp1 = pfib(k) # recursion here
if n&1:
return fkp1*fkp1+fk*fk, fkp1*(fkp1+(fk<<1))
else:
return fk*((fkp1<<1)-fk), fkp1*fkp1+fk*fk
def ffib(x):
if x < 3:
return 1
else:
fxm2,fxm1 = pfib( x - 2L )
return fxm2+fxm1
import time
def main():
if len(sys.argv) != 2:
sys.stderr.write("usage: %s number\n" % sys.argv[0])
sys.exit(2)
tStart = time.clock()
answer = ffib( long(sys.argv[1]) )
tEnd = time.clock()
print 'fib(',sys.argv[1],') =\n', answer
tEndPrint = time.clock()
print "\nThat took %10.6f seconds to calculate," \
" and %8.6f to print." % (tEnd-tStart, tEndPrint-tEnd)
if __name__ == "__main__":
main()
______________________________________________________________
Malcolm Tredinnick
> Fredrik Lundh wrote:
> > does your fastest iterative solution beat this one?
>
> That's pretty fast, once I got it to work... but still not as fast as
> my best one. Yours iis definitely interesting, largely because I
> don't understand what the hell it does. If I rename one of the fibs
> and change the appropriate call to use the new name, it still computes
> fibonacci numbers but performance goes way down as N rises. So you're
> somehow relying on the duplicated names for speed. That's a pretty
> weird optimization technique.
Ooh, ooh ... I know this one. :-)
It's a scoping trick (and it really is a "trick" here, because the same
name is being used and this leads to a bit of confusion).
/F's solution makes sure that the code objcet of the first 'fib' is in
the local namespace of the second 'fib' function. This speeds up lookups
to it significantly (local variables are implemented as a dictionary,
globals are not).
Does that make it understandable (I could rabbit on a lot further, but
why spoil all the fun)?
Cheers,
Malcolm
--
Honk if you love peace and quiet.
Bengt Richter
wrote:
>OK, I'll bite.
>fibo.py is mine, ffib.py is yours.
>Note that yours computes what is (according to mine and Frederik's scripts)
>fibonacci of N-1 rather than fibonacci of N.
>
I think it's ok for >0, but my fib(0) is plain wrong. A leftover
kludge to make it safe for negative numbers at the same time as
the starting case. Not very pure. I just googled and found
http://math.holycross.edu/~davids/fibonacci/fibonacci.html
which seems to agree. Originally I got the sequence definition
from a scheme book with the usual recursive demo examples.
I also just now googled to
http://www.auto.tuwien.ac.at/~blieb/woop/fibnum.html
where I found not only the definition
F0=0, F1=1, Fn=Fn-1+Fn-2 for n>=2
This defines the sequence 0, 1, 1, 2, 3, 5, 8, 13, 21 and so on.
but also what appears to be an iterative version or variant of my
recursive algorithm. At least some of the expression terms look
suspiciously similar. But it's written in gnat, and seems to use
lower case L as a variable, which ought to be outlawed, plus
it's got a couple Ada tricks I don't recognize. But at some point
I'd like to translate it to Python for comparison. It should be
the fastest. Of course it won't be recursive.
>Other than that, you've kicked my butt!
>
>Now is the time for me to strategically retreat and declare that what really
>matters is readability. Who cares about speed? Not me! Never did, no sir.
>
LOL, thanks for the chuckle ;-)
Tim Peters
> ...
> I just did a python recursive fib(100000) in
> just over 15 seconds, including startup and
> printing to screen, by my watch. (Not a typo,
> that was 100k). Of course, it might not be the
> usual recursive solution (see below) ;-)
> It's a close translation of a scheme version I came
> up with about five years ago. Dave Ulrich may remember.
> He pointed out that the next to last version wasn't
> doing what I thought. So he helped nudge it into being.
> Never did establish what wheel I was reinventing, but
> apparently there is something related.
Cute! For "something related", see Knuth section 4.6.3 exercise 26.
Apart from tricks specific to Fibonacci numbers, a general "good thing to
know" is that an order-N linear recurrence can be viewed as mapping
N-vectors to N-vectors via multiplication by a fixed NxN matrix M. N==2 in
this case, and if a,b,c are consecutive Fibonacci numbers then
[b c] = [a b] * M
where "*" is matmult and M is
0 1
1 1
That's why your program wound up with expressions that look a lot like
2-term dot products: they are <wink>! Moving ahead k steps is essentially
equivalent to computing M**k, and that can be done in "the usual" way via
O(log(k)) 2x2 matmults. This has practical application in, e.g., many kinds
of recurrence-based random-number generators, for "skipping ahead" a huge
number of terms very quickly.
Thomas Wouters
> On Tue, Jul 10, 2001 at 02:26:44AM +0000, Paul Winkler wrote:
> > Fredrik Lundh wrote:
[ Fredrik does 'def fib(..); def fib(.., fib=fib, ...); ]
> > That's pretty fast, once I got it to work... but still not as fast as
> > my best one. Yours iis definitely interesting, largely because I
> > don't understand what the hell it does. If I rename one of the fibs
> > and change the appropriate call to use the new name, it still computes
> > fibonacci numbers but performance goes way down as N rises. So you're
> > somehow relying on the duplicated names for speed. That's a pretty
> > weird optimization technique.
Note that there is no reason for the performance to drop dramatically as
long as you change the correct names: you need to change the first
function's name, both 'fib's in the argument list of the second function (so
both 'fib' and 'fib' in 'fib=fib') and all occurances of 'fib' in the second
function's body.
> Ooh, ooh ... I know this one. :-)
> /F's solution makes sure that the code objcet of the first 'fib' is in
> the local namespace of the second 'fib' function. This speeds up lookups
> to it significantly (local variables are implemented as a dictionary,
> globals are not).
No, that's reversed :) Globals *are* a dictionary, locals are not. If a name
is known to be local (by the compiler), and the local namespace can't be
modified indirectly (by 'from .. import *' or a bare 'exec',) the variable
access is compiled into a simple array index, which is much faster than a
dictionary lookup. If you put a bare, useless 'exec' in the function, you'll
likely see a dramatic performance drop :)
--
Thomas Wouters <tho...@xs4all.net>
Hi! I'm a .signature virus! copy me into your .signature file to help me spread!
David C. Ullrich
wrote:
Yup. Many years ago one of my favorite applications in linear algebra
was showing the kids how to compute M**k here by first diagonalizing
M. A smaller number of years ago I realized how wrong that was, from
a computational standpoint. Never got a chance to tell the kids
I'd lied - probably they're all lurking here so now it's ok.
(Took a minute to find fib.py just now, because it was filed
under "MatrixTypes". I calculate fib(100000) in 1.7
seconds this way; for comparison, str(fib(100000)) takes
8.0 seconds.)
David C. Ullrich
**********************************
About this published paper that has to do with some agreements with some of the
things that I say, I heard about it at least a couple months ago, although it might
have been within the last two months. (Ross Finlayson, sci.math 7-6-01)
Paul Winkler
> Apart from tricks specific to Fibonacci numbers, a general "good thing to
> know" is that an order-N linear recurrence can be viewed as mapping
> N-vectors to N-vectors via multiplication by a fixed NxN matrix M. N==2 in
> this case, and if a,b,c are consecutive Fibonacci numbers then
>
> [b c] = [a b] * M
>
> where "*" is matmult and M is
>
> 0 1
> 1 1
For the mathematically challenged, what is matmult?
Pointer to a FM to R would be fine.
Thanks,
PW
gbr...@cix.compulink.co.uk
Winkler) wrote:
> For the mathematically challenged, what is matmult?
> Pointer to a FM to R would be fine.
Ooh! I've got one of them!
<http://www.microtonal.co.uk/matritut.htm>
Graham
Paul Winkler
THanks!
Bengt Richter
Ullrich) wrote:
>On Tue, 10 Jul 2001 01:18:16 -0400, "Tim Peters" <tim...@home.com>
>wrote:
>
>>[Bengt Richter]
>>> ...
>>> I just did a python recursive fib(100000) in
>>> just over 15 seconds, including startup and
which turned out to be mostly str conversion for
the print, so I thought I'd try recursion on that...
(see below ;-)
[...]
>(Took a minute to find fib.py just now, because it was filed
>under "MatrixTypes". I calculate fib(100000) in 1.7
>seconds this way; for comparison, str(fib(100000)) takes
>8.0 seconds.)
Hi Dave ;-)
Try strL for comparison. It's recursive, and faster than str
for big numbers. I got
>>> len(strL.strL(ffib(100000)))
20899
so you can type in 10L**20899 on the command line
for a number in the same ballpark as the fib, for a test.
On my system I get
[18:47] C:\pywk\fib>strL.py str 10L**20899
str took 13.601617 seconds
[18:47] C:\pywk\fib>strL.py strL 10L**20899
strL took 1.044989 seconds
Recursion rides again ;-)
BTW, how do you put everything inside the strL def
to hide names, and how do you recurse inside without
a warning message?
A couple of lines wrapped...
_______________________________________________________________
# strL.py -- recursive long to decimal string conversion
# 2001-07-10 bokr
#
p10d={}
def p10(n):
if not p10d.has_key(n):
p = p10d[n] = 10L**n
return p
return p10d[n]
def strLR(n,w=0): # w>0 is known width, w<0 is searching guess
if w == 0: return []
if w > 0:
if w <=9: return [('%0'+chr(w+48)+'d') % n]
wr = w/2
nl,nr = divmod(n,p10(wr))
return strLR(nl,w-wr)+strLR(nr,wr)
else:
nl,nr = divmod(n,p10(-w))
if nl:
return strLR(nl, 2*w) + strLR(nr,-w)
else:
if w >= -9:
return ['%d' % n]
else:
return strLR(nr,w/2)
def strL(n):
if n<0:
return ''.join(['-']+strLR(-n,-9))
else:
return ''.join(strLR(n,-9))
from time import clock
import sys
def main():
def pr(x):
print x
def psl(x):
s = strL(x)
sys.stdout.write(s)
sys.stdout.write('\n')
dt={'str':str,'strL':strL,'repr':repr, 'print':pr, 'printStrL':psl
}
try:
x=long( eval(sys.argv[2]) )
fn=sys.argv[1]
fcn=dt[fn]
except:
sys.stderr.write("usage: %s [str strL repr print printStrL]
<const expr>\n" % sys.argv[0])
sys.exit(2)
t0=clock()
fcn(x)
t1=clock()
print "%s took %9.6f seconds" % (fn,t1-t0)
if __name__ == "__main__":
main()
_______________________________________________________________
David C. Ullrich
wrote:
>On Tue, 10 Jul 2001 13:54:47 GMT, ull...@math.okstate.edu (David C.
>Ullrich) wrote:
>
>>On Tue, 10 Jul 2001 01:18:16 -0400, "Tim Peters" <tim...@home.com>
>>wrote:
>>
>>>[Bengt Richter]
>>>> ...
>>>> I just did a python recursive fib(100000) in
>>>> just over 15 seconds, including startup and
>which turned out to be mostly str conversion for
>the print, so I thought I'd try recursion on that...
>(see below ;-)
Sorry I missed the "which turned out to be
mostly str conversion" the first time I read this.
>[...]
>>(Took a minute to find fib.py just now, because it was filed
>>under "MatrixTypes". I calculate fib(100000) in 1.7
>>seconds this way; for comparison, str(fib(100000)) takes
>>8.0 seconds.)
>Hi Dave ;-)
>
>Try strL for comparison. It's recursive, and faster than str
>for big numbers. I got
> >>> len(strL.strL(ffib(100000)))
> 20899
>
>so you can type in 10L**20899 on the command line
>for a number in the same ballpark as the fib, for a test.
>On my system I get
>
>[18:47] C:\pywk\fib>strL.py str 10L**20899
>str took 13.601617 seconds
>
>[18:47] C:\pywk\fib>strL.py strL 10L**20899
>strL took 1.044989 seconds
>
>Recursion rides again ;-)
Recursive or not, the idea that we can write
a replacement for str that's faster is very
curious.
Of course you have to do the recursion in a non-stupid
manner, as here; if you'd made a recurzive routine
that concatenated Python strings instead of building
that list I doubt that recursion would win. But it is
curious how often recursion does seem to win in Python.
(Doesn't usually beat built-in functions, though.)
David C. Ullrich
Jeff Shannon
"David C. Ullrich" wrote:
> On Wed, 11 Jul 2001 01:47:30 GMT, bo...@accessone.com (Bengt Richter)
> wrote:
>
> >[18:47] C:\pywk\fib>strL.py str 10L**20899
> >str took 13.601617 seconds
> >
> >[18:47] C:\pywk\fib>strL.py strL 10L**20899
> >strL took 1.044989 seconds
> >
> >Recursion rides again ;-)
>
> Recursive or not, the idea that we can write
> a replacement for str that's faster is very
> curious.
How much of this difference in speed, though, is because strL()
is a special purpose integer->string conversion, where the
standard str() is a general-purpose anything->string conversion?
Jeff Shannon
Technician/Programmer
Credit International
Bengt Richter
I would guess the general purpose str already does something
internally specialized for longs. However, the % operator is even
more general purpose, and you may note that I used it
to trim my trees in strL (because it is faster than carrying
strLR's recursion all the way down to w=1 and chr(48+n) )
BDFL & Tim & co probably just had better things to do than cater
to the small percentage of strange people with programs
that need to convert longs to multi-kilo-digit integers ;-)
I'm sure they know how to do this kind of thing very well,
but if they think it's worth the seldom-used-bloat-increment,
they're certainly welcome to take strL and make it truly
Python-worthy and incorporate it. (Maybe I'd find out how to
keep everything but strL invisible from the user, and make
strLR nested without triggering a warning ;-)
Bengt Richter
[...]
>>On my system I get
>>
>>[18:47] C:\pywk\fib>strL.py str 10L**20899
>>str took 13.601617 seconds
>>
>>[18:47] C:\pywk\fib>strL.py strL 10L**20899
>>strL took 1.044989 seconds
>>
>>Recursion rides again ;-)
>
>Recursive or not, the idea that we can write
>a replacement for str that's faster is very
>curious.
>
monster longs. They surely had more urgent things to do ;-)
>>BTW, how do you put everything inside the strL def
>>to hide names, and how do you recurse inside without
>>a warning message?
I'm leaving this question in ;-)
[...]
>
>Of course you have to do the recursion in a non-stupid
>manner, as here; if you'd made a recurzive routine
>that concatenated Python strings instead of building
>that list I doubt that recursion would win. But it is
>curious how often recursion does seem to win in Python.
>(Doesn't usually beat built-in functions, though.)
>
I hope people realize what you are pointing out,
i.e., that it's not recursion per se that made the gains.
The algorithm is the thing.
Recursion is a powerful way of expressing algorithms,
and the more expressive power you have, the better your
chances of coming up with a good algorithm.
Clean expressive power is Python's main attraction IMO.
A better algorithm can often overcome the advantage of
optimized brute force, and recursion is a natural when
you have foo(x) and can partition x into x1 and x2 such that
foo(x) == bar( foo(x1), foo(x2) )
and the times for foo-ing the pieces and bar-ing their
results is less than the time for foo-ing the whole.
BTW, if we were recursively searching for the optimumly timed partition
and sub-partitions, UIAM & IIRC it would amount to optimization by
Dynamic programming, I think. You know, the Bellman thing ;-)
Fernando Pereira
<tim...@home.com> wrote:
> a general "good thing to
> know" is that an order-N linear recurrence can be viewed as mapping
> N-vectors to N-vectors via multiplication by a fixed NxN matrix M.
M. D. McIlroy, Functional pearl: Power series, power serious, J. of
Functional Programming 9 (1999) 323-335
http://www.cs.dartmouth.edu/~doug/pearl.ps.gz
and
M. D. McIlroy, The music of streams, Information Processing Letters 77
(2001) 189-195
http://www.cs.dartmouth.edu/~doug/mdmspe.ps.gz
-- F
Andrew Gaul
> One more point about shootout. If I understood correctly, advanced
> features are banned. You can't change
>
> k = []
> for i in list:
> k.append(f(i)
>
> into:
>
> k = [f(i) for i in list]
Actually, the former isn't much slower than the latter. Using map is
almost twice as fast. I believe that map generates the result list by
calling len() on the source list, avoiding the cost of growing the
result list. I suppose list comprehensions could be implemented such
that if there were not a filter clause, to prealloacte the list. But
then, one should be using map anyway (you're only saving an implicit
lambda using a list comprehension).
meatring [~]$ time python2.1 -c 'k = []
for x in xrange(1000000):
k.append(x)'
real 0m3.934s
user 0m3.440s
sys 0m0.490s
meatring [~]$ time python2.1 -c '[ x+1 for x in xrange(1000000) ]'
real 0m3.402s
user 0m2.670s
sys 0m0.720s
meatring [~]$ time python2.1 -c 'map(lambda x: x+1, xrange(1000000))'
real 0m1.899s
user 0m1.840s
sys 0m0.060s
--
| a | n | d | r | e | w | @ | g | a | u | l | . | o | r | g |
White trash. Loser. Geek.
Tim Peters
> I would guess the general purpose str already does something
> internally specialized for longs.
Yes it does. Every type gets to implement its own routine for repr() (and
at the Python level, every class gets to implement its own too-- if it wants
to --via defining a __repr__ method, and/or a __str__ method).
> However, the % operator is even more general purpose, and you may
> note that I used it to trim my trees in strL (because it is faster
> than carrying strLR's recursion all the way down to w=1 and chr(48+n)).
And %d defers right back to the long repr routine!
> BDFL & Tim & co probably just had better things to do than cater
> to the small percentage of strange people with programs
> that need to convert longs to multi-kilo-digit integers ;-)
We *do* cater to it, but only in the power-of-2 forms: hex(long) and
oct(long) are linear-time, and you're not going to beat those with Python
code. For base 10, it's a dead-simple loop that just divides by 10 over and
over again; this is quadratic-time in the number of digits.
> I'm sure they know how to do this kind of thing very well,
> but if they think it's worth the seldom-used-bloat-increment,
> they're certainly welcome to take strL and make it truly
> Python-worthy and incorporate it.
The rub is that while this kind of thing is fun and easy to program in
Python, it's a total pain in the ass to program in C, and indeed leads to
code bloat. Since Python longs use base 2**15 internally, converting to
power-of-2 bases is both simple and fast in C, so we settled for that.
Here's another fun one: you can also write a long-int multiplication
routine in Python that runs significantly faster than the builtin long *!
Hint: recursion <wink>.
You can even write Python routines to do str(dict) and str(list) much faster
than the builtins, for very large dicts and lists. But you have to hurry on
those, because Python 2.2 will finally use linear-time algorithms for those
under the covers.
> (Maybe I'd find out how to keep everything but strL invisible from
> the user, and make strLR nested without triggering a warning ;-)
Use Python 2.1, nest the helper functions, and put
from __future__ import nested_scopes
at the top of the module. Heh -- you probably think I'm kidding.
but-i'm-not-ly y'rs - tim
Tim Peters
> M. D. McIlroy, Functional pearl: Power series, power serious, J. of
> Functional Programming 9 (1999) 323-335
>
> http://www.cs.dartmouth.edu/~doug/pearl.ps.gz
Yup, that's fun! Even with generators in Pytnon 2.2, "this kind of thing"
is more pleasant in Haskell -- but then that's not what generators were
aiming at.
> and
>
> M. D. McIlroy, The music of streams, Information Processing Letters 77
> (2001) 189-195
>
> http://www.cs.dartmouth.edu/~doug/mdmspe.ps.gz
That's actually a link to "A Killer Adversary for Quicksort". I expect this
was intended:
http://www.cs.dartmouth.edu/~doug/music.ps.gz
Bengt Richter
[...]
>
>The rub is that while this kind of thing is fun and easy to program in
>Python, it's a total pain in the ass to program in C, and indeed leads to
>code bloat. Since Python longs use base 2**15 internally, converting to
>power-of-2 bases is both simple and fast in C, so we settled for that.
>
python bytecode in python, even if there could be both speed and
space advantage for a given function?
So long as you weren't trying to lift yourself by not-yet-existent
boot straps, why not? That sounds a little funny, but ITYKWIM ;-)
BTW, looking at the way you can call the interpreter from C for embedding,
I would think you could write a translator for a useful subset of python
that would output a mix of plain C and Py_whatever calls to create C source
that could be compiled and linked into CPython. This would bypass the PITA
part and leave the fun part, ISTM ;-) Could you alter the byte code compiler
to emit this?
Done that way, strL wouldn't amount to that much C (or would it?), and you
could have 100% C code that way (i.e., not even byte codes as C constants
to feed the python interpreter).
David C. Ullrich
wrote:
>
>
Surely almost none of it! I don't know anything about the
internal representation of Python objects, but I tend to
doubt it takes more than a tick or two for str() to determine
that the argument is a long and call the appropriate
long->string code.
>Jeff Shannon
>Technician/Programmer
>Credit International
>
>
>
David C. Ullrich
David C. Ullrich
wrote:
>On Wed, 11 Jul 2001 14:48:13 GMT, ull...@math.okstate.edu (David C. Ullrich) wrote:
>[...]
>>>On my system I get
>>>
>>>[18:47] C:\pywk\fib>strL.py str 10L**20899
>>>str took 13.601617 seconds
>>>
>>>[18:47] C:\pywk\fib>strL.py strL 10L**20899
>>>strL took 1.044989 seconds
>>>
>>>Recursion rides again ;-)
>>
>>Recursive or not, the idea that we can write
>>a replacement for str that's faster is very
>>curious.
>>
>Well, it's a seldom-used aspect of str to print
>monster longs. They surely had more urgent things to do ;-)
Certainly - I wasn't meaning to say that they were
bad or I wanted my money back or anything. It _is_
curious nonetheless.
>>>BTW, how do you put everything inside the strL def
>>>to hide names, and how do you recurse inside without
>>>a warning message?
>I'm leaving this question in ;-)
Ok, I'll leave it in too then; maybe someone who
knows what they're talking about will have a hint.
>[...]
>>
>>Of course you have to do the recursion in a non-stupid
>>manner, as here; if you'd made a recurzive routine
>>that concatenated Python strings instead of building
>>that list I doubt that recursion would win. But it is
>>curious how often recursion does seem to win in Python.
>>(Doesn't usually beat built-in functions, though.)
>>
>
>I hope people realize what you are pointing out,
>i.e., that it's not recursion per se that made the gains.
>The algorithm is the thing.
>
>Recursion is a powerful way of expressing algorithms,
>and the more expressive power you have, the better your
>chances of coming up with a good algorithm.
>Clean expressive power is Python's main attraction IMO.
Huh. A better explanation than I actually expected.
David C. Ullrich
David C. Ullrich
wrote:
[...]
>
>Here's another fun one: you can also write a long-int multiplication
>routine in Python that runs significantly faster than the builtin long *!
>Hint: recursion <wink>.
I give up, howdaya do that?
(When I read this I said aha, you're getting at something like
using
[*] (a*2**k+b)*(c*2**k+d) = a*c*2**(2*k) + (a*d+b*c)*2**k + b*d.
But when I think about it I don't see why that would give any
improvement - it _seems_ to me that vanilla long multiplication
should be quadratic (a*b takes time "len"(a) * "len"(b), where
"len" is the number of "digits".) If that's correct then using
[*] wouldn't improve things at all as far as I can see.
Can't decide:
You're hinting at [*] and I'm analyzing it wrong? (Like
if vanilla multiplication is actually worse than quadratic
in the sense above then [*] will speed things up...)
You're hinting at something kinda like [*] but with clever
rearrangents that does give improvement, like that
Strassen(?) thing for matrix multiplcation?
You're talking about using an FFT-based multiplication?
(One can certainly write a recursive FFT. But surely if
_this_ is what you meant then the hint would be "FFT"
instead of "recursion"...)
Something else entirely?
???)
David C. Ullrich
Emmanuel Jeandel
> On Wed, 11 Jul 2001 23:52:59 -0400, "Tim Peters" <tim...@home.com>
> wrote:
>
> [...]
>>
>>Here's another fun one: you can also write a long-int multiplication
>>routine in Python that runs significantly faster than the builtin long *!
>>Hint: recursion <wink>.
>
> I give up, howdaya do that?
>
> (When I read this I said aha, you're getting at something like
> using
>
> [*] (a*2**k+b)*(c*2**k+d) = a*c*2**(2*k) + (a*d+b*c)*2**k + b*d.
>
(a*2**k+b)*(c*2**k+d) = a*c*2**(2*k) + ((a+d)*(b+c) - a*c - b*d)*2**k + b*d.
You only have to compute 3 multiplications
a*c
b*d
(a+d)*(b+c)
Then you can have an algorithm for multiplying a and b, if a and b
are of the same size (len(a) = len(b)) of complexity
len(a)**(1.6)
significantly better than len(a)**2
(len(a)*len(b) is *not* linear, rather quadratic)
Emmanuel
Tim Peters
> Here's another fun one: you can also write a long-int multiplication
> routine in Python that runs significantly faster than the builtin
> long *! Hint: recursion <wink>.
[David C. Ullrich]
> I give up, howdaya do that?
>
> (When I read this I said aha, you're getting at something like
> using
>
> [*] (a*2**k+b)*(c*2**k+d) = a*c*2**(2*k) + (a*d+b*c)*2**k + b*d.
>
> But when I think about it I don't see why that would give any
> improvement - it _seems_ to me that vanilla long multiplication
> should be quadratic (a*b takes time "len"(a) * "len"(b), where
> "len" is the number of "digits".) If that's correct then using
> [*] wouldn't improve things at all as far as I can see.
Right, it's not "clever" enough: that reduces an NxN mult to four
(N/2)x(N/2) mults. NxN takes N**2 "elementary" (1x1->2) mults, and
(N/2)x(N/2) N**2/4, so four of the latter is no savings over the former.
The trick is to reduce it to three (N/2)x(N/2) multiplications (and
recursively too for those in turn). Then the overall complexity drops from
O(N**2) to O(N**log2(3)) ~= O(N**1.58).
> Can't decide:
>
> You're hinting at [*] and I'm analyzing it wrong? (Like
> if vanilla multiplication is actually worse than quadratic
> in the sense above then [*] will speed things up...)
You'll figure it out <wink>. "An answer" is spelled out in Knuth vol 2, or
search for "Karatsuba multiplication" on the web.
> You're hinting at something kinda like [*] but with clever
> rearrangents that does give improvement, like that
> Strassen(?) thing for matrix multiplcation?
Yes, but not nearly *that* clever.
> You're talking about using an FFT-based multiplication?
> (One can certainly write a recursive FFT. But surely if
> _this_ is what you meant then the hint would be "FFT"
> instead of "recursion"...)
I'm not sure you can write one of those *in Python* that's actually faster
than the builtin long *, unless the longs are so large nobody would care.
See
http://groups.yahoo.com/group/python-list/message/63188
and followups for Christian Tismer's last known stab at implementing
Karatsuba in Python. It pays for ints short enough that somebody *might*
care. OTOH, anyone who cares a lot should be using one of the GMP wrappers
(GMP also uses this trick, but in excruciatingly long-winded and
platform-optimized C).
David C. Ullrich
wrote:
>In article <3b4eed0...@nntp.sprynet.com>, David C. Ullrich wrote:
>> On Wed, 11 Jul 2001 23:52:59 -0400, "Tim Peters" <tim...@home.com>
>> wrote:
>>
>> [...]
>>>
>>>Here's another fun one: you can also write a long-int multiplication
>>>routine in Python that runs significantly faster than the builtin long *!
>>>Hint: recursion <wink>.
>>
>> I give up, howdaya do that?
>>
>> (When I read this I said aha, you're getting at something like
>> using
>>
>> [*] (a*2**k+b)*(c*2**k+d) = a*c*2**(2*k) + (a*d+b*c)*2**k + b*d.
>>
>Perhaps you mean :
>(a*2**k+b)*(c*2**k+d) = a*c*2**(2*k) + ((a+d)*(b+c) - a*c - b*d)*2**k + b*d.
Aha. No, that's not what I "meant", but it's exactly what I wondered
Tim meant (too early in the morning to try to make an English sentence
out of this). Thanks.
>You only have to compute 3 multiplications
> a*c
> b*d
> (a+d)*(b+c)
>
>Then you can have an algorithm for multiplying a and b, if a and b
>are of the same size (len(a) = len(b)) of complexity
>len(a)**(1.6)
>significantly better than len(a)**2
>(len(a)*len(b) is *not* linear, rather quadratic)
>
>Emmanuel
David C. Ullrich
David C. Ullrich
wrote:
>[Tim]
>> Here's another fun one: you can also write a long-int multiplication
>> routine in Python that runs significantly faster than the builtin
>> long *! Hint: recursion <wink>.
>
>[David C. Ullrich]
>> I give up, howdaya do that?
>>
>> (When I read this I said aha, you're getting at something like
>> using
>>
>> [*] (a*2**k+b)*(c*2**k+d) = a*c*2**(2*k) + (a*d+b*c)*2**k + b*d.
>>
>> But when I think about it I don't see why that would give any
>> improvement - it _seems_ to me that vanilla long multiplication
>> should be quadratic (a*b takes time "len"(a) * "len"(b), where
>> "len" is the number of "digits".) If that's correct then using
>> [*] wouldn't improve things at all as far as I can see.
>
>Right, it's not "clever" enough: that reduces an NxN mult to four
>(N/2)x(N/2) mults. NxN takes N**2 "elementary" (1x1->2) mults, and
>(N/2)x(N/2) N**2/4, so four of the latter is no savings over the former.
>
>The trick is to reduce it to three (N/2)x(N/2) multiplications
That would do it all right...
>(and
>recursively too for those in turn). Then the overall complexity drops from
>O(N**2) to O(N**log2(3)) ~= O(N**1.58).
>
>> Can't decide:
>>
>> You're hinting at [*] and I'm analyzing it wrong? (Like
>> if vanilla multiplication is actually worse than quadratic
>> in the sense above then [*] will speed things up...)
>
>You'll figure it out <wink>.
Thanks. (Too late, Emmanuel already gave it away.)
> "An answer" is spelled out in Knuth vol 2, or
>search for "Karatsuba multiplication" on the web.
>
>> You're hinting at something kinda like [*] but with clever
>> rearrangents that does give improvement, like that
>> Strassen(?) thing for matrix multiplcation?
>
>Yes, but not nearly *that* clever.
>
>> You're talking about using an FFT-based multiplication?
>> (One can certainly write a recursive FFT. But surely if
>> _this_ is what you meant then the hint would be "FFT"
>> instead of "recursion"...)
>
>I'm not sure you can write one of those *in Python* that's actually faster
>than the builtin long *, unless the longs are so large nobody would care.
Doesn't seem likely to me either, wasn't sure what you were getting
at. (Just for giggles I made a few Python FFT's yesterday; one of
them is only about 100 times slower than the same algorithm in
Object Pascal...)
>See
>
> http://groups.yahoo.com/group/python-list/message/63188
>
>and followups for Christian Tismer's last known stab at implementing
>Karatsuba in Python. It pays for ints short enough that somebody *might*
>care. OTOH, anyone who cares a lot should be using one of the GMP wrappers
>(GMP also uses this trick, but in excruciatingly long-winded and
>platform-optimized C).
Right - wasn't meaning to suggest that this was the right solution
for serious work, just wanted to know what the algorithm in
question was. Lemme write this down: Karatsuba.
David C. Ullrich