len() on mutables vs. immutables

[Prasad, Ramit]

Terry Reedy wrote:
> On 10/18/2012 1:23 PM, Demian Brecht wrote:
> 
> > 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?
> 
> See below.
> 
> > 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
> 
> Or the length could be the difference of two pointers -- address of the
> first empty slot minus address of first item.
> 
> > that correct? If so, is it safe to assume that at least all built-in
> > types observe this behavior,
> 
> str, bytes, bytearrays, arrays, sets, frozensets, dicts, dictviews, and
> ranges should all return len in O(1) time. That includes the possibility
> of a subtraction as indicated above.
> 

Why does pointer arithmetic work for dicts? I would think the position
of a value would be based on the hash of the key and thus "random" for
the context of this conversation.

Ramit Prasad


This email is confidential and subject to important disclaimers and
conditions including on offers for the purchase or sale of
securities, accuracy and completeness of information, viruses,
confidentiality, legal privilege, and legal entity disclaimers,
available at http://www.jpmorgan.com/pages/disclosures/email.