排序列表时避免不必要的密钥评估

Question

我有一个列表,我想按多个keys 排序,如:

L = [ ... ]
L.sort(key = lambda x: ( f(x), g(x) ))

这很好用.但是,这会导致不必要的调用g,我想避免(因为可能很慢).换句话说,我想部分和懒惰地评估关键.

例如,如果f是唯一的L(即len(L) == len(set(map(f,L))))不g应该进行任何调用.

什么是最优雅/ pythonic的方式来做到这一点？

---

我能想到的一种方法是定义一个自定义cmp函数(L.sort(cmp=partial_cmp)),但IMO比使用key参数更不优雅和复杂.

另一种方法是定义一个key-wrapper类,它使用生成器表达式生成键的不同部分,并覆盖比较运算符以逐个比较.但是,我觉得必须有一个更简单的方法......

---

编辑:我对通过多个函数排序的一般问题的解决方案感兴趣,不仅如上面的例子中的两个.

Answer 1

给定一个函数，您可以创建一个 LazyComparer 类，如下所示：

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)

要从多个函数中创建一个惰性键函数，您可以创建一个实用函数：

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

它们可以一起使用，如下所示：

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) 

这产生

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

上面的 @countcalls 装饰器用于确认当f1返回很多平局时，g被调用来打破平局，但是当f2返回不同的值时， g不会被调用。

NPE 的解决方案在Key类中添加了记忆功能。通过上面的解决方案，您可以在类之外（独立于类）添加记忆LazyComparer：

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)

这会减少对以下内容的调用g：

10 calls to f1 | 10 calls to g