Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder1.news.weretis.net!feeder.erje.net!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!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.003 X-Spam-Evidence: '*H*': 0.99; '*S*': 0.00; 'indicated': 0.07; 'bytes,': 0.09; 'dict': 0.09; 'str,': 0.09; 'sure,': 0.09; 'cc:addr:python-list': 0.10; '(more': 0.16; 'arrays,': 0.16; 'awesome.': 0.16; 'bytearrays,': 0.16; 'declaration': 0.16; 'dig': 0.16; 'functions.)': 0.16; 'len': 0.16; 'oct': 0.16; 'subtraction': 0.16; 'wrote:': 0.17; 'pointer': 0.17; 'thu,': 0.17; 'cc:2**0': 0.23; '(you': 0.23; 'cc:no real name:2**0': 0.24; 'cc:addr:python.org': 0.25; 'header:In-Reply-To:1': 0.25; 'possibility': 0.27; '(e.g.,': 0.27; 'message-id:@mail.gmail.com': 0.27; 'source': 0.29; 'probably': 0.29; 'usually': 0.30; 'helpful': 0.30; 'received:google.com': 0.34; 'list': 0.35; 'pm,': 0.35; 'received:74.125': 0.36; 'method': 0.36; "i'll": 0.36; 'should': 0.36; 'subject:: ': 0.38; 'skip:o 20': 0.38; 'called': 0.39; 'header:Received:5': 0.40; 'most': 0.61; 'confirm': 0.64; 'subject:. ': 0.66; 'eyes': 0.69; 'ranges': 0.71; 'pytypeobject': 0.84; 'sets,': 0.84 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; bh=kmRoRbKSIGLQSEYAqJz1qeOKU3/aymGfKGXbCK+movY=; b=rqy8KFucZteekFfU7MeCaK9GoLQtO8vAp2s3EPmsb/TKVBxG0l8F0rmuSBf7GVCh60 BKukwHVkHFpm6gKo9vnHgRvPJf7dU+DnBDvLnWUhe+a1Z58GbdKXXQRvaSjJejeXXddX Sv2Ktg0vcoWjkfKuOJegX81YEZccLhsMSBwxYQDvwhV3pRAxOB5SB4EuF7T0oVqv3sm0 JS4DM/2ugwISzdHRVWZm6qU7EVh67xzz6DiW5Q83qpPvzTv+Lc6e4iUMB+Dftdm8f9Ad W/AA+Fc95y+FR1igtmB7tmjIxvO2WcUg6anMSe5yfv9yUNf7EpIYInohBzbmOn+6udFR EODw== MIME-Version: 1.0 In-Reply-To: <50804DA8.80708@gmail.com> References: <50803B2C.6010900@gmail.com> <50804DA8.80708@gmail.com> From: Daniel Urban Date: Thu, 18 Oct 2012 21:43:17 +0200 Subject: Re: len() on mutables vs. immutables To: Demian Brecht Content-Type: text/plain; charset=UTF-8 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: 17 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1350589418 news.xs4all.nl 6988 [2001:888:2000:d::a6]:41687 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:31682 On Thu, Oct 18, 2012 at 8:42 PM, Demian Brecht wrote: >> 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. > > Awesome. Pretty much what I figured. Of course, I'll have to dig around the > source just to confirm this with my own eyes (more just curiosity than > anything), so if you know whereabouts to look, it would be most helpful :) The source is usually in Objects/*object.c (e.g., the source for list is in Objects/listobject.c, dict is in dictobject.c and so on). The implementation of __len__ is usually in a method called whatever_length (e.g., dict.__len__ is called dict_length). To be sure, you can check the PyTypeObject declaration for the type. Probably the tp_as_sequence or tp_as_mapping field contains the pointer to __len__ (sq_length or mp_length respectively). (You can also search for "lenfunc", which is the type of such functions.)