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

Groups > comp.lang.python > #111540

Re: PEP Request: Advanced Data Structures

Show all headers | View raw

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.

Back to comp.lang.python | Previous | Next — Previous 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