Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!1.eu.feeder.erje.net!lightspeed.eweka.nl!lightspeed.eweka.nl!newsfeed.xs4all.nl!newsfeed4a.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.050 X-Spam-Evidence: '*H*': 0.90; '*S*': 0.00; 'algorithm': 0.04; 'subject:Python': 0.06; 'element': 0.07; 'wrapped': 0.09; 'times,': 0.14; '>>': 0.16; 'efficiently,': 0.16; 'iteration': 0.16; 'removed,': 0.16; 'elements': 0.16; 'wrote:': 0.18; 'wed,': 0.18; 'to:name:python-list@python.org': 0.22; '>': 0.26; 'this:': 0.26; 'header:In-Reply-To:1': 0.27; 'wondering': 0.29; 'chris': 0.29; 'message-id:@mail.gmail.com': 0.30; 'moderate': 0.31; 'subject:numbers': 0.31; 'run': 0.32; 'received:74.125.82': 0.34; 'could': 0.34; 'but': 0.35; 'received:google.com': 0.35; 'there': 0.35; 'done': 0.36; 'should': 0.36; 'seconds': 0.37; 'too': 0.37; 'list': 0.37; 'performance': 0.37; 'expected': 0.38; 'to:addr:python-list': 0.38; 'skip:- 10': 0.38; 'pm,': 0.38; 'rather': 0.38; 'expect': 0.39; 'received:74.125': 0.39; 'delete': 0.39; 'to:addr:python.org': 0.39; 'deleting': 0.60; 'new': 0.61; 'took': 0.61; 'times': 0.62; 'such': 0.63; 'more': 0.64; 'situation': 0.65; 'overall': 0.69; '2015': 0.84; 'delete,': 0.84; 'hundred': 0.95 X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:content-type; bh=v1ALmUvH33BMOYNrfnWFrLiH+IRoips3x2CaaITECiY=; b=Jh1GVUhczCEEisjgZujsW9X4ICPIeHQsma/k2AH4u9KqfSgeXepSPKmLYBni9Y0aLg htu7xUhazIjiaEsa37Ug14umCAW8zZsIgG+ibt9Fm69wL/XzIUPgIDM/DBkfTB2ZEpGc QI63qnNjhg3hWTyxhPzv0aRaHN1cvOAy0H12RyerT0EoAB7dWRSnMug3hNO7ADhpb6GT JQtWBesSvMMIrSgH+nXVemP6vonzePx+hzbuLJv+Evs+XJ/hzw4cddBto9+qzg03nr51 o2IX+33QMrF7Q9lBuqHpTL88VC4IJEuhe04e4CIgT6J+/86AMU5MQFwiSKdHIx406oKk G9Rw== X-Gm-Message-State: ALoCoQkT4WuPW7hhqE/yl30sNlFV/rzuicBXeZnWG8sS+i7TIkbrgvgVHWf7k/ZZtehwNd6d7DCT X-Received: by 10.194.190.49 with SMTP id gn17mr2668192wjc.11.1430348204683; Wed, 29 Apr 2015 15:56:44 -0700 (PDT) MIME-Version: 1.0 In-Reply-To: <87d22mbod7.fsf@Equus.decebal.nl> References: <87lhhabxod.fsf@Equus.decebal.nl> <87d22mbod7.fsf@Equus.decebal.nl> From: Chris Kaynor Date: Wed, 29 Apr 2015 15:56:24 -0700 Subject: Re: Lucky numbers in Python To: "python-list@python.org" Content-Type: multipart/alternative; boundary=047d7bf0c1b4a54d510514e4e4bc X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.20+ Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 88 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1430348212 news.xs4all.nl 2948 [2001:888:2000:d::a6]:44220 X-Complaints-To: abuse@xs4all.nl X-Received-Bytes: 7466 X-Received-Body-CRC: 3523360318 Xref: csiph.com comp.lang.python:89585 --047d7bf0c1b4a54d510514e4e4bc Content-Type: text/plain; charset=UTF-8 On Wed, Apr 29, 2015 at 2:45 PM, Cecil Westerhof 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 --047d7bf0c1b4a54d510514e4e4bc Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
On W= ed, Apr 29, 2015 at 2:45 PM, Cecil Westerhof <Cecil@decebal.nl> wrote:
>> I wa= s 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 expec= t
such a big difference: more as hundred times. The old situation took
20 seconds for 1000000. The new takes 0.17.

Its not t= oo surprising, as deleting the non-end element of a list is a O(n) operatio= n - it must copy all elements in the list into a new list each time. This m= eans 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 wrapp= ed in a while loop which will run log(n) times (I think that while loop wil= l run log(n) times, but have not actually tested the math).

Deleting a slice shou= ld take n time as well, however it is now done only once rather than once p= er 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
--047d7bf0c1b4a54d510514e4e4bc--