RE: len() on mutables vs. immutables

Discussion in 'Python' started by Nick Cash, Oct 18, 2012.

  1. Nick Cash

    Nick Cash Guest

    > I'm curious as to the implementation (I'd be happy to dig through the
    > source, just don't have the time right now). I've seen various
    > implementations across interpreters in the past (some which have been
    > rather shocking) and I'd like to get some insight into Python (well,
    > CPython at this point anyway).
    >
    > When len() is called passing an immutable built-in type (such as a
    > string), I'd assume that the overhead in doing so is simply a function
    > call and there are no on-call calculations done. Is that correct?
    >
    > I'd also assume that mutable built-in types (such as a bytearray) would
    > cache their size internally as a side effect of mutation operations. Is
    > that correct? If so, is it safe to assume that at least all built-in
    > types observe this behavior, or are there some that incur an O(n) cost
    > on every len() call?


    It appears that list has len() complexity of O(1)
    source: http://wiki.python.org/moin/TimeComplexity
    It may be worth mentioning that lists in Python are implemented using arrays instead of linked lists.

    It's reasonable to assume that other built-in collection types would be similar, though I don't see anything explicitly saying so for bytearray.

    -Nick Cash
    Nick Cash, Oct 18, 2012
    #1
    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. Demian Brecht

    len() on mutables vs. immutables

    Demian Brecht, Oct 18, 2012, in forum: Python
    Replies:
    0
    Views:
    96
    Demian Brecht
    Oct 18, 2012
  2. Terry Reedy

    Re: len() on mutables vs. immutables

    Terry Reedy, Oct 18, 2012, in forum: Python
    Replies:
    0
    Views:
    108
    Terry Reedy
    Oct 18, 2012
  3. Demian Brecht

    Re: len() on mutables vs. immutables

    Demian Brecht, Oct 18, 2012, in forum: Python
    Replies:
    0
    Views:
    119
    Demian Brecht
    Oct 18, 2012
  4. Demian Brecht

    Re: len() on mutables vs. immutables

    Demian Brecht, Oct 18, 2012, in forum: Python
    Replies:
    0
    Views:
    111
    Demian Brecht
    Oct 18, 2012
  5. Prasad, Ramit

    RE: len() on mutables vs. immutables

    Prasad, Ramit, Oct 18, 2012, in forum: Python
    Replies:
    0
    Views:
    110
    Prasad, Ramit
    Oct 18, 2012
Loading...

Share This Page