Reimplementing collections.deque as a dynamic array
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
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.
On 29May2012 00:46, Julian Berman <julian@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 <cs@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
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.
On 29May2012 00:46, Julian Berman <julian@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 <cs@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
participants (3)
-
Alexandre Vassalotti -
Cameron Simpson -
Julian Berman