Skip to content

GitLab

  • Menu
Projects Groups Snippets
    • Loading...
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
    • Contribute to GitLab
  • Sign in / Register
  • pypy pypy
  • Project information
    • Project information
    • Activity
    • Labels
    • Members
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributors
    • Graph
    • Compare
  • Issues 653
    • Issues 653
    • List
    • Boards
    • Service Desk
    • Milestones
  • Merge requests 13
    • Merge requests 13
  • CI/CD
    • CI/CD
    • Pipelines
    • Jobs
    • Schedules
  • Deployments
    • Deployments
    • Environments
    • Releases
  • Monitor
    • Monitor
    • Incidents
  • Packages & Registries
    • Packages & Registries
    • Container Registry
  • Analytics
    • Analytics
    • Value stream
    • CI/CD
    • Repository
  • Wiki
    • Wiki
  • Snippets
    • Snippets
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
Collapse sidebar
  • PyPy
  • pypypypy
  • Issues
  • #1852

Closed
Open
Created Aug 28, 2014 by Bitbucket Importer@bitbucket_importerMaintainer

sum(arrays,[]) is slow

Created originally on Bitbucket by ant6nd (ant6nd@gmail.com)

sum(strings,"") is very slow (unnecessarily so), but at least there's the "".join(strings) function. when appending a list of arrays together in a similar fashion, there's no join method.

Looping over an array and growing a result array using extend is much faster, but still kind of slow (it appears it's superlinear).

The fastest way seems to be to pre-allocate a result array and copy the values into that, but it's kind of cumbersome.

I feel that sum(arrays,[]) (and incidentally sum(strings,"")) is idiomatic, and pypy should specialize on it. It can also easily avoid re-allocations in theory, compared to using extend. Clearly, the time difference between the different approaches is unreasonable:

some profiling:

#!python


def sumExtend(arrays):
    result = []
    for a in arrays:
        result.extend(a)
    return result

def sumPreallocate(arrays):
    length = sum(len(a) for a in arrays)
    result = [0]*length
    index = 0;
    for a in arrays:
        result[index:index+len(a)] = a
        index += len(a)
    return result

arrays = [[i%10]*i for i in range(10000)]
%time result = sum(arrays,[])
#cancelled after two and half hours ... may take days?

%time _ = sumPreallocate(arrays)
#Wall time: 588 ms

%time _ = sumExtend(arrays)
#Wall time: 1min 42s
To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information
Assignee
Assign to
Time tracking