[Python-Dev] sum(...) limitation
Ronald Oussoren
ronaldoussoren at mac.com
Wed Aug 13 16:32:13 CEST 2014
On 12 Aug 2014, at 10:02, Armin Rigo <arigo at tunes.org> wrote:
> 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()).
I wonder why nobody has mentioned previous year’s discussion of the same issue yet: http://marc.info/?l=python-ideas&m=137359619831497&w=2
Maybe someone can write a PEP about this that can be pointed when the question is discussed again next summer ;-)
Ronald
More information about the Python-Dev
mailing list