Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > confused about resizing array in Python

Reply
Thread Tools

confused about resizing array in Python

 
 
Ruan
Guest
Posts: n/a
 
      02-03-2007
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?


 
Reply With Quote
 
 
 
 
Roel Schroeven
Guest
Posts: n/a
 
      02-03-2007
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
 
Reply With Quote
 
 
 
 
Ruan
Guest
Posts: n/a
 
      02-03-2007
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" <(E-Mail Removed)> wrote in message
news:8I5xh.324951$(E-Mail Removed)-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



 
Reply With Quote
 
John Machin
Guest
Posts: n/a
 
      02-03-2007
On Feb 4, 7:41 am, "Ruan" <(E-Mail Removed)> wrote:
> 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





 
Reply With Quote
 
Roel Schroeven
Guest
Posts: n/a
 
      02-03-2007
Ruan schreef:
> "Roel Schroeven" <(E-Mail Removed)> 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
 
Reply With Quote
 
Dongsheng Ruan
Guest
Posts: n/a
 
      02-03-2007
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" <(E-Mail Removed)> wrote in message
news:vc8xh.325172$(E-Mail Removed)-ops.be...
> Ruan schreef:
>> "Roel Schroeven" <(E-Mail Removed)> 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



 
Reply With Quote
 
Roel Schroeven
Guest
Posts: n/a
 
      02-04-2007
Dongsheng Ruan schreef:
> "Roel Schroeven" <(E-Mail Removed)> wrote in message
> news:vc8xh.325172$(E-Mail Removed)-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
 
Reply With Quote
 
Dongsheng Ruan
Guest
Posts: n/a
 
      02-04-2007
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" <(E-Mail Removed)> wrote in message
news:qx9xh.325276$(E-Mail Removed)-ops.be...
> Dongsheng Ruan schreef:
>> "Roel Schroeven" <(E-Mail Removed)> wrote in message
>> news:vc8xh.325172$(E-Mail Removed)-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



 
Reply With Quote
 
Marc 'BlackJack' Rintsch
Guest
Posts: n/a
 
      02-04-2007
In <eq39n7$2b9g$(E-Mail Removed)>, 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
 
Reply With Quote
 
Neil Cerutti
Guest
Posts: n/a
 
      02-05-2007
On 2007-02-04, Marc 'BlackJack' Rintsch <(E-Mail Removed)> wrote:
>> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Resizing a div by resizing its borders Pil (Trustworthy from Experience) Javascript 9 04-21-2009 07:35 AM
Resizing a div by resizing its borders Proper Javascript 0 04-18-2009 08:02 PM
Array resizing Victor Shepelev Ruby 6 03-28-2006 01:56 PM
A little bit confused about array+array addition (bug or expected behavior?) gga Ruby 6 02-17-2005 02:03 PM
resizing an array, is there a better way? someone else C Programming 29 08-09-2004 07:42 PM



Advertisments