避免在对列表进行排序时进行不必要的键值评估

Question

我有一个列表，希望按多个关键字排序，例如：

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

这个方法运行良好。但是，这会导致不必要地调用 `g` 函数，我希望避免这种情况（因为这可能会慢）。换句话说，我想要对 key 进行部分和延迟计算。

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

最优雅/pythonic 的方法是什么？

一个我能想到的方法是定义一个自定义的 `cmp` 函数，（`L.sort(cmp=partial_cmp)`），但在我看来，这比使用 `key` 参数更加繁琐、复杂。

另一个方法是定义一个 key-wrapper 类，它接受生成器表达式来生成 key 的不同部分，并覆盖比较运算符以逐个进行比较。但是，我觉得肯定有更简单的方法...

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

- shx2

---

实际上据我所知，“cmp”版本可能比“key”版本慢，因为“key”被评估了N次，而“cmp”被评估了O(log(n)n)次。 - jb.

@jb。Python的排序不是O(nlogn)吗？ - Siegfried Gevatter

@jb 有趣。然而，针对我的具体情况，我们可以假设 g 比比较 f 和 g 的结果慢得多（此外，我可以将结果缓存到包装器对象中）。 - shx2

Answer 1

您可以尝试使用 itertools.groupby 进行操作：

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

还有一种可能性，甚至不太优雅，但也可以实现：

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:
        L[start:end+1] = sorted(L[start:end+1], key=g)
        start = None
if start != None and end != None:
    L[start:end+1] = sorted(L[start:end+1], key=g)

第一个版本可以推广到任意数量的函数：

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)

- BartoszKP

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)

为了将多个函数制作成一个懒惰的键函数，您可以创建一个实用函数：

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

- unutbu

Answer 3

您可以使用一个关键对象来懒惰地评估和缓存 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)

这是一个使用示例：

def f(x):
  f.count += 1
  return x // 2
f.count = 0

def g(x):
  g.count += 1
  return x
g.count = 0

L = [1, 10, 2, 33, 45, 90, 3, 6, 1000, 1]
print sorted(L, key=Key)
print f.count, g.count

- NPE