[Python-Dev] sum(...) limitation

[Armin Rigo]

Hi all,

The core of the matter is that if we repeatedly __add__ strings from a
long list, we get O(n**2) behavior.  For one point of view, the
reason is that the additions proceed in left-to-right order.  Indeed,
sum() could proceed in a more balanced tree-like order: from [x0, x1,
x2, x3, ...], reduce the list to [x0+x1, x2+x3, ...]; then repeat
until there is only one item in the final list.  This order ensures
that sum(list_of_strings) is at worst O(n log n).  It might be in
practice close enough from linear to not matter.  It also improves a
lot the precision of sum(list_of_floats) (though not reaching the same
precision levels of math.fsum()).


Just a thought,

Armin.