Issue 26002: make statistics.median_grouped more efficient (original) (raw)

Created on 2016-01-03 14:21 by upendra-k14, last changed 2022-04-11 14:58 by admin. This issue is now closed.

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) *	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) *	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)	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