# [Tutor] lazily decorated sort

Chris Smith smichr at gmail.com
Tue Sep 11 13:44:04 CEST 2012

```Hi all,

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:

def f():
"""delay for 2 seconds"""
from time import time
from random import random
t=time()
while time()-t<1:
pass
return random

class foo(object):
"""an object that calls the delay function when comparing"""
def __eq__(self, other):
return f() == f()
def __lt__(self, other):
return f() < f()

def lazyDSU(seq, keys=[]):
"""Return sorted seq, breaking ties by lazily applying keys successively
as needed from the list of provided keys."""
if not keys:
seq = sorted(seq)
else:
d = defaultdict(list)
f = keys.pop(0)
for a in seq:
d[f(a)].append(a)
seq = []
for k in sorted(d.keys()):
if len(d[k]) > 1 and keys:
seq.extend(lazyDSU(d[k], keys=keys[1:]))
else:
seq.extend(d[k])
return tuple(seq)

>>> lazyDSU(range(5)) # fast
(0, 1, 2, 3, 4)
>>> [i[0] for i in lazyDSU(zip(range(5), [foo()]*5))] # fast, no ties
[0, 1, 2, 3, 4]
>>> [i[0] for i in lazyDSU([(0, foo())] + list(zip(range(5), [foo()]*5)))] # slower
[0, 0, 1, 2, 3, 4]

The last run takes 4 seconds (but not 12 seconds) because only two had
to have ties broken.

In the examples, no keys were passed but the discretionary decoration
was demonstrated.

/Chris
```