[Python-Dev] sum(...) limitation (original) (raw)
Ronald Oussoren ronaldoussoren at mac.com
Wed Aug 13 16:32:13 CEST 2014
- Previous message: [Python-Dev] sum(...) limitation
- Next message: [Python-Dev] [Python-checkins] cpython: Issue #22003: When initialized from a bytes object, io.BytesIO() now
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
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(listofstrings) 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(listoffloats) (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
- Previous message: [Python-Dev] sum(...) limitation
- Next message: [Python-Dev] [Python-checkins] cpython: Issue #22003: When initialized from a bytes object, io.BytesIO() now
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]