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)]
To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information