在避免不必要的键求值时对lis进行排序

Question

我有一个要按多个key排序的列表，例如：

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

这个很好用。但是，这会导致对g的不必要调用，我希望避免这种调用（因为它可能很慢）。换句话说，我想部分地、懒惰地评估密钥。在

例如，如果f对L（即len(L) == len(set(map(f,L)))）是唯一的，则不应调用g。在

什么是最优雅/最具Python风格的方式？

---

我能想到的一种方法是定义一个自定义的cmp函数（L.sort(cmp=partial_cmp)），但在我看来，这比使用key参数要简单得多。在

另一种方法是定义一个键包装类，该类接受生成器表达式来生成键的不同部分，并重写比较运算符以逐个进行比较。但是，我觉得一定有一个更简单的方法。。。在

---

编辑：我对通过多个函数进行排序的一般问题的解决方案感兴趣，而不仅仅是上面例子中的两个函数。在

Answer 1

您可以使用一个键对象来延迟求值并缓存g(x)：

class Key(object):
  def __init__(self, obj):
    self.obj = obj
    self.f = f(obj)
  @property
  def g(self):
    if not hasattr(self, "_g"):
      self._g = g(self.obj)
    return self._g
  def __cmp__(self, rhs):
    return cmp(self.f, rhs.f) or cmp(self.g, rhs.g)

下面是一个使用示例：

^{pr2}$

Answer 2

给定一个函数，可以创建如下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)

要从多个函数中生成一个lazy key函数，可以创建一个实用函数：

^{pr2}$

它们一起使用可以这样：

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返回很多 对于ties，调用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

Answer 3

您可以尝试使用^{}：

result = []
for groupKey, group in groupby(sorted(L, key=f), key=f):
    sublist = [y for y in group]
    if len(sublist) > 1:
        result += sorted(sublist, key=g)
    else:
        result += sublist

另一种可能性，甚至不那么优雅，但在适当的地方：

^{pr2}$

第一版通用于任意数量的函数：

def sortBy(l, keyChain):
    if not keyChain:
        return l

    result = []
    f = keyChain[0]
    for groupKey, group in groupby(sorted(l, key=f), key=f):
        sublist = [y for y in group]
        if len(sublist) > 1:
            result += sortBy(sublist, keyChain[1:])
        else:
            result += sublist
    return result

第二个版本一般化为任意数量的函数（但是还没有完全到位）：

def subSort(l, start, end, keyChain):
    part = l[start:end+1]
    sortBy(part, keyChain[1:])
    l[start:end+1] = part

def sortBy(l, keyChain):
    if not keyChain:
        return

    f = keyChain[0]
    l.sort(key = f)

    start = None
    end = None
    for i,x in enumerate(l):
        if start == None:
            start = i
        elif f(x) == f(l[start]):
            end = i
        elif end == None:
            start = i
        else:
            subSort(l, start, end, keyChain)
            start = i
            end = None
    if start != None and end != None:
        subSort(l, start, end, keyChain)