Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #32443

Re: Negative array indicies and slice()

References (6 earlier) <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 2012-10-29 17:43 -0600
Subject Re: Negative array indicies and slice()
Newsgroups comp.lang.python
Message-ID <mailman.3057.1351554215.27098.python-list@python.org> (permalink)

Show all headers | View raw

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.

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

Thread

Negative array indicies and slice() andrewr3mail@gmail.com - 2012-10-28 20:12 -0700
  Re: Negative array indicies and slice() Ian Kelly <ian.g.kelly@gmail.com> - 2012-10-28 21:42 -0600
    Re: Negative array indicies and slice() andrewr3mail@gmail.com - 2012-10-28 21:00 -0700
      Re: Negative array indicies and slice() Ian Kelly <ian.g.kelly@gmail.com> - 2012-10-28 22:25 -0600
        Re: Negative array indicies and slice() Andrew <andrewr3mail@gmail.com> - 2012-10-29 00:54 -0700
          Re: Negative array indicies and slice() Chris Rebert <clp2@rebertia.com> - 2012-10-29 01:18 -0700
          Re: Negative array indicies and slice() Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-10-29 11:19 +0000
            Re: Negative array indicies and slice() Chris Angelico <rosuav@gmail.com> - 2012-10-29 22:32 +1100
            Re: Negative array indicies and slice() Andrew Robinson <andrew3@r3dsolutions.com> - 2012-10-28 21:52 -0700
            Re: Negative array indicies and slice() Chris Angelico <rosuav@gmail.com> - 2012-10-29 23:40 +1100
              Re: Negative array indicies and slice() Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-10-29 22:02 +0000
            Re: Negative array indicies and slice() Andrew Robinson <andrew3@r3dsolutions.com> - 2012-10-28 23:01 -0700
              Re: Negative array indicies and slice() Roy Smith <roy@panix.com> - 2012-10-29 09:52 -0400
                Re: Negative array indicies and slice() Andrew Robinson <andrew3@r3dsolutions.com> - 2012-10-29 08:20 -0700
                Re: Negative array indicies and slice() Ian Kelly <ian.g.kelly@gmail.com> - 2012-10-29 17:01 -0600
                Re: Negative array indicies and slice() Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2012-10-30 00:04 +0000
                Re: Negative array indicies and slice() Andrew Robinson <andrew3@r3dsolutions.com> - 2012-10-29 16:54 -0700
                Re: Negative array indicies and slice() Ian Kelly <ian.g.kelly@gmail.com> - 2012-10-30 02:15 -0600
            Re: Negative array indicies and slice() Chris Angelico <rosuav@gmail.com> - 2012-10-30 00:53 +1100
            Re: Negative array indicies and slice() Ian Kelly <ian.g.kelly@gmail.com> - 2012-10-29 11:09 -0600
            Re: Negative array indicies and slice() Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-10-29 22:14 +0000
            Re: Negative array indicies and slice() Andrew Robinson <andrew3@r3dsolutions.com> - 2012-10-29 08:42 -0700
              Re: Negative array indicies and slice() Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-10-30 00:02 +0000
                Re: Negative array indicies and slice() Andrew Robinson <andrew3@r3dsolutions.com> - 2012-10-29 12:34 -0700
                Re: Negative array indicies and slice() Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-10-30 08:17 +0000
                Re: Negative array indicies and slice() Andrew Robinson <andrew3@r3dsolutions.com> - 2012-10-30 08:47 -0700
                Re: Negative array indicies and slice() Mark Lawrence <breamoreboy@yahoo.co.uk> - 2012-10-30 23:48 +0000
                Re: Negative array indicies and slice() Michael Torrie <torriem@gmail.com> - 2012-10-30 23:29 -0600
                Re: Negative array indicies and slice() Michael Torrie <torriem@gmail.com> - 2012-10-29 23:53 -0600
                Re: Negative array indicies and slice() Andrew Robinson <andrew3@r3dsolutions.com> - 2012-10-29 17:04 -0700
            Re: Negative array indicies and slice() Chris Angelico <rosuav@gmail.com> - 2012-10-30 09:55 +1100
            Re: Negative array indicies and slice() Ian Kelly <ian.g.kelly@gmail.com> - 2012-10-29 17:07 -0600
              Re: Negative array indicies and slice() Roy Smith <roy@panix.com> - 2012-10-29 19:24 -0400
                Re: Negative array indicies and slice() Ian Kelly <ian.g.kelly@gmail.com> - 2012-10-29 17:43 -0600
                Re: Negative array indicies and slice() Roy Smith <roy@panix.com> - 2012-10-29 20:17 -0400
                Re: Negative array indicies and slice() Ian Kelly <ian.g.kelly@gmail.com> - 2012-10-29 18:05 -0600
            Re: Negative array indicies and slice() Andrew Robinson <andrew3@r3dsolutions.com> - 2012-10-29 11:00 -0700
            Re: Negative array indicies and slice() Chris Kaynor <ckaynor@zindagigames.com> - 2012-10-29 18:49 -0700
            Re: Negative array indicies and slice() Andrew Robinson <andrew3@r3dsolutions.com> - 2012-10-29 15:39 -0700
            Re: Negative array indicies and slice() Ian Kelly <ian.g.kelly@gmail.com> - 2012-10-29 23:55 -0600
            Re: Negative array indicies and slice() Ian Kelly <ian.g.kelly@gmail.com> - 2012-10-30 00:51 -0600
            Re: Negative array indicies and slice() Andrew Robinson <andrew3@r3dsolutions.com> - 2012-10-29 17:17 -0700
            Re: Negative array indicies and slice() Ian Kelly <ian.g.kelly@gmail.com> - 2012-10-30 01:21 -0600
            Re: Negative array indicies and slice() Ian Kelly <ian.g.kelly@gmail.com> - 2012-10-30 01:32 -0600
            Re: Negative array indicies and slice() Ian Kelly <ian.g.kelly@gmail.com> - 2012-10-30 02:46 -0600
            Re: Negative array indicies and slice() Ian Kelly <ian.g.kelly@gmail.com> - 2012-10-30 12:02 -0600
            Re: Negative array indicies and slice() Andrew Robinson <andrew3@r3dsolutions.com> - 2012-10-30 07:21 -0700
            Re: Negative array indicies and slice() Mark Lawrence <breamoreboy@yahoo.co.uk> - 2012-10-30 21:33 +0000
              Re: Negative array indicies and slice() Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-10-31 10:07 +0000
                Re: Negative array indicies and slice() Mark Lawrence <breamoreboy@yahoo.co.uk> - 2012-10-31 16:01 +0000
            Re: Negative array indicies and slice() Ian Kelly <ian.g.kelly@gmail.com> - 2012-10-30 15:47 -0600
            Re: Negative array indicies and slice() Ian Kelly <ian.g.kelly@gmail.com> - 2012-10-30 15:55 -0600
            Re: Negative array indicies and slice() Chris Angelico <rosuav@gmail.com> - 2012-10-31 09:00 +1100
            Re: Negative array indicies and slice() Ian Kelly <ian.g.kelly@gmail.com> - 2012-10-30 16:02 -0600
            Re: Negative array indicies and slice() Mark Lawrence <breamoreboy@yahoo.co.uk> - 2012-10-30 23:30 +0000
          Re: Negative array indicies and slice() Ian Kelly <ian.g.kelly@gmail.com> - 2012-10-29 11:27 -0600
          Re: Negative array indicies and slice() Andrew Robinson <andrew3@r3dsolutions.com> - 2012-10-29 16:33 -0700
        Re: Negative array indicies and slice() Andrew <andrewr3mail@gmail.com> - 2012-10-29 00:54 -0700
    Re: Negative array indicies and slice() andrewr3mail@gmail.com - 2012-10-28 21:00 -0700
    Re: Negative array indicies and slice() Andrew <andrewr3mail@gmail.com> - 2012-10-28 21:09 -0700
      Re: Negative array indicies and slice() alex23 <wuwei23@gmail.com> - 2012-10-28 21:44 -0700
        Re: Negative array indicies and slice() andrewr3mail@gmail.com - 2012-10-29 01:24 -0700
          Re: Negative array indicies and slice() Chris Rebert <clp2@rebertia.com> - 2012-10-29 01:37 -0700
            Re: Negative array indicies and slice() andrewr3mail@gmail.com - 2012-10-29 01:59 -0700
              Re: Negative array indicies and slice() Mark Lawrence <breamoreboy@yahoo.co.uk> - 2012-10-29 09:36 +0000
              Re: Negative array indicies and slice() Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-10-29 10:34 +0000
            Re: Negative array indicies and slice() andrewr3mail@gmail.com - 2012-10-29 01:59 -0700
      Re: Negative array indicies and slice() Paul Rubin <no.email@nospam.invalid> - 2012-10-28 22:14 -0700
        Re: Negative array indicies and slice() andrewr3mail@gmail.com - 2012-10-29 01:08 -0700
          Re: Negative array indicies and slice() Chris Rebert <clp2@rebertia.com> - 2012-10-29 01:26 -0700
    Re: Negative array indicies and slice() Andrew <andrewr3mail@gmail.com> - 2012-10-28 21:09 -0700
  Re: Negative array indicies and slice() MRAB <python@mrabarnett.plus.com> - 2012-10-29 03:45 +0000
  Re: Negative array indicies and slice() 88888 Dihedral <dihedral88888@googlemail.com> - 2012-11-01 18:08 -0700

csiph-web