[New-bugs-announce] [issue27047] O(1) deque indexing

Serhiy Storchaka report at bugs.python.org
Tue May 17 15:41:40 EDT 2016

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 <report at bugs.python.org>

More information about the New-bugs-announce mailing list