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 can be added at both sides for constant time. Memory consumption is almost the same. ---------- assignee: rhettinger components: Extension Modules files: deque_array.patch keywords: patch messages: 265773 nosy: rhettinger, serhiy.storchaka priority: normal severity: normal stage: patch review status: open title: O(1) deque indexing type: enhancement versions: Python 3.6 Added file: http://bugs.python.org/file42879/deque_array.patch _______________________________________ Python tracker <rep...@bugs.python.org> <http://bugs.python.org/issue27047> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
