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
    • Planning hierarchy
    • Members
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributors
    • Graph
    • Compare
  • Issues 650
    • Issues 650
    • 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
  • #3732

Closed
Open
Created Apr 28, 2022 by 4atj@4atj

Performance issue with sorting using a key

In PyPy list sorting is 1.6x faster than CPython but using a key PyPy is 4x slower. There is multiple problems in CodeForces that can't be solved using PyPy but can be solved using CPython because of the slow sorting, and some can't be solved by either because CPython is slow.

I found a workaround that is 1.6x faster than PyPy's sorted(with key) but still x2.5 slower than CPython, in case the problem is hard to fix.

def faster_sorted(iterable, key = None, reverse = False):
    if key is None:
        return sorted(iterable, reverse=reverse)

    iterable = list(iterable)
    mapped_iterable = [key(e) for e in iterable]
    dict_mapped_iterable = {}
    for k, v in zip(mapped_iterable,iterable):
        if k in dict_mapped_iterable:
            dict_mapped_iterable[k].append(v)
        else:
            dict_mapped_iterable[k] = [v]
    sorted_mapped_iterable = sorted(mapped_iterable, reverse=reverse)
    return [dict_mapped_iterable[e].pop() for e in sorted_mapped_iterable]

This 2x faster than PyPy's sort() but still x2 slower than CPython. But it doesn't behave exactly like sort(key=key)

def faster_sorted(iterable, key = None, reverse = False):
    if key is None:
        return sorted(iterable, reverse=reverse)
    return [e[1] for e in sorted(((key(e), e) for e in a), reverse=reverse)]
Edited May 16, 2022 by 4atj
To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information
Assignee
Assign to
Time tracking