Re: PEP Request: Advanced Data Structures

From	Chris Angelico <rosuav@gmail.com>
Newsgroups	comp.lang.python
Subject	Re: PEP Request: Advanced Data Structures
Date	2016-07-17 11:30 +1000
Message-ID	<mailman.49.1468719034.2307.python-list@python.org> (permalink)
References	<fphlobd109lvi2e4r4oe4qjpcf97chhe67@4ax.com> <20160717005426.GA50011@cskk.homeip.net> <CAPTjJmpfPBMwT5zSM43zonUht_AY2dpzqwSv53XZiX5OZMCoig@mail.gmail.com>

Show all headers | View raw

On Sun, Jul 17, 2016 at 10:54 AM,  <cs@zip.com.au> wrote:
> Well, in a larger context you can keep a reference to an element deep in the
> list, and insert a new element in O(1) time at that point.
>

I'd like to know how many elements your list needs before that
actually becomes faster than CPython's heavily-optimized C-implemented
list structure. And if someone's proposing a new core data type, I
very much doubt that'll fly - and at the C level, wouldn't tracing the
links cost massively more than the occasional insertion too? I'm not
sure O(1) is of value at any size, if the costs of all your other
operations go up.

ChrisA

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

Thread

Re: PEP Request: Advanced Data Structures Chris Angelico <rosuav@gmail.com> - 2016-07-17 11:30 +1000
  Re: PEP Request: Advanced Data Structures Paul Rubin <no.email@nospam.invalid> - 2016-07-16 19:33 -0700
    Re: PEP Request: Advanced Data Structures Chris Angelico <rosuav@gmail.com> - 2016-07-17 12:43 +1000
    Re: PEP Request: Advanced Data Structures MRAB <python@mrabarnett.plus.com> - 2016-07-17 03:49 +0100

csiph-web