[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

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

def make_key(keys):
    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:
                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:
                     return a < b
            return False
    return Key

def bench(description):
    start = time.time()
    stop = time.time()
    print(description.format(stop - start))

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

    data = list(range(N)) + [N, N]
    wanted = list(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

More information about the Tutor mailing list