Project

General

Profile

Actions

Feature #12217

closed

Introducing Enumerable#sum for precision compensated summation and revert r54237

Added by mrkn (Kenta Murata) about 8 years ago. Updated over 7 years ago.

Status:
Closed
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.


Files

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

Related issues 2 (0 open2 closed)

Related to Ruby master - Feature #10298: Array#float_sum (like math.fsum of Python)RejectedActions
Related to Ruby master - Feature #12222: Introducing basic statistics methods for Enumerable (and optimized implementation for Array)Closedakr (Akira Tanaka)Actions

Updated by akr (Akira Tanaka) about 8 years 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.
Actions #2

Updated by akr (Akira Tanaka) about 8 years ago

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

Updated by akr (Akira Tanaka) about 8 years 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.

Actions #4

Updated by mrkn (Kenta Murata) about 8 years ago

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

Updated by mrkn (Kenta Murata) almost 8 years ago

  • Assignee changed from matz (Yukihiro Matsumoto) to mrkn (Kenta Murata)
Actions #7

Updated by akr (Akira Tanaka) almost 8 years ago

  • Status changed from Assigned to Closed

Applied in changeset r54566.


add a space in [ruby-core:74569] [Feature #12217]

Updated by akr (Akira Tanaka) almost 8 years 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 }

Updated by akr (Akira Tanaka) over 7 years 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.

Updated by mrkn (Kenta Murata) over 7 years 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

Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0Like0