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>
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

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