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

Groups > comp.lang.python > #111536 > unrolled thread

Re: PEP Request: Advanced Data Structures

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  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

#111536 — Re: PEP Request: Advanced Data Structures

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

[toc] | [next] | [standalone]

#111538

Chris Angelico <rosuav@gmail.com> writes:
>> keep a reference to an element deep in the list, and insert a new
>> element in O(1) time at that point.
> 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.

I think the idea is that you're already deep in the list when you decide
to insert an element or do other surgery on the list.  An example might
be a lookup table with linear search, where you want to bring the LRU
item to the front of the list after finding it.  Really though, that's
an ugly thing to be doing in any language, and it definitely isn't
something that comes up much in Python.

[toc] | [prev] | [next] | [standalone]

#111539

On Sun, Jul 17, 2016 at 12:33 PM, Paul Rubin <no.email@nospam.invalid> wrote:
> Chris Angelico <rosuav@gmail.com> writes:
>>> keep a reference to an element deep in the list, and insert a new
>>> element in O(1) time at that point.
>> 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.
>
> I think the idea is that you're already deep in the list when you decide
> to insert an element or do other surgery on the list.  An example might
> be a lookup table with linear search, where you want to bring the LRU
> item to the front of the list after finding it.  Really though, that's
> an ugly thing to be doing in any language, and it definitely isn't
> something that comes up much in Python.

Right, but how did you *get* that deep into the list? By following a
chain of pointers. That's a relatively costly operation, so the
benefit of not having to move all the following elements is damaged
some by the cost of chasing pointers to get there in the first place.
So overall, performance would be better with the high-performance
list, even if it does mean moving a bunch of elements (when you delete
some). Since it's a difference in asymptotic cost, there would
theoretically be some number of elements after which it would be
cheaper to use the linked list... but maybe the cost of chasing
pointers goes up even more, to make that never happen.

ChrisA

[toc] | [prev] | [next] | [standalone]

#111540

On 2016-07-17 03:33, Paul Rubin wrote:
> Chris Angelico <rosuav@gmail.com> writes:
>>> keep a reference to an element deep in the list, and insert a new
>>> element in O(1) time at that point.
>> 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.
>
> I think the idea is that you're already deep in the list when you decide
> to insert an element or do other surgery on the list.  An example might
> be a lookup table with linear search, where you want to bring the LRU
> item to the front of the list after finding it.  Really though, that's
> an ugly thing to be doing in any language, and it definitely isn't
> something that comes up much in Python.
>
I once sped up lookups on a doubly-linked list by adding a dict that 
would take me straight to the appropriate node. This was in C, though.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web