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

Groups > comp.lang.python > #31702

Re: len() on mutables vs. immutables

Show key headers only | View raw

On 10/18/2012 3:18 PM, Prasad, Ramit wrote:
> 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?

It would only possibly be for lists, bytearrays, and, array module 
arrays.They are all over-allocated and need pointer to beginning, and 
either len or pointers to current end and allocated end. The current 
authoritative answer is in the current code itself.

-- 
Terry Jan Reedy

Back to comp.lang.python | Previous | Next | Find similar | Unroll thread

Thread

Re: len() on mutables vs. immutables Terry Reedy <tjreedy@udel.edu> - 2012-10-18 21:27 -0400

csiph-web