Re: confused about resizing array in Python

You mentioned "it doubles in size".

Are you saying that a new double sized array is allocated and the contents
of the old list is copied there?

Then the old list is freed from memory?

It seems to be what is called amortized constant.

Say the list size is 100, before it is fully used, the append takes O(1)
time. But for the 101th element, the time will be O(100+1), and then from
then on, it is O(1) again. Like John Machin said in the previous post?

But on average, it is O(1). I guess this is the amortized constant. Isn't
it?

"Roel Schroeven" <rschroev_nospam_ml@xxxxxxxxxxx> wrote in message
news:vc8xh.325172$Au6.6345787@xxxxxxxxxxxxxxxxxxxxxxxx
Ruan schreef:
"Roel Schroeven" <rschroev_nospam_ml@xxxxxxxxxxx> wrote:
Ruan schreef:
My confusion comes from the following piece of code:

memo = {1:1, 2:1}
def fib_memo(n):
global memo
if not n in memo:
memo[n] = fib_memo(n-1) + fib_memo(n-2)
return memo[n]

I used to think that the time complexity for this code is O(n) due to
its use of memoization.

However, I was told recently that in Python, dictionary is a special
kind of array and to append new element to it or to resize it, it is in
fact
internally inplemented by creating another array and copying the old
one to
it and append a new one.

That's not correct. Python dictionaries are highly optimized and I
believe the time complexity is amortized constant (i.e. O(1)) for both
insertions and lookups.

Then how about Python's list?

What is done exactly when list.append is executed?

For list, is there another larger list initialized and the contents from
the
old list is copied to it together with the new appended list?

I'm not sure, but I think each time the list needs to grow, it doubles in
size. That leaves room to add a number of elements before the allocated
space needs to grow again. It's a frequently used approach, since it is
quite efficient and the memory needed is never double the amount of memory
strictly needed for the elements of the list.

You can always study the source code for all gory details of course.

--
If I have been able to see further, it was only because I stood
on the shoulders of giants. -- Isaac Newton

Roel Schroeven


.

Relevant Pages

  • Re: Append from array - Memofeld
    ... Versuchs mal mit SCATTER MEMO NAME bzw. GATHER MEMO NAME damit muestest du ... Ralf Alkenbrecher wrote: ... >a) mit APPEND FROM FileName ... >b) Umweg über ein ARRAY ...
    (microsoft.public.de.fox)
  • Re: confused about resizing array in Python
    ... memo = ... internally inplemented by creating another array and copying the old one to ... it and append a new one. ... Python dictionaries are highly optimized and I believe the time complexity is amortized constant ) for both insertions and lookups. ...
    (comp.lang.python)
  • confused about resizing array in Python
    ... memo = ... internally inplemented by creating another array and copying the old one to ... it and append a new one. ... Can anybody here familiar with the internal mechanism of python confirm ...
    (comp.lang.python)
  • PowerMean
    ... Demonstrate various ways of summarising/averaging a list of doubles ... @param numbers array of doubles ... double sum = 0; ...
    (comp.lang.java.help)
  • Re: indirect sort
    ... I wrote a Comparator and ... ... Is there a way to create a doublearray of my fields I want to sort by, sort that array and then recover the permutation? ... As i'm sure you've realised, you could write something of your own without too much trouble - just do a normal sort, but keep a side array of the objects, intitially set to the range from 0 to N-1, and every time you swap doubles, swap objects too. ...
    (comp.lang.java.programmer)