Wenn wir die Summe einer Liste bilden, bezeichnen wir einen Akkumulator ( memo ) und gehen dann durch die Liste, wobei sie die Binärfunktion "x+y" auf jedes Element und den Akkumulator anwenden. Verfahrenstechnisch sieht das so aus:
def mySum(list):
memo = 0
for e in list:
memo = memo + e
return memo
Dies ist ein gängiges Muster und nicht nur für Summen nützlich - wir können es auf jede binäre Funktion verallgemeinern, die wir als Parameter übergeben, und dem Aufrufer auch erlauben, einen Anfangswert anzugeben. Damit erhalten wir eine Funktion, die als reduce , foldl , oder inject [1] :
def myReduce(function, list, initial):
memo = initial
for e in list:
memo = function(memo, e)
return memo
def mySum(list):
return myReduce(lambda memo, e: memo + e, list, 0)
In Python 2, reduce war eine eingebaute Funktion, aber in Python 3 wurde sie in die functools Modul:
from functools import reduce
Wir können alle möglichen coolen Sachen machen mit reduce abhängig von der Funktion, die wir als erstes Argument angeben. Wenn wir "Summe" durch "Listenverkettung" und "Null" durch "leere Liste" ersetzen, erhalten wir die (oberflächliche) copy Funktion:
def myCopy(list):
return reduce(lambda memo, e: memo + [e], list, [])
myCopy(range(10))
> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Fügen wir eine transform Funktion als weiteren Parameter für copy und wendet es vor der Verkettung an, so erhält man map :
def myMap(transform, list):
return reduce(lambda memo, e: memo + [transform(e)], list, [])
myMap(lambda x: x*2, range(10))
> [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
Fügen wir eine predicate Funktion, die die e als Parameter verwendet und einen booleschen Wert zurückgibt und diesen verwendet, um zu entscheiden, ob verkettet werden soll oder nicht, erhalten wir filter :
def myFilter(predicate, list):
return reduce(lambda memo, e: memo + [e] if predicate(e) else memo, list, [])
myFilter(lambda x: x%2==0, range(10))
> [0, 2, 4, 6, 8]
map y filter sind eine etwas unschöne Art und Weise, Listenauffassungen zu schreiben - wir hätten auch sagen können [x*2 for x in range(10)] o [x for x in range(10) if x%2==0] . Es gibt keine entsprechende Syntax für das Verstehen von Listen für reduce denn reduce muss überhaupt keine Liste zurückgeben (wie wir es bei sum die Python zufällig auch als eingebaute Funktion anbietet).
Es hat sich herausgestellt, dass für die Berechnung einer laufenden Summe die Fähigkeiten zur Listenerstellung von reduce sind genau das, was wir wollen, und wahrscheinlich der eleganteste Weg, um dieses Problem zu lösen, trotz seines Rufs (zusammen mit lambda ) als eine Art unpythonisches Schibboleth. Die Version von reduce das bei seiner Ausführung Kopien seiner alten Werte hinterlässt, heißt reductions o scanl [1] und es sieht so aus:
def reductions(function, list, initial):
return reduce(lambda memo, e: memo + [function(memo[-1], e)], list, [initial])
So ausgerüstet, können wir nun definieren:
def running_sum(list):
first, rest = list[0], list[1:]
return reductions(lambda memo, e: memo + e, rest, first)
running_sum(range(10))
> [0, 1, 3, 6, 10, 15, 21, 28, 36, 45]
Dieser präzise Ansatz ist zwar konzeptionell elegant, funktioniert aber in der Praxis mit Python nur schlecht. Weil Pythons list.append() eine Liste an Ort und Stelle verändert, sie aber nicht zurückgibt, können wir sie nicht effektiv in einem Lambda verwenden und müssen die + stattdessen den Operator. Dadurch wird eine völlig neue Liste erstellt, was Zeit in Anspruch nimmt, die proportional zur Länge der bisher aufgelaufenen Liste ist (also eine O(n)-Operation). Da wir uns bereits innerhalb der O(n) for Schleife von reduce Wenn wir dies tun, erhöht sich die gesamte Zeitkomplexität auf O(n 2 ).
In einer Sprache wie Ruby [2] , wobei array.push e gibt die mutierte array läuft das Äquivalent in O(n)-Zeit:
class Array
def reductions(initial, &proc)
self.reduce [initial] do |memo, e|
memo.push proc.call(memo.last, e)
end
end
end
def running_sum(enumerable)
first, rest = enumerable.first, enumerable.drop(1)
rest.reductions(first, &:+)
end
running_sum (0...10)
> [0, 1, 3, 6, 10, 15, 21, 28, 36, 45]
dasselbe in JavaScript [2] , dessen array.push(e) gibt zurück. e (nicht array ), aber deren anonyme Funktionen erlauben uns, mehrere Anweisungen einzuschließen, die wir verwenden können, um einen Rückgabewert separat anzugeben:
function reductions(array, callback, initial) {
return array.reduce(function(memo, e) {
memo.push(callback(memo[memo.length - 1], e));
return memo;
}, [initial]);
}
function runningSum(array) {
var first = array[0], rest = array.slice(1);
return reductions(rest, function(memo, e) {
return x + y;
}, first);
}
function range(start, end) {
return(Array.apply(null, Array(end-start)).map(function(e, i) {
return start + i;
}
}
runningSum(range(0, 10));
> [0, 1, 3, 6, 10, 15, 21, 28, 36, 45]
Wie können wir also dieses Problem lösen und gleichzeitig die konzeptionelle Einfachheit einer reductions Funktion, die wir gerade übergeben lambda x, y: x + y zu, um die Funktion der laufenden Summe zu erstellen? Lassen Sie uns umschreiben reductions verfahrenstechnisch. Wir können die zufällig quadratisch Problem, und wenn wir schon dabei sind, die Ergebnisliste vorab zuzuweisen, um Heap Thrashing zu vermeiden [3] :
def reductions(function, list, initial):
result = [None] * len(list)
result[0] = initial
for i in range(len(list)):
result[i] = function(result[i-1], list[i])
return result
def running_sum(list):
first, rest = list[0], list[1:]
return reductions(lambda memo, e: memo + e, rest, first)
running_sum(range(0,10))
> [0, 1, 3, 6, 10, 15, 21, 28, 36, 45]
Das ist für mich der richtige Punkt: O(n)-Leistung, und der optimierte prozedurale Code ist unter einem aussagekräftigen Namen versteckt, wo er wiederverwendet werden kann, wenn Sie das nächste Mal eine Funktion schreiben müssen, die Zwischenwerte in einer Liste akkumuliert.
- Die Namen
reduce / reductions stammen aus der LISP-Tradition, foldl / scanl aus der ML-Tradition, und inject aus der Smalltalk-Tradition.
- Pythons
List und Ruby's Array sind beide Implementierungen einer Datenstruktur mit automatischer Größenänderung, die als "dynamisches Array" (oder std::vector in C++). JavaScript ist Array ist ein wenig barocker, verhält sich aber identisch, vorausgesetzt, dass Sie nicht an Indizes außerhalb der Grenzen zuweisen oder mutieren Array.length .
- Das dynamische Array, das den Hintergrundspeicher der Liste in der Python-Laufzeitumgebung bildet, ändert seine Größe jedes Mal, wenn die Länge der Liste eine Zweierpotenz überschreitet. Die Größenänderung einer Liste bedeutet, dass eine neue Liste mit der doppelten Größe der alten Liste auf dem Heap zugewiesen wird, der Inhalt der alten Liste in die neue kopiert wird und der Speicher der alten Liste an das System zurückgegeben wird. Dies ist eine O(n)-Operation, aber da dies immer seltener geschieht, je größer die Liste wird, beträgt die Zeitkomplexität des Anhängens an eine Liste im Durchschnitt O(1). Das "Loch", das die alte Liste hinterlässt, kann jedoch je nach Position im Heap manchmal schwer zu recyceln sein. Selbst mit Garbage Collection und einem robusten Speicherallokator kann die Vorabzuweisung eines Arrays mit bekannter Größe den zugrunde liegenden Systemen einige Arbeit ersparen. In einer eingebetteten Umgebung ohne den Vorteil eines Betriebssystems wird diese Art von Mikro-Management sehr wichtig.
