Path: csiph.com!usenet.pasdenom.info!news.albasani.net!newsfeed.freenet.ag!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.001 X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'interpreter': 0.04; 'cache': 0.05; 'attribute.': 0.09; 'behavior,': 0.09; 'immutable': 0.09; 'internally': 0.09; 'mutable': 0.09; 'terry': 0.09; 'url:github': 0.09; 'cc:addr:python-list': 0.10; 'assume': 0.11; 'index': 0.13; 'language': 0.14; 'passing': 0.15; 'accesses': 0.16; 'call?': 0.16; 'mutated': 0.16; 'operation.': 0.16; 'received:206.46': 0.16; 'received:206.46.173': 0.16; 'reedy': 0.16; 'wrote:': 0.17; 'specifies': 0.17; 'jan': 0.18; 'latter': 0.22; 'operations.': 0.22; 'url:02': 0.22; "i'd": 0.22; 'cc:2**0': 0.23; 'cc:no real name:2**0': 0.24; 'least': 0.25; 'cc:addr:python.org': 0.25; 'header:User-Agent:1': 0.26; 'done.': 0.27; '(such': 0.27; 'methods.': 0.29; 'overhead': 0.29; 'publicly': 0.29; 'received:192.168.1.3': 0.29; 'value)': 0.29; '(including': 0.30; 'classes': 0.30; 'function': 0.30; 'accessible': 0.33; 'built-in': 0.35; 'so,': 0.35; 'doing': 0.35; 'pm,': 0.35; 'there': 0.35; 'subject:: ': 0.38; 'some': 0.38; 'received:192': 0.39; 'called': 0.39; 'little': 0.39; 'received:192.168': 0.40; 'side': 0.61; 'between': 0.63; 'safe': 0.63; 'received:206': 0.65; 'subject:. ': 0.66; 'lack': 0.71; 'truth': 0.75; 'calculations': 0.84; 'url:2013': 0.84; 'url:posts': 0.84 Date: Thu, 07 Feb 2013 23:30:41 -0500 From: Terry Reedy User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:17.0) Gecko/17.0 Thunderbird/17.0 MIME-version: 1.0 To: Demian Brecht Subject: Re: len() on mutables vs. immutables References: In-reply-to: Content-type: text/plain; charset=UTF-8; format=flowed Content-transfer-encoding: 7bit Cc: python-list@python.org X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 29 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1360297894 news.xs4all.nl 6844 [2001:888:2000:d::a6]:43530 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:38399 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