unnötige Schlüssel Auswertungen zu vermeiden, wenn eine Liste

Question

Ich habe eine Liste Sortierung, die ich durch mehrere key s sortieren möchten, wie:

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

Das funktioniert gut. Dies führt jedoch zu unnötigen Aufrufen von g, die ich vermeiden möchte (weil sie möglicherweise langsam sind). Mit anderen Worten möchte ich teilweise und träge den Schlüssel auswerten.

Wenn beispielsweise f eindeutig über L ist (d. H. len(L) == len(set(map(f,L)))), sollten keine Aufrufe an g vorgenommen werden.

Was wäre der eleganteste/pythonischste Weg, dies zu tun?

---

Ein Weg, ich denken kann, ist eine benutzerdefinierte Funktion cmp (L.sort(cmp=partial_cmp)) zu definieren, aber IMO ist dies weniger elegant und komplizierter als die key Parameter.

Eine andere Möglichkeit wäre, eine Schlüssel-Wrapper-Klasse zu definieren, die einen Generatorausdruck zum Generieren der verschiedenen Teile des Schlüssels verwendet und die Vergleichsoperatoren überschreibt, um sie einzeln zu vergleichen. Aber ich fühle mich muss es ein einfacherer Weg sein ...

---

EDIT: Ich habe Interesse an einer Lösung für das allgemeine Problem des Sortierens von mehr Funktionen, nicht nur zwei wie in meinem Beispiel über.

Answer 1

eine Funktion gegeben, Sie könnten eine LazyComparer-Klasse wie folgt erstellen:

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) 

Um einen faulen Schlüsselfunktion aus mehreren Funktionen zu machen, könnten Sie eine Nutzenfunktion erstellen:

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

Und zusammen könnten sie wie folgt verwendet werden:

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) 

die

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

ergibt

Der @countcalls Decorator oben wird verwendet, um zu bestätigen, dass wenn f1 eine Menge von Bindungen,zurückgibtwird aufgerufen, um die Bindungen zu brechen, aber wenn f2 eindeutige Werte zurückgibt, wird g nicht aufgerufen.

---

NPE-Lösung fügt memoization innerhalb der Key Klasse. Mit der Lösung oben, Sie memoization außerhalb hinzufügen könnte (unabhängig), um die LazyComparer Klasse:

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) 

, die in weniger Anrufe führt zu g:

10 calls to f1 | 10 calls to g 

Answer 2

können Sie versuchen, itertools.groupby mit:

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 

Eine weitere Möglichkeit, noch weniger elegant, aber an Ort und Stelle:

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) 

Erste Version auf eine beliebige Anzahl von Funktionen verallgemeinert:

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 

Die zweite Version verallgemeinert auf eine beliebige Anzahl von Funktionen (nicht vollständig in obwohl Platz):

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

Sie könnten ein Schlüssel-Objekt verwenden, die gemächlich bewerten würde und Cache 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) 

Hier ist ein Beispiel für die Verwendung:

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