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