Here are the timings I get by pretty much just copying balanced_list_prod.
sage: L2=range(100)
sage: L3=range(1000)
sage: L4=range(10000)
sage: L5=range(100000)
sage: L6=range(1000000)
sage: timeit('a=balanced_sum(L2,0)')
625 loops, best of 3: 12.6 µs per loop
sage: timeit('a=sum(L2,0)')
625 loops, best of 3: 101 µs per loop
sage: timeit('a=balanced_sum(L3,0)')
625 loops, best of 3: 47.4 µs per loop
sage: timeit('a=sum(L3,0)')
625 loops, best of 3: 1.02 ms per loop
sage: timeit('a=balanced_sum(L4,0)')
625 loops, best of 3: 469 µs per loop
sage: timeit('a=sum(L4,0)')
25 loops, best of 3: 10.2 ms per loop
sage: timeit('a=balanced_sum(L5,0)')
125 loops, best of 3: 4.54 ms per loop
sage: timeit('a=sum(L5,0)')
5 loops, best of 3: 104 ms per loop
sage: timeit('a=balanced_sum(L6,0)')
5 loops, best of 3: 54.5 ms per loop
sage: timeit('a=sum(L6,0)')
5 loops, best of 3: 1.05 s per loop
--Mike
On Mon, Mar 31, 2008 at 1:13 AM, David Roe <[EMAIL PROTECTED]> wrote:
>
> 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
-~----------~----~----~----~------~----~------~--~---
