Splitting it like this still yields a linear algorithm. If f(n) is
the time to add a list of length n, then you have
f(n) = 2*f(n/2), so f(n) is linear.
David
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
-~----------~----~----~----~------~----~------~--~---
