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

Groups > comp.lang.python > #89582

Re: Lucky numbers in Python

Show key headers only | View raw

Op Wednesday 29 Apr 2015 21:57 CEST schreef Ian Kelly:

> On Wed, Apr 29, 2015 at 12:24 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.

The code is know (I added a missing check):
    def lucky_numbers(n):
        if n < 3:
            return [1]
        sieve = range(1, n + 1, 2)
        sieve_index = 1
        while True:
            sieve_len   = len(sieve)
            if (sieve_index + 1) > sieve_len:
                break
            skip_count  = sieve[sieve_index]
            if sieve_len < skip_count:
                break
            del sieve[skip_count - 1 : (sieve_len // skip_count) * skip_count : skip_count]
            sieve_index += 1
        return sieve


> And although it's not clear to me what this is supposed to be doing,
> you probably no longer need the middle term if the intention is to
> continue deleting all the way to the end of the list (if it is then
> I think you have a bug in the existing implementation, since the
> last item in the list can never be deleted).

What do you mean by this? Executing:
    lucky_numbers(5)
gives:
    [1, 3]

So the last element (5) is deleted.

-- 
Cecil Westerhof
Senior Software Engineer
LinkedIn: http://www.linkedin.com/in/cecilwesterhof

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