[Python-ideas] Reimplementing collections.deque as a dynamic array

[Julian Berman]

I've occasionally had a need for a container with constant-time append
to both ends without sacrificing constant-time indexing in the middle.
collections.deque will in these cases narrowly miss the target due to
linear indexing (with the current use case being for two deques
storing the lines of text surrounding the cursor in a text editor
while still being randomly indexed occasionally).

Wikipedia lists at least two common deque implementations:

http://en.wikipedia.org/wiki/Double-ended_queue#Implementations

where switching to a dynamic array would seemingly satisfy my requirements.

I know from a bit of experience (and a quick SO perusal) that "How do
I index a deque" does occasionally come up. Any thoughts on the value
of such a change?

JB
_______________________________________________
Python-ideas mailing list
Python...@python.org
http://mail.python.org/mailman/listinfo/python-ideas

[Alexandre Vassalotti]

The current implementation of deque is a doubly linked list of arrays. Indexing is indeed linear, but still very efficient. It takes 1 ms to index a deque with a million items.

If that's not good enough, you should try to implement your own container using lists (which are dynamic arrays in Python). That should be easy to implement though this approach will likely be slower for everything but very large datasets.

[Cameron Simpson]

On 29May2012 00:46, Julian Berman <jul...@grayvines.com> wrote:
| I've occasionally had a need for a container with constant-time append
| to both ends without sacrificing constant-time indexing in the middle.
| collections.deque will in these cases narrowly miss the target due to
| linear indexing (with the current use case being for two deques
| storing the lines of text surrounding the cursor in a text editor
| while still being randomly indexed occasionally).
|
| Wikipedia lists at least two common deque implementations:
|
| http://en.wikipedia.org/wiki/Double-ended_queue#Implementations
|
| where switching to a dynamic array would seemingly satisfy my requirements.
|
| I know from a bit of experience (and a quick SO perusal) that "How do
| I index a deque" does occasionally come up. Any thoughts on the value
| of such a change?

It was pointed out to me recently that Python's list.append() is constant
time overall.

Use two lists, one for append-forward and one for append backward. Keep
track of the bound. Access to item "i" is trivially computed from the
backward and forward list sizes and ends.

Cheers,
--
Cameron Simpson <c...@zip.com.au> DoD#743
http://www.cskk.ezoshosting.com/cs/

The mere existence of a problem is no proof of the existence of a solution.
- Yiddish Proverb