New submission from Raymond Hettinger: The current algorithm for remove() rotates the deque one-by-one until a match is found, pops it off the deque and does single mass rotate to undo the 1-step rotates.
An alternative approach is to use deque_index() to locate the value of interest and use deque_del_item() to remove it. If not value is found, the alternative is better because it never moves the data in the deque. If the value is found, the alternative removes it using two mass rotations. The advantage in that case is the mass rotates are faster than many 1-step rotates. The disadvantage is that we go through the pointer chain twice (the first time visiting and comparing every element and the second time only following the chain of links). If the deque mutates during the search, a RuntimeError is raised. This is a behavior change, formerly it raised an IndexError. ---------- assignee: rhettinger files: deque_better_remove.diff keywords: patch messages: 251691 nosy: rhettinger priority: normal severity: normal stage: patch review status: open title: Alternative algorithm for deque_remove() versions: Python 3.6 Added file: http://bugs.python.org/file40594/deque_better_remove.diff _______________________________________ Python tracker <rep...@bugs.python.org> <http://bugs.python.org/issue25246> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
