Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #31679 > unrolled thread

RE: len() on mutables vs. immutables

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  RE: len() on mutables vs. immutables Nick Cash <nick.cash@npcinternational.com> - 2012-10-18 18:28 +0000

#31679 — RE: len() on mutables vs. immutables

> 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

[toc] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web