However, if I do the following, the timings look the same.
sage: sage: L6=srange(1000000)
sage: sage: timeit('a=sum(L6,0)')
5 loops, best of 3: 179 ms per loop
sage: sage: timeit('a=balanced_sum(L6,0)')
5 loops, best of 3: 202 ms per loop
--Mike
On Mon, Mar 31, 2008 at 4:04 AM, Mike Hansen <[EMAIL PROTECTED]> wrote:
> 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
-~----------~----~----~----~------~----~------~--~---
