classification
Title: make statistics.median_grouped more efficient
Type: performance Stage: resolved
Components: Library (Lib) Versions: Python 3.6
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: python-dev, rhettinger, steven.daprano, upendra-k14
Priority: normal Keywords: patch

Created on 2016-01-03 14:21 by upendra-k14, last changed 2016-05-06 12:04 by berker.peksag. This issue is now closed.

Files
File name Uploaded Description Edit
median_grouped.patch upendra-k14, 2016-01-03 14:21 Improving the performance of counting number of occurence of 'x' and finding leftmost position of 'x'
Messages (6)
msg257419 - (view) Author: Upendra Kumar (upendra-k14) * Date: 2016-01-03 14:21
statistics.median_grouped currently uses cf=data.index(x) to find the leftmost position of x in data ( line number 445 ). Here, data.index() has linear time complexity, which may not be good for long lists.

But, here since the list 'data' is sorted beforehand, we can use binary search ( bisect_left() ) to find the leftmost occurrence of 'x' in 'data'. 

Similarly, for counting number of occurrence of 'x' in data after sorting, we can find the position of rightmost occurrence of 'x' in data[l1....len(data)], where l1 is position of leftmost occurrence of 'x' (line number 447 )
msg259095 - (view) Author: Upendra Kumar (upendra-k14) * Date: 2016-01-28 06:28
Can someone please review my patch?  I think it can increase the performance significantly of the median_grouped() function. But, I don't have any standard way of checking if it would improve or will be an overkill for the median_grouped() function?
msg259102 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2016-01-28 07:06
This code looks good and will certainly reduce the number of comparisons in non-trivial cases.

FWIW, It looks like the index functions are lifted directly from the bisect docs.

Steven, any objections?
msg259104 - (view) Author: Upendra Kumar (upendra-k14) * Date: 2016-01-28 07:22
Yeah, I slightly modified the functions from the bisect docs to suit for the purpose here.
msg260104 - (view) Author: Steven D'Aprano (steven.daprano) * (Python committer) Date: 2016-02-11 14:22
Looks good to me.

I've run some quick timing tests, and for very small lists, there's no significant difference, but for larger lists I'm getting up to a 50% speedup. Nicely done, thank you.
msg264847 - (view) Author: Roundup Robot (python-dev) (Python triager) Date: 2016-05-04 18:47
New changeset 7b2fafd78c1d by Steven D'Aprano in branch 'default':
Issue 26002 and 25974
https://hg.python.org/cpython/rev/7b2fafd78c1d
History
Date User Action Args
2016-05-06 12:04:27berker.peksagsetstatus: open -> closed
resolution: fixed
stage: commit review -> resolved
2016-05-05 02:04:52steven.dapranosetstage: patch review -> commit review
2016-05-04 18:47:25python-devsetnosy: + python-dev
messages: + msg264847
2016-02-11 14:22:55steven.dapranosetmessages: + msg260104
2016-01-28 07:22:38upendra-k14setmessages: + msg259104
2016-01-28 07:06:04rhettingersetversions: - Python 3.5
nosy: + rhettinger

messages: + msg259102

stage: patch review
2016-01-28 06:28:42upendra-k14setmessages: + msg259095
2016-01-03 14:33:51SilentGhostsetnosy: + steven.daprano

versions: - Python 3.4
2016-01-03 14:21:58upendra-k14create