len() on mutables vs. immutables
nick.cash at npcinternational.com
Thu Oct 18 20:28:18 CEST 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)
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.
More information about the Python-list