Complexity question on Python 3 lists

[Franck Ditter]

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

 

[Chris Rebert]

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

 

[Ian Kelly]

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

 

[Dave Angel]

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.

 

[Stefan Behnel]

Ian Kelly, 15.02.2012 19:43:

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

 

[Chris Rebert]

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

 

[Dennis Lee Bieber]

"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%...

 

[Terry Reedy]

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.

 

[Ian Kelly]

       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%.

 

[Steven D'Aprano]

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.