Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Convert statistics sum of squares to a single pass algorithm #90415

Closed
rhettinger opened this issue Jan 4, 2022 · 2 comments
Closed

Convert statistics sum of squares to a single pass algorithm #90415

rhettinger opened this issue Jan 4, 2022 · 2 comments
Labels
3.11 only security fixes performance Performance or resource usage stdlib Python modules in the Lib dir

Comments

@rhettinger
Copy link
Contributor

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']
    @rhettinger
    Copy link
    Contributor Author

    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().

    @rhettinger rhettinger added 3.11 only security fixes stdlib Python modules in the Lib dir performance Performance or resource usage labels Jan 4, 2022
    @rhettinger
    Copy link
    Contributor Author

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

    @ezio-melotti ezio-melotti transferred this issue from another repository Apr 10, 2022
    @CAM-Gerlach CAM-Gerlach mentioned this issue Oct 19, 2022
    Merged
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
    Assignees
    No one assigned
    Labels
    3.11 only security fixes performance Performance or resource usage stdlib Python modules in the Lib dir
    Projects
    None yet
    Milestone
    No milestone
    Development

    No branches or pull requests
    1 participant
    @rhettinger