Description

rhettinger

opened on Jan 4, 2022

Issue body actions

BPO	46257
Nosy	@rhettinger, @stevendaprano
PRs	bpo-46257: Convert statistics._ss() to a single pass algorithm #30403

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2022-01-05.15:39:37.204>
created_at = <Date 2022-01-04.17:04:05.171>
labels = ['3.11', 'library', 'performance']
title = 'Convert statistics sum of squares to a single pass algorithm'
updated_at = <Date 2022-01-05.15:39:37.203>
user = 'https://github.com/rhettinger'

bugs.python.org fields:

activity = <Date 2022-01-05.15:39:37.203>
actor = 'rhettinger'
assignee = 'none'
closed = True
closed_date = <Date 2022-01-05.15:39:37.204>
closer = 'rhettinger'
components = ['Library (Lib)']
creation = <Date 2022-01-04.17:04:05.171>
creator = 'rhettinger'
dependencies = []
files = []
hgrepos = []
issue_num = 46257
keywords = ['patch']
message_count = 2.0
messages = ['409692', '409777']
nosy_count = 2.0
nosy_names = ['rhettinger', 'steven.daprano']
pr_nums = ['30403']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue46257'
versions = ['Python 3.11']

Activity

1. rhettinger commented on Jan 4, 2022

   

   rhettinger

   on Jan 4, 2022

   ContributorAuthor

   More actions

   The existing code makes two passes, one to compute the mean and another to compute the sum of squared differences from the mean. A consequence of making two passes is that iterator inputs must be converted to a list before processing. This throws away the memory saving advantages of iterators.

   The ostensible reason for the two pass code is that the single pass variant is numerically unstable when implemented with floating point accumulators. However, this code uses fractions throughout, so the accumulation is exact.

   Changing to a single pass saves memory, doubles the speed, and simplifies the upstream code in variance(), pvariance(), stdev(), and pstdev().
2. rhettinger

   added

   3.11only security fixesonly security fixes

   stdlibStandard Library Python modules in the Lib/ directoryStandard Library Python modules in the Lib/ directory

   performancePerformance or resource usagePerformance or resource usage

   on Jan 4, 2022
3. rhettinger commented on Jan 5, 2022

   

   rhettinger

   on Jan 5, 2022

   ContributorAuthor

   More actions

   New changeset 43aac29 by Raymond Hettinger in branch 'main':
   bpo-46257: Convert statistics._ss() to a single pass algorithm (GH-30403)
   43aac29
4. rhettinger

   closed this as completedon Jan 5, 2022
5. rhettinger

   closed this as completedon Jan 5, 2022
6. ezio-melotti

   transferred this issue fromon Apr 10, 2022

Issue actions