Language Shootout

[David C. Ullrich]

On Wed, 11 Jul 2001 01:47:30 GMT, bokr at accessone.com (Bengt Richter)
wrote:

>On Tue, 10 Jul 2001 13:54:47 GMT, ullrich at math.okstate.edu (David C.
>Ullrich) wrote:
>
>>On Tue, 10 Jul 2001 01:18:16 -0400, "Tim Peters" <tim.one at 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.

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

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

>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