Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Perhaps exponential performance of sum(listoflists, []) #50105

Closed
sjohn mannequin opened this issue Apr 27, 2009 · 2 comments
Closed

Perhaps exponential performance of sum(listoflists, []) #50105

sjohn mannequin opened this issue Apr 27, 2009 · 2 comments
Labels
interpreter-core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage

Comments

@sjohn
Copy link
Mannequin

sjohn mannequin commented Apr 27, 2009

BPO 5855
Nosy @pitrou
Files
  • testsumflat.py: Performance check - test file (just execute)
    		•

    Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.

    Show more details

    GitHub fields:

    assignee = None
closed_at = <Date 2009-04-27.12:38:33.369>
created_at = <Date 2009-04-27.12:10:46.458>
labels = ['interpreter-core', 'invalid', 'performance']
title = 'Perhaps exponential performance of sum(listoflists, [])'
updated_at = <Date 2009-04-27.12:38:33.345>
user = 'https://bugs.python.org/sjohn'

    bugs.python.org fields:

    activity = <Date 2009-04-27.12:38:33.345>
actor = 'pitrou'
assignee = 'none'
closed = True
closed_date = <Date 2009-04-27.12:38:33.369>
closer = 'pitrou'
components = ['Interpreter Core']
creation = <Date 2009-04-27.12:10:46.458>
creator = 'sjohn'
dependencies = []
files = ['13795']
hgrepos = []
issue_num = 5855
keywords = []
message_count = 2.0
messages = ['86658', '86659']
nosy_count = 2.0
nosy_names = ['pitrou', 'sjohn']
pr_nums = []
priority = 'normal'
resolution = 'not a bug'
stage = None
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue5855'
versions = ['Python 2.5', 'Python 2.4']
    @sjohn
    Copy link
    Mannequin Author

    sjohn mannequin commented Apr 27, 2009

    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...

    @sjohn sjohn mannequin added interpreter-core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage labels Apr 27, 2009
    @pitrou
    Copy link
    Member

    pitrou commented Apr 27, 2009

    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.

    @pitrou pitrou closed this as completed Apr 27, 2009
    @pitrou pitrou added the invalid label Apr 27, 2009
    @ezio-melotti ezio-melotti transferred this issue from another repository Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
    Assignees
    No one assigned
    Labels
    interpreter-core (Objects, Python, Grammar, and Parser dirs) performance Performance or resource usage
    Projects
    None yet
    Milestone
    No milestone
    Development

    No branches or pull requests
    1 participant
    @pitrou