Avoiding unnecessary key evaluations when sorting a list

lazy-evaluation, python, python-2.7, sorting

Solution

Given a function, you could create a LazyComparer class like this:

def lazy_func(func):
    class LazyComparer(object):
        def __init__(self, x):
            self.x = x
        def __lt__(self, other):
            return func(self.x) < func(other.x)
        def __eq__(self, other):
            return func(self.x) == func(other.x)
    return lambda x: LazyComparer(x)

To make a lazy key function out of multiple functions, you could create a utility function:

def make_lazy(*funcs):
    def wrapper(x):
        return [lazy_func(f)(x) for f in funcs]
    return wrapper

And together they could be used like this:

def countcalls(f):
    "Decorator that makes the function count calls to it."
    def _f(*args, **kwargs):
        _f._count += 1
        return f(*args, **kwargs)
    _f._count = 0
    return _f

@countcalls
def g(x): return x

@countcalls
def f1(x): return 0

@countcalls
def f2(x): return x

def report_calls(*funcs):
    print(' | '.join(['{} calls to {}'.format(f._count, f.func_name)
                      for f in funcs]))

L = range(10)[::-1]

L.sort(key=make_lazy(f1, g))
report_calls(f1, g)

g._count = 0
L.sort(key=make_lazy(f2, g))
report_calls(f2, g)

which yields

18 calls to f1 | 36 calls to g
36 calls to f2 | 0 calls to g

The @countcalls decorator above is used to connfirm that when `f1` returns a lot of ties, `g` is called to break the ties, but when `f2` returns distinct values, `g` does not get called.

NPE's solution adds memoization within the `Key` class. With the solution above, you could add memoization outside (independent of) the `LazyComparer` class:

def memo(f):
    # Author: Peter Norvig
    """Decorator that caches the return value for each call to f(args).
    Then when called again with same args, we can just look it up."""
    cache = {}
    def _f(*args):
        try:
            return cache[args]
        except KeyError:
            cache[args] = result = f(*args)
            return result
        except TypeError:
            # some element of args can't be a dict key
            return f(*args)
    _f.cache = cache
    return _f

L.sort(key=make_lazy(memo(f1), memo(g)))
report_calls(f1, g)

which results in fewer calls to `g`:

10 calls to f1 | 10 calls to g

Problem

I have a list which I want to sort by multiple `key`s, like: ``` L = [ ... ] L.sort(key = lambda x: ( f(x), g(x) )) ``` This works fine. However, this results with unnecessary calls to `g`, which I would like to avoid (for being potentially slow). In other words, I want to partially and lazily evaluate the key. For example, if `f` is unique over `L` (i.e. `len(L) == len(set(map(f,L)))`) no calls to `g` should be made. What would be the most elegant/pythonic way to do this? One way I can think of is to define a custom `cmp` function (`L.sort(cmp=partial_cmp)`), but IMO this is less elegant and more complicated than using the `key` parameter. Another way would be to define a key-wrapper class which takes a generator expression to generate the different parts of the key, and override the comparison operators to compare one-by-one. However, I'm feeling there must be a simpler way... EDIT: I'm interested in a solution for the general problem of sorting by multiple functions, not only two as in my example above.

Original source