Home Original page

PEP Request: Advanced Data Structures

Chris Angelico rosuav at gmail.com
Sat Jul 16 21:30:25 EDT 2016 
On Sun, Jul 17, 2016 at 10:54 AM,  <cs at 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
More information about the Python-list mailing list