Why is my code faster with append() in a loop than with a large list?

Dave Angel davea at ieee.org
Mon Jul 6 20:28:05 CEST 2009


MRAB wrote:
> <div class="moz-text-flowed" style="font-family: -moz-fixed">Dave 
> Angel wrote:
>> MRAB wrote:
>>> <div class="moz-text-flowed" style="font-family: -moz-fixed">Dave 
>>> Angel wrote:
>>> [snip]
>>>> It would probably save some time to not bother storing the zeroes 
>>>> in the list at all.  And it should help if you were to step through 
>>>> a list of primes, rather than trying every possible int.  Or at 
>>>> least constrain yourself to odd numbers (after the initial case of 2).
>>>>
>>> Or stop looking for more factors when you've passed the square root of
>>> num. I don't know what effect there'll be on the time if you 
>>> recalculate
>>> the square root when num changes (expensive calculation vs smaller
>>> search space).
>>>
>>> </div>
>>>
>> But if I remember the code, it stopped when the quotient is one, 
>> which is usually sooner than the square root.  And no need to 
>> precalculate the square root.
>>
> If the number is a large prime then the code will try all the numbers up
> to that, eg if num == 1000003 then it'll try 2..1000003 even though it
> could've given up after 1000.
>
> </div>
>
That's one reason I suggested (and Piet implemented) a sieve.  You can 
stop dividing when the square of the next prime exceeds your quotient.




More information about the Python-list mailing list