classification
Title: Avoid inefficient way to find start point in deque.index
Type: enhancement Stage: resolved
Components: Library (Lib) Versions: Python 3.8
process
Status: closed Resolution: out of date
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: hacksg, ksg97031, rhettinger, ronaldoussoren
Priority: normal Keywords: patch

Created on 2018-08-01 02:31 by ksg97031, last changed 2019-08-22 18:39 by rhettinger. This issue is now closed.

Pull Requests
URL Status Linked Edit
PR 8611 closed ksg97031, 2018-08-02 00:07
Messages (7)
msg322834 - (view) Author: ksg97031 (ksg97031) * Date: 2018-08-01 02:31
Source base : heads/master:b75d7e2435, Aug  1 2018, 10:32:28

$ cat test.py
import timeit

queue_setup = '''
from collections import deque
q = deque()
start = 10**5
stop = start + 500
for i in range(0, stop):
    q.append(i)
'''

code = '''
index = q.index(30, 1, stop)
assert index == 30
'''
code2 = '''
index = q.index((start >> 1) + 1, start >> 1, stop >> 1)
assert index == (start >> 1) + 1
'''
code3 = '''
index = q.index(start + 1, start, stop)
assert index == start + 1
'''

repeat = 100000
print(timeit.timeit(setup = queue_setup, stmt = code, number = repeat * 20))
print(timeit.timeit(setup = queue_setup, stmt = code2, number = repeat))
print(timeit.timeit(setup = queue_setup, stmt = code3, number = repeat))

$ ./python_cur.exe test.py
2.154346022
2.899595406
5.265440983

$ ./python_ksg.exe test.py
2.1457827320000002
0.717190736
1.9934196979999999

----------------------
msg322859 - (view) Author: Ronald Oussoren (ronaldoussoren) * (Python committer) Date: 2018-08-01 12:37
I'm not sure what your proposal is. Do you have a patch that increases the performance of collections.deque in some cases?  If so please share that patch, preferably as a pull request on GitHub (see <https://devguide.python.org/pullrequest/> for an explanation).
msg322862 - (view) Author: Seonggi Kim (hacksg) * Date: 2018-08-01 14:12
Sorry, I'm waiting for permit CLA signing.
I will request PR after CLA was signed.
msg322863 - (view) Author: Ronald Oussoren (ronaldoussoren) * (Python committer) Date: 2018-08-01 14:15
That's ok, I hadn't expected that you'd sign the CLA before being asked to do so :-)

Good luck.
msg322883 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2018-08-01 20:10
Why are we getting multiple tracker items opening and closing for this at the same time?  Something odd is happening.  Please don't close the tracker and change user ids in the middle of a conversation:

   https://bugs.python.org/issue34298
   https://bugs.python.org/issue34295
msg322900 - (view) Author: Seonggi Kim (hacksg) * Date: 2018-08-02 00:10
I thing so too, it's my fault.
msg350225 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2019-08-22 18:39
It looks like deque.index() now has a fast searcher.
History
Date User Action Args
2019-08-22 18:39:40rhettingersetstatus: open -> closed
resolution: out of date
messages: + msg350225

stage: patch review -> resolved
2018-08-02 00:10:08hacksgsetmessages: + msg322900
2018-08-02 00:07:21ksg97031setkeywords: + patch
stage: patch review
pull_requests: + pull_request8117
2018-08-01 20:10:01rhettingersetassignee: rhettinger
messages: + msg322883
2018-08-01 14:15:24ronaldoussorensetmessages: + msg322863
2018-08-01 14:12:44hacksgsetnosy: + hacksg
messages: + msg322862
2018-08-01 12:37:41ronaldoussorensetnosy: + ronaldoussoren
messages: + msg322859
2018-08-01 02:31:05ksg97031create