[Python-Dev] deque implementation question

[Joao S. O. Bueno]

On 15 July 2017 at 04:01, Max Moroz <maxmoroz at gmail.com> wrote:

> 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 at python.org
> https://mail.python.org/mailman/listinfo/python-dev
> Unsubscribe: https://mail.python.org/mailman/options/python-dev/
> jsbueno%40python.org.br
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-dev/attachments/20170718/b953d377/attachment.html>