> > My own ideal solution would be a subtle hack to the list
> > implementation to make pop(0) and insert(0, x) go a lot faster -- this
> > can be done by adding one or two extra fields to the list head and
> > allowing empty space at the front of the list as well as at the end.
>
> I'm sure you know this, but just for sake of argument, how many extra
> fields?
You misunderstood -- the *fields* I was talking about are
counters or pointers that keep track of the overallocation, and 1 or
at most 2 is enough.
> A couple? A few? 20? 30? I'm not sure there really is a
> good hard and fast number.
You're talking about the amount of overallocation. I would propose to
overallocate exactly as much as the list implementation currently does,
which is a very subtle scheme that overallocates more when the list
grows larger to maintain logarithmic behavior.
> I think it makes as much sense to
> preallocate the same number of entries to the front of a list, as to
> what is currently allocated to the back. At that point, you can
> guarantee O(1) {pop(0), pop(), append() and insert(0)} behavior, at the
> cost of slightly more memory. Then it really wouldn't matter how people
> implement their stacks or queues (front, back, double-list), it would
> still be fast.
Right.
--Guido van Rossum (home page: http://www.python.org/~guido/)
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4