PEP Request: Advanced Data Structures
MRAB
python at mrabarnett.plus.com
Sat Jul 16 22:49:06 EDT 2016
On 2016-07-17 03:33, Paul Rubin 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.
>
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.
More information about the Python-list
mailing list