confused about resizing array in Python

Discussion in 'Python' started by Ruan, Feb 3, 2007.

  1. Ruan

    Ruan Guest

    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?
     
    Ruan, Feb 3, 2007
    #1
    1. Advertising

  2. 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
     
    Roel Schroeven, Feb 3, 2007
    #2
    1. Advertising

  3. Ruan

    Ruan Guest

    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" <> wrote in message
    news:8I5xh.324951$-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
     
    Ruan, Feb 3, 2007
    #3
  4. Ruan

    John Machin Guest

    On Feb 4, 7:41 am, "Ruan" <> 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
     
    John Machin, Feb 3, 2007
    #4
  5. Ruan schreef:
    > "Roel Schroeven" <> 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
     
    Roel Schroeven, Feb 3, 2007
    #5
  6. 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" <> wrote in message
    news:vc8xh.325172$-ops.be...
    > Ruan schreef:
    >> "Roel Schroeven" <> 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
     
    Dongsheng Ruan, Feb 3, 2007
    #6
  7. Dongsheng Ruan schreef:
    > "Roel Schroeven" <> wrote in message
    > news:vc8xh.325172$-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
     
    Roel Schroeven, Feb 4, 2007
    #7
  8. 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" <> wrote in message
    news:qx9xh.325276$-ops.be...
    > Dongsheng Ruan schreef:
    >> "Roel Schroeven" <> wrote in message
    >> news:vc8xh.325172$-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
     
    Dongsheng Ruan, Feb 4, 2007
    #8
  9. In <eq39n7$2b9g$>, 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
     
    Marc 'BlackJack' Rintsch, Feb 4, 2007
    #9
  10. Ruan

    Neil Cerutti Guest

    On 2007-02-04, Marc 'BlackJack' Rintsch <> 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
     
    Neil Cerutti, Feb 5, 2007
    #10
  11. En Sat, 03 Feb 2007 21:34:19 -0300, Dongsheng Ruan <>
    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
     
    Gabriel Genellina, Feb 5, 2007
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. someone else

    resizing an array, is there a better way?

    someone else, Aug 1, 2004, in forum: C Programming
    Replies:
    29
    Views:
    750
    Malcolm
    Aug 9, 2004
  2. gga
    Replies:
    6
    Views:
    150
    Stefan Lang
    Feb 17, 2005
  3. Victor Shepelev

    Array resizing

    Victor Shepelev, Mar 28, 2006, in forum: Ruby
    Replies:
    6
    Views:
    142
    Victor Shepelev
    Mar 28, 2006
  4. Pil (Trustworthy from Experience)

    Resizing a div by resizing its borders

    Pil (Trustworthy from Experience), Apr 18, 2009, in forum: Javascript
    Replies:
    9
    Views:
    370
    Proper
    Apr 21, 2009
  5. Proper
    Replies:
    0
    Views:
    211
    Proper
    Apr 18, 2009
Loading...

Share This Page