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!newsgate.cistron.nl!newsgate.news.xs4all.nl!194.109.133.84.MISMATCH!newsfeed.xs4all.nl!newsfeed5.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.022
X-Spam-Evidence: '*H*': 0.96; '*S*': 0.00; 'append': 0.07; 'python': 0.09; 'subject:()': 0.09; 'amortized': 0.16; 'copied.': 0.16; 'oct': 0.16; 'reserves': 0.16; 'resized': 0.16; 'subject:array': 0.16; 'mon,': 0.16; 'wrote:': 0.17; 'copied': 0.17; 'pass': 0.25; 'header:In-Reply-To:1': 0.25; 'am,': 0.27; 'andrew': 0.27; 'message-id:@mail.gmail.com': 0.27; 'attempted': 0.29; 'once.': 0.29; 'point': 0.31; 'to:addr:python-list': 0.33; 'that,': 0.34; 'received:google.com': 0.34; 'list': 0.35; 'received:209.85': 0.35; 'list.': 0.35; 'but': 0.36; 'received:209': 0.37; 'subject:: ': 0.38; 'several': 0.39; 'to:addr:python.org': 0.39; 'space': 0.39; 'header:Received:5': 0.40; 'times': 0.63; 'more': 0.63; 'million': 0.72; 'complexity': 0.84; 'to:name:python': 0.84
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=U1lIrXBrPrLXHft6cInFU29h2snqxcDCL6IIDGRXXpo=; b=lXivdrMrpmPFtV2RGZOr9uuuZHOQHvMXWlpqfB73RhkBnFAF3hlMsqZf1yjPkQB46p tcsvCVDYdazHAx5pKbcwytkRCjx2IW+FG4f8w0xyDF2j2PcW8Ym58cguzeK7cRg4viy2 NL38tCWxZhGNvNL8TCP7IOmThXw1aKksPYIELOon4fEIlYIopqmsZaTnWPukSc0pwKxZ UX1c/p8XHTGtM3qmj5bKiMGLKFTfIwWnVmx69ruD4CgvhlMMqGKLRuhRUclk4Grtsuqk OPcf0P64qPWYVWBidf7XuxPvSHhGu6aWVWoHPNPMLJA9p5fxmATrrhvP8630JU5heXuq ae3w==
MIME-Version: 1.0
In-Reply-To: <508EA3EF.5080504@r3dsolutions.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>
From: Ian Kelly <ian.g.kelly@gmail.com>
Date: Mon, 29 Oct 2012 17:07:53 -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.3056.1351552107.27098.python-list@python.org>
Lines: 13
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1351552107 news.xs4all.nl 6967 [2001:888:2000:d::a6]:43037
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:32439

On Mon, Oct 29, 2012 at 9:42 AM, Andrew Robinson
<andrew3@r3dsolutions.com> wrote:
> The list was generated in a single pass by many .append() 's, and then
> copied once -- the original was left in place; and then I attempted to slice
> it.

Note that if the list was generated by .appends, then it was copied
more than once.  Python reserves a specific amount of space for the
list.  When it grows past that, the list must be reallocated and
copied.  It grows the list exponentially in order to keep the
amortized time complexity of append at O(1), but the point is that a
list of 20 million items is going to be resized and copied several
times before it is complete.