Lucky numbers in Python

[Chris Kaynor]

On Wed, Apr 29, 2015 at 2:45 PM, Cecil Westerhof <Cecil at decebal.nl> wrote:

> >> I was wondering if there is a way to do this:
> >> for del_index in range((sieve_len // skip_count) * skip_count - 1,
> >> skip_count - 2, -skip_count):
> >> del sieve[del_index]
> >> in a more efficient way.
> >
> > You can delete using slices.
> >
> > del sieve[(sieve_len // skip_count) * skip_count - 1 : skip_count -
> > 2 : -skip_count]
> >
> > Now you no longer need to do the iteration in reverse, which makes
> > the slicing simpler:
> >
> > del sieve[skip_count - 1 : (sieve_len // skip_count) * skip_count :
> > skip_count]
>
> I expected that it could be done more efficiently, but did not expect
> such a big difference: more as hundred times. The old situation took
> 20 seconds for 1000000. The new takes 0.17.


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).

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.

Chris
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20150429/66acf048/attachment.html>