classification
Title: Perhaps exponential performance of sum(listoflists, [])
Type: performance Stage:
Components: Interpreter Core Versions: Python 2.4, Python 2.5
process
Status: closed Resolution: not a bug
Dependencies: Superseder:
Assigned To: Nosy List: pitrou, sjohn
Priority: normal Keywords:

Created on 2009-04-27 12:10 by sjohn, last changed 2009-04-27 12:38 by pitrou. This issue is now closed.

Files
File name Uploaded Description Edit
testsumflat.py sjohn, 2009-04-27 12:10 Performance check - test file (just execute)
Messages (2)
msg86658 - (view) Author: (sjohn) Date: 2009-04-27 12:10
To flatten lists of lists, e.g. [[0], [1], [2], ...], I found the short
and quite python-like one-liner "sum(listoflists, [])". This, however,
has absolutely awful performance: while the equivalent way of iterating
by hand and extending a flat list is longer and uglier, it performs fast
and in linear time. The sum() variant takes unacceptably long. I do not
know why this should behave worse-than-linear...
msg86659 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2009-04-27 12:38
No wonder it's quadratic (rather than exponential), since summing will
invoke the + operator and therefore produce a new list object at every
iteration.
If you use "f = f + l" in your explicit version, it becomes quadratic too.
History
Date User Action Args
2009-04-27 12:38:33pitrousetstatus: open -> closed

nosy: + pitrou
messages: + msg86659

resolution: not a bug
2009-04-27 12:10:46sjohncreate