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
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
