deque implementation question
What would be the disadvantage of implementing collections.deque as a circular array (rather than a doubly linked list of blocks)? My naive thinking was that a circular array would maintain the current O(1) append/pop from either side, and would improve index lookup in the middle from O(n) to O(1). What am I missing? The insertion/removal of an arbitrary item specified by a pointer would increase from constant time to linear, but since we don't have pointers this is a moot point. Of course when the circular array is full, it will need to be reallocated, but the amortized cost of that is still O(1). (Moreover, for a bounded deque, there's even an option of preallocation, which would completely eliminate reallocations.) Thanks Max
I found the answer in _collectionsmodule.c
/* Data for deque objects is stored in a doubly-linked list of fixed
* length blocks. This assures that appends or pops never move any
* other data elements besides the one being appended or popped.
*
* Another advantage is that it completely avoids use of realloc(),
* resulting in more predictable performance.
Regards,
INADA Naoki
What would be the disadvantage of implementing collections.deque as a circular array (rather than a doubly linked list of blocks)? My naive thinking was that a circular array would maintain the current O(1) append/pop from either side, and would improve index lookup in the middle from O(n) to O(1). What am I missing?
The insertion/removal of an arbitrary item specified by a pointer would increase from constant time to linear, but since we don't have pointers this is a moot point.
Of course when the circular array is full, it will need to be reallocated, but the amortized cost of that is still O(1). (Moreover, for a bounded deque, there's even an option of preallocation, which would completely eliminate reallocations.)
Thanks
Max
_______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/songofacandy%40gmail.com
[Max Moroz
What would be the disadvantage of implementing collections.deque as a circular array (rather than a doubly linked list of blocks)? ...
You answered it yourself ;-)
... Of course when the circular array is full, it will need to be reallocated, but the amortized cost of that is still O(1).
Bingo. The primary point of a deque is to make popping and pushing at both ends efficient. That's what the current implementation does: worst-case constant time per push or pop regardless of how many items are in the deque. That beats "amortized O(1)" in the small and in the large. That's why it was done this way. Some other deque methods are consequently slower than they are for lists, but who cares? For example, the only indices I've ever used with a deque are 0 and -1 (to peek at one end or the other of a deque), and the implementation makes accessing those specific indices constant-time too.
On 15 July 2017 at 04:01, Max Moroz
What would be the disadvantage of implementing collections.deque as a circular array (rather than a doubly linked list of blocks)? My naive thinking was that a circular array would maintain the current O(1) append/pop from either side, and would improve index lookup in the middle from O(n) to O(1). What am I missing?
The insertion/removal of an arbitrary item specified by a pointer would increase from constant time to linear, but since we don't have pointers this is a moot point.
Of course when the circular array is full, it will need to be reallocated, but the amortized cost of that is still O(1). (Moreover, for a bounded deque, there's even an option of preallocation, which would completely eliminate reallocations.)
Now - since you are at it, you could possibly mine pypi for interesting efficient data structures that could cover use cases lists and deque not suffice. I am pretty sure one could find a couple, - and once we get a few that are well behaved and somewhat popular, they could be made candidates for inclusion in collections, I guess.
Thanks
Max
_______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/ jsbueno%40python.org.br
participants (4)
-
INADA Naoki -
Joao S. O. Bueno -
Max Moroz -
Tim Peters