[issue46257] Convert statistics sum of squares to a single pass algorithm

[Raymond Hettinger]

Change by Raymond Hettinger :


--
resolution:  -> fixed
stage: patch review -> resolved
status: open -> closed

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue46257] Convert statistics sum of squares to a single pass algorithm

[Raymond Hettinger]

Raymond Hettinger  added the comment:


New changeset 43aac29cbbb8a963a22c334b5b795d1e43417d6b by Raymond Hettinger in 
branch 'main':
bpo-46257: Convert statistics._ss() to a single pass algorithm (GH-30403)
https://github.com/python/cpython/commit/43aac29cbbb8a963a22c334b5b795d1e43417d6b


--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue46257] Convert statistics sum of squares to a single pass algorithm

[Raymond Hettinger]

Change by Raymond Hettinger :


--
keywords: +patch
pull_requests: +28611
stage:  -> patch review
pull_request: https://github.com/python/cpython/pull/30403

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue46257] Convert statistics sum of squares to a single pass algorithm

[Raymond Hettinger]

New submission from Raymond Hettinger :

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

--
components: Library (Lib)
messages: 409692
nosy: rhettinger, steven.daprano
priority: normal
severity: normal
status: open
title: Convert statistics sum of squares to a single pass algorithm
type: performance
versions: Python 3.11

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com