473,326 Members | 2,168 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,326 software developers and data experts.

confused about resizing array in Python

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.

Therefore, for "memo[n] = fib_memo(n-1) + fib_memo(n-2)", the time it taks
is not at all constant. The larger the n grows, the more time this statement
takes.

Can anybody here familiar with the internal mechanism of python confirm
this?
Feb 3 '07 #1
10 6720
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.

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

Roel Schroeven
Feb 3 '07 #2
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?

"Roel Schroeven" <rs****************@fastmail.fmwrote in message
news:8I**********************@phobos.telenet-ops.be...
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.

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

Roel Schroeven

Feb 3 '07 #3
On Feb 4, 7:41 am, "Ruan" <rds1...@sh163.netwrote:
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?
Qi ren you tian :-)

Llike with dictionaries, some spare space is left each time the list
is expanded, so over-all the amortised cost is O(n).

HTH,

John

Feb 3 '07 #4
Ruan schreef:
"Roel Schroeven" <rs****************@fastmail.fmwrote:
>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
Feb 3 '07 #5
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" <rs****************@fastmail.fmwrote in message
news:vc**********************@phobos.telenet-ops.be...
Ruan schreef:
>"Roel Schroeven" <rs****************@fastmail.fmwrote:
>>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

Feb 3 '07 #6
Dongsheng Ruan schreef:
"Roel Schroeven" <rs****************@fastmail.fmwrote in message
news:vc**********************@phobos.telenet-ops.be...
>Ruan schreef:
>>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 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?
I think so, more or less, but as I said I'm not entirely sure about how
Python handles lists.

One thing to keep in mind is that the list (like any other Python data
structure) doesn't store the objects themselves; it only stores
references to the objects. If the list needs to be copied, only the
references are copied; the objects themselves can stay where they are.
For small objects this doesn't make much difference, but if the objects
grow larger it gets much more efficient if you only have to move the
references around.

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

Roel Schroeven
Feb 4 '07 #7
This seems to be clever to use reference for list.

Is it unique to Python?

How about the traditional programming languages like C, Pascal or C++?

"Roel Schroeven" <rs****************@fastmail.fmwrote in message
news:qx**********************@phobos.telenet-ops.be...
Dongsheng Ruan schreef:
>"Roel Schroeven" <rs****************@fastmail.fmwrote in message
news:vc**********************@phobos.telenet-ops.be...
>>Ruan schreef:
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 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?

I think so, more or less, but as I said I'm not entirely sure about how
Python handles lists.

One thing to keep in mind is that the list (like any other Python data
structure) doesn't store the objects themselves; it only stores references
to the objects. If the list needs to be copied, only the references are
copied; the objects themselves can stay where they are. For small objects
this doesn't make much difference, but if the objects grow larger it gets
much more efficient if you only have to move the references around.

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

Roel Schroeven

Feb 4 '07 #8
In <eq***********@netnews.upenn.edu>, Dongsheng Ruan wrote:
This seems to be clever to use reference for list.

Is it unique to Python?
No of course not. Java is very similar in only passing references around
for objects. And `ArrayList` and `Vector` behave similar to Python lists.
How about the traditional programming languages like C, Pascal or C++?
For a start they don't have a built in list type. C and Pascal don't even
have one in the standard library. C++ has STL vectors and if you, the
programmer, decide to store pointers in it instead of structures or
objects then you have something like Python's list type.

Ciao,
Marc 'BlackJack' Rintsch
Feb 4 '07 #9
On 2007-02-04, Marc 'BlackJack' Rintsch <bj****@gmx.netwrote:
>How about the traditional programming languages like C, Pascal
or C++?

For a start they don't have a built in list type. C and Pascal
don't even have one in the standard library. C++ has STL
vectors and if you, the programmer, decide to store pointers in
it instead of structures or objects then you have something
like Python's list type.
You need to store some form of smart pointer (rather than a bare
pointer) in C++ standard containers in order to avoid heart, head
and stomach aches. A reference counted pointer type will come
fairly close to Python semantics.

--
Neil Cerutti
Eddie Robinson is about one word: winning and losing. --Eddie Robinson's agent
Paul Collier
Feb 5 '07 #10
En Sat, 03 Feb 2007 21:34:19 -0300, Dongsheng Ruan <ru**@jcmills.com>
escribió:
This seems to be clever to use reference for list.

Is it unique to Python?

How about the traditional programming languages like C, Pascal or C++?
Python is written in C - so obviously it can be done in plain C.
Delphi (Pascal) has a similar thing; lists hold only a reference to the
object, and grow in discrete steps when needed.
And in C++ you have several container variants in the STL to choose from.
In all cases, there is a library behind, and a fairly good amount of code.
The good news is that it's already done for python: you get a lot of data
structures ready to use in Python.

--
Gabriel Genellina

Feb 6 '07 #11

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

4
by: Ruby Tuesday | last post by:
I have a section(185pixelsx 185pixels) in my web page to display an image that is stored in a directory. Using php, how do you resize so if: the image dimension is smaller(width and height is...
5
by: Haoyu Zhang | last post by:
Dear Friends, Python assignment is a reference assignment. However, I really can't explain the difference in the following example. When the object is a list, the assignment seems to be a...
45
by: Edward K. Ream | last post by:
Hello all, First of all, my present state of mind re pep 318 is one of sheepish confusion. I suspect pep 318 will not affect Leo significantly, but I am most surprised that an apparently...
2
by: Iyer, Prasad C | last post by:
Actually I am bit confused between the modules and .py file How do I differentiate between the 2. For example I have a file import1.py, import2.py file Which has few functions and classes And...
7
by: Kjell | last post by:
H I'm a former VB programmer and I have a issue with Arrays in C If I can't tell the size in advance how can I solve the issue since C# does not suppor resizing arrays like VB do (i.e. Redim...
4
by: John A Grandy | last post by:
As there is no ReDim in C# , what is the preferred technique for dynmically increasing the size of any array ? Does the answer depend on whether the array holds primitives versus instances of...
1
by: Nick ! | last post by:
Chris Share <usenet at caesium.me.ukwrote: http://web.cs.mun.ca/~rod/ncurses/ncurses.html#xterm says "The ncurses library does not catch signal, because it cannot in general know how you want...
9
by: dli07 | last post by:
Hello, I'm trying to convert a piece of code that creates a dynamic vertical resizing bar in a table from internet explorer to firefox. It's based on a post from...
8
by: brahmaforces | last post by:
Hi Folks, I am using cherrypy and python. I am trying to get a user profile image to resize on the client side before uploading to the server. PHP has a gd library that does it it seems. Has...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.