Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #89585

Re: Lucky numbers in Python

Show key headers only | View raw

[Multipart message — attachments visible in raw view] - view raw

On Wed, Apr 29, 2015 at 2:45 PM, Cecil Westerhof <Cecil@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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Lucky numbers in Python Cecil Westerhof <Cecil@decebal.nl> - 2015-04-29 20:24 +0200
  Re: Lucky numbers in Python Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-29 13:57 -0600
    Re: Lucky numbers in Python Cecil Westerhof <Cecil@decebal.nl> - 2015-04-29 23:45 +0200
      Re: Lucky numbers in Python Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-29 16:38 -0600
        Re: Lucky numbers in Python Cecil Westerhof <Cecil@decebal.nl> - 2015-04-30 02:01 +0200
          Re: Lucky numbers in Python Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-29 20:55 -0600
            Re: Lucky numbers in Python Cecil Westerhof <Cecil@decebal.nl> - 2015-04-30 08:34 +0200
      Re: Lucky numbers in Python Chris Kaynor <ckaynor@zindagigames.com> - 2015-04-29 15:56 -0700
    Re: Lucky numbers in Python Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-30 10:11 +1000
      Re: Lucky numbers in Python Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-29 21:08 -0600
  Re: Lucky numbers in Python Cecil Westerhof <Cecil@decebal.nl> - 2015-04-30 20:55 +0200
    Re: Lucky numbers in Python Dave Angel <davea@davea.name> - 2015-04-30 15:28 -0400

csiph-web