排序列表

Question

時，我有一個名單，我想通過多key s到進行排序，如避免不必要的主要評價：

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 

Answer 2

您可以嘗試使用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 

另一種可能性，即使是那麼優雅，但地點：

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 

：

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 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) 

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