Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > RE: len() on mutables vs. immutables

Reply
Thread Tools

RE: len() on mutables vs. immutables

 
 
Nick Cash
Guest
Posts: n/a
 
      10-18-2012
> 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

 
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
RE: len() on mutables vs. immutables Prasad, Ramit Python 0 10-18-2012 07:18 PM
Re: len() on mutables vs. immutables Demian Brecht Python 0 10-18-2012 06:42 PM
Re: len() on mutables vs. immutables Demian Brecht Python 0 10-18-2012 06:38 PM
Re: len() on mutables vs. immutables Terry Reedy Python 0 10-18-2012 06:29 PM
len() on mutables vs. immutables Demian Brecht Python 0 10-18-2012 05:23 PM



Advertisments