Worin besteht der Sinn der Definition von seen_add = gesehen.add in diesem Itertools-Rezept?

Question

Ich lese die itertools recipe for unique_everseen:

def unique_everseen(iterable, key=None): 
    "List unique elements, preserving order. Remember all elements ever seen." 
    # unique_everseen('AAAABBBCCDAABBB') --> A B C D 
    # unique_everseen('ABBCcAD', str.lower) --> A B C D 
    seen = set() 
    seen_add = seen.add 
    if key is None: 
     for element in filterfalse(seen.__contains__, iterable): 
      seen_add(element) 
      yield element 
    else: 
     for element in iterable: 
      k = key(element) 
      if k not in seen: 
       seen_add(k) 
       yield element 

Was ist der Punkt seen_add = seen.add in dem obigen Code zu definieren?

Answer 1

Leistung. einen lokalen Namen zu verwenden dereferenzieren das Verfahren ist viel schneller als ein Attribut-Lookup (die eine neue Methode Objekt jedes Mal binden):

>>> import timeit 
>>> timeit.timeit('s.add', 's = set()', number=10**7) 
0.4227792940218933 
>>> timeit.timeit('seen_add', 's = set(); seen_add = s.add', number=10**7) 
0.15441945398924872 

eine lokale Referenz zu verwenden ist fast 3 so schnell mal. Da in einer Schleife verwendet wird, lohnt es sich, die Attributsuche zu optimieren.

Answer 2

Das ist eine Technik namens "hoisting" or "Loop-invariant code motion". Im Wesentlichen führen Sie eine Operation aus, die mehrfach ausgeführt wird, aber immer den gleichen Wert außerhalb der Schleife und nicht im Schleifenkörper zurückgibt.

In diesem Fall würde die Schleife das add-Attribut Ihres seen-Satzes wiederholt suchen und eine "gebundene Methode" erstellen. Das ist eigentlich ziemlich schnell, aber immer noch eine Operation, die mehrmals innerhalb einer Schleife ausgeführt wird und immer das gleiche Ergebnis liefert. So können Sie das Attribut (in diesem Fall die gebundene Methode) einmal nachschlagen und es in einer Variablen speichern, um etwas Leistung zu erhalten.

Beachten Sie, dass, während dies eine Beschleunigung bietet, es keineswegs "viel" ist. Ich entfernte den zweiten Zweig für diesen Zeitpunkt den Code kürzer zu machen:

from itertools import filterfalse 

def unique_everseen(iterable): 
    seen = set() 
    seen_add = seen.add 
    for element in filterfalse(seen.__contains__, iterable): 
     seen_add(element) 
     yield element 

def unique_everseen_without(iterable): 
    seen = set() 
    for element in filterfalse(seen.__contains__, iterable): 
     seen.add(element) 
     yield element 

Einige exemplaric Timings:

# no duplicates 
a = list(range(10000)) 
%timeit list(unique_everseen(a)) 
# 5.73 ms ± 279 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 
%timeit list(unique_everseen_without(a)) 
# 6.81 ms ± 396 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 

# some duplicates 
import random 
a = [random.randint(0, 100) for _ in range(10000)] 
%timeit list(unique_everseen(a)) 
# 1.64 ms ± 12.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 
%timeit list(unique_everseen_without(a)) 
# 1.66 ms ± 16.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 

# only duplicates 
a = [1]*10000 
%timeit list(unique_everseen(a)) 
# 1.64 ms ± 78.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 
%timeit list(unique_everseen_without(a)) 
# 1.63 ms ± 24.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 

So, während Sie ~ 10% Speedup in der keine Duplikate erhalten Fall ist es eigentlich fast nutzlos in Falls du viele Duplikate hast.

Eigentlich zeigt dieses Rezept ein anderes Beispiel für "hissen", genauer gesagt die filterfalse(seen.__contains__, iterable). Dies schlägt die Methode Ihres seen einmalig vor und ruft sie wiederholt innerhalb der filterfalse auf.

Vielleicht sollte der Take-Away sein: Hoisting Methode Lookups ist eine Mikro-Optimierung. Es reduziert den konstanten Faktor Ihrer Schleife. Die Beschleunigung mag sich bei bestimmten Operationen lohnen, aber ich persönlich denke, dass sie sparsam und nur in Kombination mit Profiling/Benchmarking eingesetzt werden sollte.