<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Wed, Apr 29, 2015 at 2:45 PM, Cecil Westerhof <span dir="ltr"><<a href="mailto:Cecil@decebal.nl" target="_blank">Cecil@decebal.nl</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">>> I was wondering if there is a way to do this:<br>
>> for del_index in range((sieve_len // skip_count) * skip_count - 1,<br>
>> skip_count - 2, -skip_count):<br>
>> del sieve[del_index]<br>
>> in a more efficient way.<br>
><br>
</span><span class="">> You can delete using slices.<br>
><br>
> del sieve[(sieve_len // skip_count) * skip_count - 1 : skip_count -<br>
> 2 : -skip_count]<br>
><br>
> Now you no longer need to do the iteration in reverse, which makes<br>
> the slicing simpler:<br>
><br>
> del sieve[skip_count - 1 : (sieve_len // skip_count) * skip_count :<br>
> skip_count]<br>
<br>
</span>I expected that it could be done more efficiently, but did not expect<br>
such a big difference: more as hundred times. The old situation took<br>
20 seconds for 1000000. The new takes 0.17.</blockquote></div><br>Its not too surprising, as deleting the non-end element of a list is a O(n) operation - it must copy all elements in the list into a new list each time. This means that your algorithm is roughly O(n*n*log(n)) performance - n for each list delete, which is wrapped in a for loop of n iterations, which is wrapped in a while loop which will run log(n) times (I think that while loop will run log(n) times, but have not actually tested the math).</div><div class="gmail_extra"><br></div><div class="gmail_extra">Deleting a slice should take n time as well, however it is now done only once rather than once per item to be removed, which should reduce the overall algorithm to O(n*log(n)) time - aka, a HUGE difference with any moderate to large input.<br><br clear="all"><div><div class="gmail_signature">Chris</div></div>
</div></div>