PEP Request: Advanced Data Structures

[Chris Angelico]

On Sun, Jul 17, 2016 at 12:33 PM, Paul Rubin <no.email at nospam.invalid> wrote:
> Chris Angelico <rosuav at 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