On Wed, Apr 29, 2015 at 2:45 PM, Cecil Westerhof <ce...@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
-- https://mail.python.org/mailman/listinfo/python-list
