Groups > comp.lang.python > #20464

Re: Complexity question on Python 3 lists

Path	csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!news.stack.nl!newsfeed.xs4all.nl!newsfeed5.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Return-Path	<python-python-list@m.gmane.org>
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; 'cpython': 0.05; 'subject:Python': 0.05; 'behave': 0.07; 'python': 0.08; 'append': 0.09; 'received:80.91': 0.09; 'received:80.91.229': 0.09; 'received:gmane.org': 0.09; 'received:list': 0.09; 'am,': 0.12; 'case.': 0.15; 'from:addr:behnel.de': 0.16; 'from:addr:stefan_ml': 0.16; 'from:name:stefan behnel': 0.16; 'limit.': 0.16; 'subject:question': 0.16; 'wed,': 0.17; 'wrote:': 0.18; 'java': 0.21; 'memory': 0.21; 'header:In-Reply-To:1': 0.22; '(or': 0.22; 'feb': 0.22; 'stefan': 0.24; 'otherwise,': 0.25; 'lists': 0.28; "i'm": 0.28; 'constant': 0.29; 'array': 0.30; 'that,': 0.32; 'list': 0.32; 'header:User-Agent:1': 0.33; 'header:X-Complaints- To:1': 0.34; 'received:84': 0.34; 'certain': 0.34; 'to:addr :python-list': 0.35; 'subject:lists': 0.36; 'received:org': 0.36; 'bound': 0.37; 'but': 0.37; 'uses': 0.38; 'to:addr:python.org': 0.40; 'more': 0.61; 'your': 0.61; 'believe': 0.65; 'absolutely.': 0.84; 'certain,': 0.84; 'steps.': 0.93
X-Injected-Via-Gmane	http://gmane.org/
To	python-list@python.org
From	Stefan Behnel <stefan_ml@behnel.de>
Subject	Re: Complexity question on Python 3 lists
Date	Wed, 15 Feb 2012 20:01:07 +0100
References	<franck-B0D585.19202115022012@news.free.fr> <CALwzidmOuA7hWxEN+Zoy5oKmf1j7-Lc-xxPrEXmXqdnsx_DnVw@mail.gmail.com>
Mime-Version	1.0
Content-Type	text/plain; charset=UTF-8
Content-Transfer-Encoding	7bit
X-Gmane-NNTP-Posting-Host	dslb-084-056-019-053.pools.arcor-ip.net
User-Agent	Mozilla/5.0 (X11; Linux x86_64; rv:10.0) Gecko/20120129 Thunderbird/10.0
In-Reply-To	<CALwzidmOuA7hWxEN+Zoy5oKmf1j7-Lc-xxPrEXmXqdnsx_DnVw@mail.gmail.com>
X-BeenThere	python-list@python.org
X-Mailman-Version	2.1.12
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.5846.1329332480.27778.python-list@python.org> (permalink)
Lines	20
NNTP-Posting-Host	2001:888:2000:d::a6
X-Trace	1329332480 news.xs4all.nl 6941 [2001:888:2000:d::a6]:52027
X-Complaints-To	abuse@xs4all.nl
Xref	x330-a1.tempe.blueboxinc.net comp.lang.python:20464

Show key headers only | View raw

Ian Kelly, 15.02.2012 19:43:
> On Wed, Feb 15, 2012 at 11:20 AM, Franck Ditter wrote:
>> Do lists in Python 3 behave like ArrayList in Java (if the capacity
>> is full, then the array grows by more than 1 element) ?
> 
> I believe the behavior in CPython is that if the array is full, the
> capacity is doubled

But only up to a certain limit. After that, it grows in constant steps.
Otherwise, your memory would be bound to explode on an append even though
your list uses only half of it (or one third, in case it needs to copy).

>, but I'm not certain, and that would be an
> implementation detail in any case.

Absolutely.

Stefan

Thread

Complexity question on Python 3 lists Franck Ditter <franck@ditter.org> - 2012-02-15 19:20 +0100
  Re: Complexity question on Python 3 lists Chris Rebert <clp2@rebertia.com> - 2012-02-15 10:35 -0800
  Re: Complexity question on Python 3 lists Ian Kelly <ian.g.kelly@gmail.com> - 2012-02-15 11:43 -0700
  Re: Complexity question on Python 3 lists Dave Angel <d@davea.name> - 2012-02-15 13:45 -0500
  Re: Complexity question on Python 3 lists Stefan Behnel <stefan_ml@behnel.de> - 2012-02-15 20:01 +0100
  Re: Complexity question on Python 3 lists Chris Rebert <clp2@rebertia.com> - 2012-02-15 11:11 -0800
  Re: Complexity question on Python 3 lists Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2012-02-15 15:28 -0500
  Re: Complexity question on Python 3 lists Terry Reedy <tjreedy@udel.edu> - 2012-02-15 16:41 -0500
  Re: Complexity question on Python 3 lists Ian Kelly <ian.g.kelly@gmail.com> - 2012-02-15 15:54 -0700
  Re: Complexity question on Python 3 lists Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-02-16 00:41 +0000

csiph-web