len() on mutables vs. immutables

[Terry Reedy]

On 2/7/2013 8:09 PM, Demian Brecht wrote:

> http://demianbrecht.github.com/posts/2013/02/07/understanding-len/

> 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?

The language specification specifies behavior, not resource usage. 
However, CPython's concrete collection classes all require knowing how 
many items they contain for their operation. And they 'know' that they 
must respond to len() inquiries (including for truth value) and for 
sequences, deal with index and slice operations. So you may assume that 
len() simply accesses a private internal attribute.

Keep in mind that 'immutables' have to be internally mutated to set 
their values, so from the interpreter viewpoint, there is little 
difference between mutable and immutable. The latter simply lack 
publicly accessible mutation methods.

--
Terry Jan Reedy