python - 排序列表时避免不必要的键评估

Question

我有一个列表，我想按多个 key 排序，例如:

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 包装类，它采用生成器表达式来生成 key 的不同部分，并覆盖比较运算符以进行逐一比较。但是，我觉得必须有一个更简单的方法......

---

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

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)