Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!goblin3!goblin2!goblin.stu.neva.ru!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!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.010 X-Spam-Evidence: '*H*': 0.98; '*S*': 0.00; 'subject:Python': 0.05; 'behave': 0.07; 'python': 0.08; 'append': 0.09; 'def': 0.13; 'algorithm': 0.13; '"""returns': 0.16; 'reallocate': 0.16; 'received:192.168.1.104': 0.16; 'res': 0.16; 'cc:addr:python- list': 0.16; 'subject:question': 0.16; 'wrote:': 0.18; 'thanks,': 0.19; 'java': 0.21; 'cc:no real name:2**0': 0.21; 'header:In- Reply-To:1': 0.22; 'knowing': 0.23; 'sfxlen:0': 0.23; 'smallest': 0.23; 'expect': 0.25; 'cc:2**0': 0.26; 'mainly': 0.28; 'lists': 0.28; '(see': 0.28; "i'm": 0.28; 'cc:addr:python.org': 0.29; 'pm,': 0.29; 'array': 0.30; 'list': 0.32; 'header:User-Agent:1': 0.33; 'instead': 0.33; 'realize': 0.34; 'calling': 0.34; 'however,': 0.35; 'expanding': 0.35; 'subject:lists': 0.36; 'received:192': 0.38; 'doing': 0.38; 'received:192.168.1': 0.39; 'huge': 0.61; 'more': 0.61; 'your': 0.61; 'below': 0.62; 'header :Reply-To:1': 0.70; 'reply-to:no real name:2**0': 0.72; 'biggest': 0.74; 'trial': 0.76; 'inefficient': 0.91 Date: Wed, 15 Feb 2012 13:45:33 -0500 From: Dave Angel User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.24) Gecko/20111109 Thunderbird/3.1.16 MIME-Version: 1.0 To: Franck Ditter Subject: Re: Complexity question on Python 3 lists References: In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Provags-ID: V02:K0:OJZXiETaSvElOFyC3sGzYJukm8tK5WSnultpjO9DDdw 7Ka6HCgsIIZRnyIiTYottl88XSDqtna6dQEecH6fwoTmdUkA5U h4g4M0HPZWf9IXa+cwm7MQ5bfWSd3LufkceKJ8nlMlmx4kwNvZ pGJtZfaEFRz5P6uzhXgkYK/ZU2lhqyCr0/3vS93RaG5r0ezgoo WorAb7IAn3sK9NvSpYViwMwW8P3GcYwAXyQRr4SBNCw833UqJZ e0OfLZayyZ4+Iv6MwzQkpYa0Pof8WIikkgwXfNjxqQ9Ygl209y pgmGUA4P5IpyeARWhN8JlmXkOM4zb8H2zZONhO+YrtAcUblxQ= = Cc: python-list@python.org X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.12 Precedence: list Reply-To: d@davea.name 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: 42 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1329331566 news.xs4all.nl 6919 [2001:888:2000:d::a6]:59091 X-Complaints-To: abuse@xs4all.nl Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:20461 On 02/15/2012 01:20 PM, Franck Ditter wrote: > What is the cost of calling primes(n) below ? I'm mainly interested in > knowing if the call to append is O(1), even amortized. > Do lists in Python 3 behave like ArrayList in Java (if the capacity > is full, then the array grows by more than 1 element) ? > > def sdiv(n) : # n>= 2 > """returns the smallest (prime) divisor of n""" > if n % 2 == 0 : return 2 > for d in range(3,int(sqrt(n))+1,2) : > if n % d == 0 : return d > return n > > def isPrime(n) : > """Returns True iff n is prime""" > return n>= 2 and n == sdiv(n) > > def primes(n) : # n>= 2 > """Returns the list of primes in [2,n]""" > res = [] > for k in range(2,n+1) : > if isPrime(k) : res.append(k) # cost O(1) ? > return res > > Thanks, > > franck Yes, lists behave the way you'd expect (see vector in C++), where when they have to reallocate they do so exponentially. However, realize that your algorithm is inefficient by a huge factor more than any time spent expanding lists. The biggest single thing you need to do is to memoize -- store the list of known primes, and add to it as you encounter more. Then use that list instead of range(3, xxx, 2) for doing the trial divisions. -- DaveA