# [Tutor] lazily decorated sort

Peter Otten __peter__ at web.de
Fri Sep 28 14:17:31 CEST 2012

```Chris Smith wrote:

> I'm wondering if anyone has seen or knows of a good way to do a lazily
> decorated sort. I was reading about how good the DSU (decorate, sort,
> undecorate) approach is but the problem that we are running into in
> SymPy is that we want to get by with a fast hash sort if possible, and
> only decorate to break ties *if necessary*. It's a pity to decorate
> with an expensive function if you don't need it but I don't know how
> to only decorate when there are ties. Do you have any ideas how to do
> the following better:

Here's an implementation that uses the key argument that is supported by
list.sort() and the built-in sorted(). A generator function (keys(value)) is
used to calculate the partial keys as necessary.

import time
import random

from contextlib import contextmanager
from functools import total_ordering

try:
from itertools import izip
except ImportError:
# python 3
izip = zip

def make_key(keys):
@total_ordering
class Key(object):
def __init__(self, value):
self._keys = keys(value)
self._cached = []
def keys(self):
for k in self._cached:
yield k
for k in self._keys:
self._cached.append(k)
yield k
def __eq__(self, other):
return all(a == b for a, b in izip(self.keys(), other.keys()))
def __lt__(self, other):
for a, b in izip(self.keys(), other.keys()):
if a == b:
pass
else:
return a < b
return False

return Key

@contextmanager
def bench(description):
print("starting...")
start = time.time()
yield
stop = time.time()
print(description.format(stop - start))

if __name__ == "__main__":
N = 10
def keys(value):
"""user defined lazy key"""
yield value
time.sleep(.1)
yield random.random()

data = list(range(N)) + [N, N]
wanted = list(data)
random.shuffle(data)

with bench("lazy key: {:.1f}s"):
got = sorted(data, key=make_key(keys))
assert got == wanted

with bench("eager key: {:.1f}s"):
got = sorted(data, key=lambda value: tuple(keys(value)))
assert got == wanted

```