Hi Simon,
sum() is a builtin Python function. There has been passing discussion
of making an asymptotically fast sum function, but I don't think that
anyone has gotten around to it. There is a balanced product which you
can find
http://www.sagemath.org/hg/sage-main/file/cc1e12a492fc/sage/misc/misc_c.pyx
. Writing a balanced sum based on that wouldn't be too difficult.
--Mike
On Mon, Mar 31, 2008 at 1:04 AM, Simon King <[EMAIL PROTECTED]> wrote:
>
> Dear Sage team,
>
> i made a few timings with the "sum" function:
>
> sage: L2=range(100)
> sage: L3=range(1000)
> sage: L4=range(10000)
> sage: L5=range(100000)
> sage: L6=range(1000000)
> sage: timeit('a=sum(L2,0)')
> 625 loops, best of 3: 299 µs per loop
> sage: timeit('a=sum(L3,0)')
> 125 loops, best of 3: 1.35 ms per loop
> sage: timeit('a=sum(L4,0)')
> 25 loops, best of 3: 13.6 ms per loop
> sage: timeit('a=sum(L5,0)')
> 5 loops, best of 3: 138 ms per loop
> sage: timeit('a=sum(L6,0)')
> 5 loops, best of 3: 1.37 s per loop
>
> So, it seems that the time grows about linearly in the length of the
> list. Shouldn't it be possible to have it growing logarithmically?
> Namely when sum(L) splits L into two sub-lists L0,L1 of about the same
> size and returns sum(L0)+sum(L1)? Or would this introduce a huge
> overhead?
>
> I am not a computer scientist, so perhaps i am mistaken. Where is the
> source code of the sum function?
>
> Yours
> Simon
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
