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

Groups > comp.lang.python > #20454 > unrolled thread

Complexity question on Python 3 lists

Back to article view | Back to comp.lang.python

Contents

  Complexity question on Python 3 lists Franck Ditter <franck@ditter.org> - 2012-02-15 19:20 +0100
    Re: Complexity question on Python 3 lists Chris Rebert <clp2@rebertia.com> - 2012-02-15 10:35 -0800
    Re: Complexity question on Python 3 lists Ian Kelly <ian.g.kelly@gmail.com> - 2012-02-15 11:43 -0700
    Re: Complexity question on Python 3 lists Dave Angel <d@davea.name> - 2012-02-15 13:45 -0500
    Re: Complexity question on Python 3 lists Stefan Behnel <stefan_ml@behnel.de> - 2012-02-15 20:01 +0100
    Re: Complexity question on Python 3 lists Chris Rebert <clp2@rebertia.com> - 2012-02-15 11:11 -0800
    Re: Complexity question on Python 3 lists Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2012-02-15 15:28 -0500
    Re: Complexity question on Python 3 lists Terry Reedy <tjreedy@udel.edu> - 2012-02-15 16:41 -0500
    Re: Complexity question on Python 3 lists Ian Kelly <ian.g.kelly@gmail.com> - 2012-02-15 15:54 -0700
    Re: Complexity question on Python 3 lists Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-02-16 00:41 +0000

#20454 — Complexity question on Python 3 lists

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

[toc] | [next] | [standalone]

#20457

On Wed, Feb 15, 2012 at 10:20 AM, Franck Ditter <franck@ditter.org> 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) ?

Yes. Python lists aren't linked lists. list.append() resizes the
underlying array intelligently to give O(1) performance, although I
can't find any guarantee of this in the docs, but it is true in
practice for all major Python implementations.

Cheers,
Chris

[toc] | [prev] | [next] | [standalone]

#20460

On Wed, Feb 15, 2012 at 11:20 AM, Franck Ditter <franck@ditter.org> 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.

Yes, it's amortized O(1).  See:

http://wiki.python.org/moin/TimeComplexity

>From a relatively shallow analysis, primes(n) appears to be O(n **
(3/2)), but it might be possible to tighten that up a bit with an
analysis of the distribution of primes and their smallest divisors.

> Do lists in Python 3 behave like ArrayList in Java (if the capacity
> is full, then the array grows by more than 1 element) ?

I believe the behavior in CPython is that if the array is full, the
capacity is doubled, but I'm not certain, and that would be an
implementation detail in any case.

Cheers,
Ian

[toc] | [prev] | [next] | [standalone]

#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

[toc] | [prev] | [next] | [standalone]

#20464

Ian Kelly, 15.02.2012 19:43:
> On Wed, Feb 15, 2012 at 11:20 AM, Franck Ditter wrote:
>> Do lists in Python 3 behave like ArrayList in Java (if the capacity
>> is full, then the array grows by more than 1 element) ?
> 
> I believe the behavior in CPython is that if the array is full, the
> capacity is doubled

But only up to a certain limit. After that, it grows in constant steps.
Otherwise, your memory would be bound to explode on an append even though
your list uses only half of it (or one third, in case it needs to copy).


>, but I'm not certain, and that would be an
> implementation detail in any case.

Absolutely.

Stefan

[toc] | [prev] | [next] | [standalone]

#20465

On Wed, Feb 15, 2012 at 10:43 AM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
> On Wed, Feb 15, 2012 at 11:20 AM, Franck Ditter <franck@ditter.org> wrote:
<snip>
>> Do lists in Python 3 behave like ArrayList in Java (if the capacity
>> is full, then the array grows by more than 1 element) ?
>
> I believe the behavior in CPython is that if the array is full, the
> capacity is doubled, but I'm not certain, and that would be an
> implementation detail in any case.

It's slightly more complex:
http://hg.python.org/cpython/file/096b31e0f8ea/Objects/listobject.c
"The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, …"
    -- list_resize()

Cheers,
Chris

[toc] | [prev] | [next] | [standalone]

#20469

On Wed, 15 Feb 2012 11:11:27 -0800, Chris Rebert <clp2@rebertia.com>
wrote:


>"The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, …"
>    -- list_resize()
>
	Rather perverse, is it not? The first set is plain doubling, but
then you get a series of increases by:

	... 9, 10, 11, 12, 14, 16, 16,...

or

	100%, 100%, 100%, 56%, 40%, 34%, 30%, 27%, 22%,...

	Big jump form 100% to 56%...
-- 
	Wulfraed                 Dennis Lee Bieber         AF6VN
        wlfraed@ix.netcom.com    HTTP://wlfraed.home.netcom.com/

[toc] | [prev] | [next] | [standalone]

#20479

On 2/15/2012 2:11 PM, Chris Rebert wrote:
>
> It's slightly more complex:
> http://hg.python.org/cpython/file/096b31e0f8ea/Objects/listobject.c
> "The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, …"
>      -- list_resize()

This has apparently changed from time to time.

-- 
Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]

#20485

On Wed, Feb 15, 2012 at 1:28 PM, Dennis Lee Bieber
<wlfraed@ix.netcom.com> wrote:
> On Wed, 15 Feb 2012 11:11:27 -0800, Chris Rebert <clp2@rebertia.com>
> wrote:
>
>
>>"The growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, …"
>>    -- list_resize()
>>
>        Rather perverse, is it not? The first set is plain doubling, but
> then you get a series of increases by:
>
>        ... 9, 10, 11, 12, 14, 16, 16,...
>
> or
>
>        100%, 100%, 100%, 56%, 40%, 34%, 30%, 27%, 22%,...
>
>        Big jump form 100% to 56%...

Based on the formula in the code, it would seem to asymptotically
approach 12.5%.

[toc] | [prev] | [next] | [standalone]

#20494

On Wed, 15 Feb 2012 19:20:21 +0100, 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)

Your primes() function appears to be a variation on trial division, which 
is asymptotically O(n*sqrt(n)/(log n)**2). Regardless of the exact Big Oh 
behaviour, it is going to be SLOW for large values of n.

The behaviour of append is the least of your concerns.



-- 
Steven

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web