Re: len() on mutables vs. immutables

Path	csiph.com!usenet.pasdenom.info!weretis.net!feeder1.news.weretis.net!feeder.erje.net!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Return-Path	<demianbrecht@gmail.com>
X-Original-To	python-list@python.org
Delivered-To	python-list@mail.python.org
X-Spam-Status	OK 0.011
X-Spam-Evidence	'H': 0.98; 'S': 0.00; 'explicitly': 0.04; 'python': 0.09; 'before.': 0.09; 'similar,': 0.09; 'cc:addr :python-list': 0.10; 'assume': 0.11; 'nick': 0.16; 'wrote:': 0.17; 'url:moin': 0.17; 'saying': 0.18; 'appears': 0.18; 'cc:2**0': 0.23; 'cc:addr:python.org': 0.25; 'header:In-Reply-To:1': 0.25; 'header:User-Agent:1': 0.26; 'url:wiki': 0.26; 'am,': 0.27; 'implemented': 0.27; 'arrays': 0.29; 'link,': 0.29; 'lists': 0.31; 'url:python': 0.32; 'received:google.com': 0.34; 'thanks': 0.34; 'list': 0.35; 'built-in': 0.35; 'lists.': 0.35; 'received:209.85.220': 0.35; 'received:209.85': 0.35; 'message- id:@gmail.com': 0.36; 'url:org': 0.36; 'anything': 0.36; 'received:209': 0.37; 'subject:: ': 0.38; 'instead': 0.39; 'header:Received:5': 0.40; 'worth': 0.63; 'subject:. ': 0.66; 'believe': 0.69; 'complexity': 0.84
DKIM-Signature	v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=message-id:date:from:user-agent:mime-version:to:cc:subject :references:in-reply-to:content-type:content-transfer-encoding; bh=Q5VBNCPPyiYriixD7POAUN/xq5F3enVz6VKRSA+LvTw=; b=GBGX1X4YXsmO7QVlsRutvg5IhW6k2TVS/f3f+bIQq2HLk1QzGiHOM8DJgr7ElZ3BOE yXc+Z1iwiTrGd4IHFThfAC9dOYcRT3DD68oQxJ2VPWPPXZnu9nN1GXilj957OSua7QR3 2JjpRN9AhDeZW5i6zgCaQopwioial+PL2HGQDoDLPHVKleiSIvGcukid9ROW3iyR40vp I2ujQA7bB6M74cQSZ2CkGE6L5PKwvb+/brf6sf7Lz4wjI+IBY4ymGnh07vkKt9i34ZUy J1cwVB1nxUNNBUQIU+IgABbcy/gUX1+voNNMzTcCWq8BFnOn3czhOo4HszDasAGr92l0 5NEw==
Date	Thu, 18 Oct 2012 11:38:20 -0700
From	Demian Brecht <demianbrecht@gmail.com>
User-Agent	Mozilla/5.0 (Windows NT 6.1; WOW64; rv:16.0) Gecko/20121010 Thunderbird/16.0.1
MIME-Version	1.0
To	Nick Cash <nick.cash@npcinternational.com>
Subject	Re: len() on mutables vs. immutables
References	<50803B2C.6010900@gmail.com> <846C3A8E860C4344B567D813B63AA51D5A9C82FE@BL2PRD0610MB349.namprd06.prod.outlook.com>
In-Reply-To	<846C3A8E860C4344B567D813B63AA51D5A9C82FE@BL2PRD0610MB349.namprd06.prod.outlook.com>
Content-Type	text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding	7bit
Cc	"python-list@python.org" <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 <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.2461.1350585508.27098.python-list@python.org> (permalink)
Lines	12
NNTP-Posting-Host	2001:888:2000:d::a6
X-Trace	1350585509 news.xs4all.nl 6891 [2001:888:2000:d::a6]:49827
X-Complaints-To	abuse@xs4all.nl
Xref	csiph.com comp.lang.python:31672

Show key headers only | View raw

On 10/18/2012 11:28 AM, Nick Cash wrote:
> 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 arrays instead of linked lists.
>
> It's reasonable to assume that other built-in collection types would be similar, though I don't see anything explicitly saying so for bytearray.
>
> -Nick Cash

Thanks for the link, I don't believe I had seen that one before.

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

Thread

Re: len() on mutables vs. immutables Demian Brecht <demianbrecht@gmail.com> - 2012-10-18 11:38 -0700

csiph-web