[issue27047] O(1) deque indexing

2016-05-17 Thread Raymond Hettinger
Raymond Hettinger added the comment: Sorry Serhiy, I really don't want to do this. Indexing is the least important part of the API and should not drive the overall structure. This optimization is at odds with the design goal of a structure that is efficient at near end-points and is not inte

[issue27047] O(1) deque indexing

2016-05-17 Thread Serhiy Storchaka
New submission from Serhiy Storchaka: Proposed patch changes the complexity of deque indexing from linear to constant. All other operations preserves its amortized cost. New deque implementation use two-level array instead of linked list. Since free space is reserved at both side, new blocks c