[issue25246] Alternative algorithm for deque_remove()

[Raymond Hettinger]

Change by Raymond Hettinger :


--
resolution: rejected -> fixed

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue25246] Alternative algorithm for deque_remove()

[Raymond Hettinger]

Raymond Hettinger  added the comment:


New changeset 6b1ac809b9718a369aea67b99077cdd682be2238 by Raymond Hettinger in 
branch 'master':
bpo-25246: Optimize deque.remove() (GH-23898)
https://github.com/python/cpython/commit/6b1ac809b9718a369aea67b99077cdd682be2238


--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue25246] Alternative algorithm for deque_remove()

[Raymond Hettinger]

Raymond Hettinger  added the comment:

Created a new PR that gives a substantial speed-up while keeping the API 
unchanged and while closely matching the logic for list.remove().

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue25246] Alternative algorithm for deque_remove()

[Raymond Hettinger]

Change by Raymond Hettinger :


--
pull_requests: +22753
pull_request: https://github.com/python/cpython/pull/23898

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue25246] Alternative algorithm for deque_remove()

[Raymond Hettinger]

Raymond Hettinger  added the comment:

Am closing this one because it isn't worth an API change.  The remove() method 
is little used and to the extent people do use it, they expect it to work like 
list.remove().  The latter never raises a RuntimeError.

--
resolution:  -> rejected
stage: patch review -> resolved
status: open -> closed

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue25246] Alternative algorithm for deque_remove()

[Pablo Galindo Salgado]

Change by Pablo Galindo Salgado :


--
pull_requests: +9221

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue25246] Alternative algorithm for deque_remove()

[Pablo Galindo Salgado]

Change by Pablo Galindo Salgado :


--
pull_requests: +7285

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue25246] Alternative algorithm for deque_remove()

[Tal Einat]

Tal Einat  added the comment:

IMO both approaches sound better than the existing implementation.  Better to 
choose one than to do nothing.

--
nosy: +taleinat

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue25246] Alternative algorithm for deque_remove()

[Raymond Hettinger]

Change by Raymond Hettinger :


--
priority: normal -> low
versions: +Python 3.8 -Python 3.6

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue25246] Alternative algorithm for deque_remove()

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

There is more optimal approach.

Find not just an index in a deque, but a block and an index in a block. After 
that move left or right part of a deque one position right or left. 
__delitem__() could be 2 times faster, remove() could be faster too. Helpers 
proposed in issue17394 allow to do this easily.

--
nosy: +serhiy.storchaka

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue25246] Alternative algorithm for deque_remove()

[Raymond Hettinger]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com