Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder1.news.weretis.net!feeder.erje.net!eu.feeder.erje.net!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Return-Path: <ian.g.kelly@gmail.com>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.019
X-Spam-Evidence: '*H*': 0.96; '*S*': 0.00; 'method.': 0.05; 'subject:()': 0.09; 'times,': 0.13; "(i'm": 0.16; 'oct': 0.16; 'resize': 0.16; 'resized': 0.16; 'roy': 0.16; 'still,': 0.16; 'subject:array': 0.16; 'term.': 0.16; 'mon,': 0.16; 'wrote:': 0.17; 'copied': 0.17; 'odd': 0.17; 'assuming': 0.22; 'constant': 0.22; 'header:In-Reply-To:1': 0.25; 'instead.': 0.27; 'message- id:@mail.gmail.com': 0.27; "doesn't": 0.28; 'correct': 0.28; 'factor': 0.29; 'once.': 0.29; 'array': 0.29; "i'm": 0.29; 'maybe': 0.29; 'point': 0.31; 'to:addr:python-list': 0.33; 'received:google.com': 0.34; 'list': 0.35; 'doing': 0.35; 'pm,': 0.35; 'received:209.85': 0.35; 'there': 0.35; 'add': 0.36; 'really': 0.36; 'anything': 0.36; 'enough': 0.36; 'item': 0.37; 'received:209': 0.37; 'subject:: ': 0.38; 'sure': 0.38; 'to:addr:python.org': 0.39; 'list,': 0.39; 'skip:" 10': 0.40; 'header:Received:5': 0.40; 'think': 0.40; 'first': 0.61; 'provide': 0.62; 'times': 0.63; 'stuck': 0.65; 'smith': 0.71; 'to:name:python': 0.84; 'average': 0.93
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 :content-type; bh=c+m79loXz09qmnQDSZuGzD9WYhJY00c6QHKW1/7O6d8=; b=SB5JqWw0fElelnh6f5WgWwXeRGcVxg+ilNXtZuywOYVrVttT5/PTL8jKTTytF9u1LT BQpuic4mbOLn/tSgWua/36BGj7EP5L27BhrsnuW9AMDwqOL0IMAIMTPwtqNN2xVin9em WdZ2IIkJKJ8dSggZjEidRbc6zpyuaSCX6lZTcLA/EH5VJBfcvfPYrEmNI1aDWv8jDDWD P3EJDqkVZbzGtIhd6qRjKTNW15Xpo+u2jsDdnzOExrSi2KK9imq2tn9YxYhiS9iwhmjD +Ca5WybkijKVItRYySYs2YkVlH/3LJQhSREi0+Phtz5S5lY/dwFUBwD2dlK08Jh3wj9m 2sOQ==
MIME-Version: 1.0
In-Reply-To: <roy-4A06AD.19241029102012@news.panix.com>
References: <6998a955-7b34-4f4f-b8d6-62d1028f7561@googlegroups.com> <mailman.2986.1351482209.27098.python-list@python.org> <4c024364-84df-403b-8b9e-4a4c8f06121c@googlegroups.com> <mailman.2991.1351484760.27098.python-list@python.org> <cd108b9d-e951-463e-8e50-a5a024a27c7f@googlegroups.com> <508e6649$0$29967$c3e8da3$5496439d@news.astraweb.com> <508E1BC9.3000308@r3dsolutions.com> <CALwzid=rhea2aMXM_St2FwTiAx+cnZ20_H6RtwW0_81uSQAFBQ@mail.gmail.com> <508EA3EF.5080504@r3dsolutions.com> <mailman.3056.1351552107.27098.python-list@python.org> <roy-4A06AD.19241029102012@news.panix.com>
From: Ian Kelly <ian.g.kelly@gmail.com>
Date: Mon, 29 Oct 2012 17:43:03 -0600
Subject: Re: Negative array indicies and slice()
To: Python <python-list@python.org>
Content-Type: text/plain; charset=ISO-8859-1
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.3057.1351554215.27098.python-list@python.org>
Lines: 20
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1351554215 news.xs4all.nl 6866 [2001:888:2000:d::a6]:34363
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:32443

On Mon, Oct 29, 2012 at 5:24 PM, Roy Smith <roy@panix.com> wrote:
> I think you're missing the point of "amortized constant time".  Yes, the
> first item appended to the list will be copied lg(20,000,000) ~= 25
> times, because the list will be resized that many times(*).  But, on
> average (I'm not sure if "average" is strictly the correct word here),
> each item will be copied only once.
>
> Still, it always stuck me as odd that there's no preallocate() method.
> There are times when you really do know how many items you're going to
> add to the list, and doing a single allocation would be a win.  And it
> doesn't cost anything to provide it.  I suppose, however, if you're
> adding enough items that preallocating would really matter, then maybe
> you want an array instead.
>
> (*) I don't know the exact implementation; I'm assuming each resize is a
> factor of 2.

The growth factor is approximately 1.125.  "Approximately" because
there is also a small constant term.  The average number of copies per
item converges on 8.