Project

General

Profile

Feature #12217

Introducing Enumerable#sum for precision compensated summation and revert r54237

Added by Kenta Murata 10 months ago. Updated 7 months ago.

Status:
Closed
Priority:
Normal
Assignee:
Target version:
-
[ruby-core:74569]

Description

In this issue I propose to introduce Enumerable#sum for precision compensated summation of an array of floating point numbers.

In r54237, I've changed Enumerable#inject to support precision compensated summation for summing up floating point numbers.
But I noticed that this commit broke the equality of ary.inject(:+) == ary.inject {|a, x| a + x }.
I think this equality is important property of inject method, so I don't want to break it.

And because precision compensated algorithms are complicated, I think they are provided in the standard library, especially simple summation.

inject-plus.txt View (1.21 MB) Akira Tanaka, 03/25/2016 12:55 PM


Related issues

Related to Ruby trunk - Feature #10298: Array#float_sum (like math.fsum of Python) Rejected
Related to Ruby trunk - Feature #12222: Introducing basic statistics methods for Enumerable (and optimized implementation for Array) Assigned

Associated revisions

Revision 54566
Added by Akira Tanaka 9 months ago

add a space in [Feature #12217]

History

#1 [ruby-core:74570] Updated by Akira Tanaka 10 months ago

I think sum of elements of an enumerable is used in many situations.

I searched '.inject[ ({]' and '+' in .rb files in gems:
inject-plus.txt

It seems .inject(:+) is an idiom for summation.

% fgrep '.inject(:+)' inject-plus.txt|wc -l
1040
% fgrep '.inject(&:+)' inject-plus.txt|wc -l
446
% fgrep '.inject(0, :+)' inject-plus.txt|wc -l
138
% fgrep '.inject(0, &:+)' inject-plus.txt|wc -l
90
% fgrep '.inject(0.0, :+)' inject-plus.txt|wc -l 
13
% fgrep '.inject(0.0, &:+)' inject-plus.txt|wc -l
23

It seems .inject {|s,e| s + e} is also used.

% grep '.inject(0) *{|\([a-z0-9]\+\), *\([a-z0-9]\+\)| *\1 *+ *\2 *}' inject-plus.txt|wc -l
311
% grep '.inject *{|\([a-z0-9]\+\), *\([a-z0-9]\+\)| *\1 *+ *\2 *}' inject-plus.txt|wc -l  
213
% grep '.inject(0.0) *{|\([a-z0-9]\+\), *\([a-z0-9]\+\)| *\1 *+ *\2 *}' inject-plus.txt|wc -l
27

I think Enumerable#sum is useful:
- Enumerable#sum is shorter than Enumerable#inject(:+) ant it makes code succinct.
- it can return 0 for empty enumerable. It makes us to avoid bugs on empty enumerable.
- more accurate for sum of Floats by Kahan's compensated summation algorithm (as muraken said)
- faster than Enumerable#inject(:+) (Enumerable#inject(:+) will also be faster since Ruby 2.4, though)

However it has a problem:
- Enumerable#sum is not well defined for non-numeric elements, especially objects without + method.

#2 Updated by Akira Tanaka 10 months ago

  • Related to Feature #10298: Array#float_sum (like math.fsum of Python) added

#3 [ruby-core:74573] Updated by Akira Tanaka 10 months ago

Akira Tanaka wrote:

  • Enumerable#sum is not well defined for non-numeric elements, especially objects without + method.

An idea to avoid this problem is an argument to specify the initial object.

module Enumerable
  def sum(init=0)
    inject(init, :+) # or better algorithm.
  end
end

Programmers have responsibility that init has + method.

However init has the default value 0 because #sum is mostly used for numeric.

#4 Updated by Kenta Murata 10 months ago

  • Related to Feature #12222: Introducing basic statistics methods for Enumerable (and optimized implementation for Array) added

#6 [ruby-core:74932] Updated by Kenta Murata 9 months ago

  • Assignee changed from Yukihiro Matsumoto to Kenta Murata

#7 Updated by Akira Tanaka 9 months ago

  • Status changed from Assigned to Closed

Applied in changeset r54566.


add a space in [Feature #12217]

#8 [ruby-core:75559] Updated by Akira Tanaka 8 months ago

matz accepted Enumerable#sum (and Range#sum).

Examples:
Range#sum for mathematical sigma: (0..n).sum {|i| ... }
Hash#sum for expected value such as { value1 => probability1, ... }.sum {|v, prob| v * prob }

#10 [ruby-core:76312] Updated by Akira Tanaka 7 months ago

Richard Schneeman wrote:

Would be nice if we could match behavior with Rails Enumerable#sum https://github.com/rails/rails/blob/3d716b9e66e334c113c98fb3fc4bcf8a945b93a1/activesupport/lib/active_support/core_ext/enumerable.rb#L2-L27

I don't like it because the behavior is too complex.

For example, [false].sum returns 0.

It is difficult to document (and understand) the behavior.

#11 [ruby-core:76313] Updated by Kenta Murata 7 months ago

For example, [false].sum returns 0.

I reported this undocumented behavior as a bug several months ago.
https://github.com/rails/rails/issues/24796

Also available in: Atom PDF