Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!eternal-september.org!feeder.eternal-september.org!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: <nick.cash@npcinternational.com>
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; 'explicitly': 0.04; 'cache': 0.05; 'cpython': 0.05; 'python': 0.09; "(i'd": 0.09; 'behavior,': 0.09; 'immutable': 0.09; 'internally': 0.09; 'mutable': 0.09; 'similar,': 0.09; 'assume': 0.11; 'passing': 0.15; 'source,': 0.15; '(well,': 0.16; 'anyway).': 0.16; 'call?': 0.16; 'dig': 0.16; 'url:moin': 0.17; 'saying': 0.18; 'appears': 0.18; 'to:name:python-list@python.org': 0.20; 'operations.': 0.22; "i'd": 0.22; 'to:2**1': 0.23; "i've": 0.23; 'received:169.254': 0.24; 'least': 0.25; 'header:In-Reply-To:1': 0.25; 'url:wiki': 0.26; 'done.': 0.27; 'implemented': 0.27; '(such': 0.27; 'received:216.32': 0.27; 'arrays': 0.29; 'overhead': 0.29; 'received:169': 0.29; "i'm": 0.29; 'function': 0.30; 'header:Received:8': 0.30; 'lists': 0.31; 'point': 0.31; 'url:python': 0.32; 'curious': 0.33; 'received:10.43': 0.33; 'to:addr:python-list': 0.33; 'list': 0.35; 'built-in': 0.35; 'lists.': 0.35; 'received:bigfish.com': 0.35; 'so,': 0.35; 'doing': 0.35; 'there': 0.35; 'url:org': 0.36; 'anything': 0.36; 'charset:us-ascii': 0.36; 'rather': 0.37; 'subject:: ': 0.38; 'some': 0.38; 'received:10': 0.38; 'instead': 0.39; 'to:addr:python.org': 0.39; 'called': 0.39; 'side': 0.61; 'received:216': 0.62; 'safe': 0.63; 'worth': 0.63; 'subject:. ': 0.66; 'insight': 0.71; 'calculations': 0.84; 'complexity': 0.84; 'received:ch1ehsmhs012.bigfish.com': 0.84
X-Forefront-Antispam-Report: CIP:157.56.240.117; KIP:(null); UIP:(null); IPV:NLI; H:BL2PRD0610HT005.namprd06.prod.outlook.com; RD:none; EFVD:NLI
X-SpamScore: -2
X-BigFish: PS-2(zz709fI1432Izz1202h1d1ah1d2ahzz17326ah8275dhz2fh2a8h668h839h944hd25hf0ah107ah1220h1288h12a5h12a9h12bdh137ah13b6h1441h1155h)
Received-SPF: pass (mail213-ch1: domain of npcinternational.com designates 157.56.240.117 as permitted sender) client-ip=157.56.240.117; envelope-from=nick.cash@npcinternational.com; helo=BL2PRD0610HT005.namprd06.prod.outlook.com ; .outlook.com ;
From: Nick Cash <nick.cash@npcinternational.com>
To: Demian Brecht <demianbrecht@gmail.com>, "python-list@python.org" <python-list@python.org>
Subject: RE: len() on mutables vs. immutables
Thread-Topic: len() on mutables vs. immutables
Thread-Index: AQHNrVVr26ph0/czwEqTEzzJHg3qB5e/YKfg
Date: Thu, 18 Oct 2012 18:28:18 +0000
References: <50803B2C.6010900@gmail.com>
In-Reply-To: <50803B2C.6010900@gmail.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach: 
X-MS-TNEF-Correlator: 
x-originating-ip: [70.166.238.194]
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-OriginatorOrg: npcinternational.com
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <http://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <http://mail.python.org/pipermail/python-list/>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <http://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.2469.1350587629.27098.python-list@python.org>
Lines: 26
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1350587629 news.xs4all.nl 6873 [2001:888:2000:d::a6]:46146
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:31679

> I'm curious as to the implementation (I'd be happy to dig through the
> source, just don't have the time right now). I've seen various
> implementations across interpreters in the past (some which have been
> rather shocking) and I'd like to get some insight into Python (well,
> CPython at this point anyway).
>=20
> 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?
>=20
> 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?

It appears that list has len() complexity of O(1)
source: http://wiki.python.org/moin/TimeComplexity
It may be worth mentioning that lists in Python are implemented using array=
s instead of linked lists.

It's reasonable to assume that other built-in collection types would be sim=
ilar, though I don't see anything explicitly saying so for bytearray.

-Nick Cash