len() on mutables vs. immutables
Terry Reedy
tjreedy at udel.edu
Thu Feb 7 23:30:41 EST 2013
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
More information about the Python-list
mailing list