On Tue, Nov 23, 2010 at 8:51 AM, John Cremona <john.crem...@gmail.com> wrote:
> So: in Pablo's first version the problem was not in computing
> len(results), but in the comparison between that value (a Python int)
> and the Sage Integer cota, which involves creating a temporary Sage
> integer and then doing the comparison between two of those.
Yep. Since this is such a common case, I wonder if we should modify
the Sage integer __richcmp__ method to be more sophisticated, and
allow direct comparisons with builtin Python types, without first
requiring them to be converted to Sage integers? The main problem
with:
"while len(results)<cota:"
is that in every iteration, len(results) is converted to a Sage
integer, and that conversion is expensive.
GMP has a function:
mpz_cmp_si
and we could rewrite Sage integers so if comparing with a Python int,
one grabs the long out of it (very quick) and calls mpz_cmp_si.
Does anybody want to do this? See the function
def __richcmp__(left, right, int op):
in devel/sage/rings/integer.pyx to get going.
> In Pablo's second version there is no conversion, but still two Sage
> integers are being compared.
>
> In Tom's version the variable cota is a python int so (since taking
> len() really is negligible!) the speedup comes from the speed of
> comparing two (very small) python ints.
>
> There is a lesson to be learned here, which is in fact very similar to
> one which William explained very well recently: beware the Sage
> preprocessor which converts every integer it sees to an Integer, which
> can have serious performance consequences and is often not necessary!
But also a good way to point out ideas for optimizations to Sage.
William
>
> John
>
> On Tue, Nov 23, 2010 at 4:44 PM, Tom Boothby <tomas.boot...@gmail.com> wrote:
>> The problem is not with len(), merely with the conversion from an int
>> to an Integer required in comparing len(results)<cota.
>>
>> The following code is faster than either of your versions. Note that
>> '3r' is an int, whereas '3' is an Integer.
>>
>> tri=pen=hex=dt=dp=dh=1r
>> results=[]
>> cota = 3r
>> while len(results)<cota:
>> if tri==pen==hex:
>> results.append(tri)
>> if tri<=pen and tri<=hex:
>> dt+=1r
>> tri+=dt
>> elif pen<=hex:
>> dp+=3r
>> pen+=dp
>> else:
>> dh+=4r
>> hex+=dh
>> print results
>>
>> On Tue, Nov 23, 2010 at 3:00 AM, Pablo Angulo <pablo.ang...@uam.es> wrote:
>>> Hello:
>>> A colleague was working in code for a certain projecteuler problem,
>>> and found that using "len" of a list has a severe penalty on the sage
>>> notebook, which doesn't happen on either the sage or the python console.
>>> The two versions of the code below differ only in a call to the function
>>> len. In console, the penalty in performance is around 10%, but in the
>>> Sage notebook, it takes 3 times longer: the call to "len" costs doble
>>> time as the rest of the loop. Anyway, we've been getting weird results
>>> from time and its family lately (like CPU time longer than Wall time: is
>>> that ok?). This is tested on versions 4.6 and 4.4, on different
>>> architectures.
>>>
>>> Regards
>>>
>>> Version 1
>>>
>>> tri=pen=hex=dt=dp=dh=1
>>> results=[]
>>> cota = 3
>>> while len(results)<cota:
>>> if tri==pen==hex:
>>> results.append(tri)
>>> if tri<=pen and tri<=hex:
>>> dt+=1
>>> tri+=dt
>>> elif pen<=hex:
>>> dp+=3;
>>> pen+=dp
>>> else:
>>> dh+=4;
>>> hex+=dh
>>> print results
>>>
>>>
>>> Version 2
>>>
>>> cota = 3
>>> tri=pen=hex=dt=dp=dh=1
>>> results=[]
>>> n=0
>>> while n<cota:
>>> if tri==pen==hex:
>>> results.append(tri)
>>> n+=1
>>> if tri<=pen and tri<=hex:
>>> dt+=1
>>> tri+=dt
>>> elif pen<=hex:
>>> dp+=3;
>>> pen+=dp
>>> else:
>>> dh+=4;
>>> hex+=dh
>>> print results
>>>
>>> --
>>> To post to this group, send an email to sage-devel@googlegroups.com
>>> To unsubscribe from this group, send an email to
>>> sage-devel+unsubscr...@googlegroups.com
>>> For more options, visit this group at
>>> http://groups.google.com/group/sage-devel
>>> URL: http://www.sagemath.org
>>>
>>
>> --
>> To post to this group, send an email to sage-devel@googlegroups.com
>> To unsubscribe from this group, send an email to
>> sage-devel+unsubscr...@googlegroups.com
>> For more options, visit this group at
>> http://groups.google.com/group/sage-devel
>> URL: http://www.sagemath.org
>>
>
> --
> To post to this group, send an email to sage-devel@googlegroups.com
> To unsubscribe from this group, send an email to
> sage-devel+unsubscr...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
>
--
William Stein
Professor of Mathematics
University of Washington
http://wstein.org
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
