Listen-Abstraktion (List Comprehension)

Einführung

alternative to map, filter, reduce and lambda Im vorigen Kapitel über lambda, filter, reduce and map haben wir erfahren, dass Guido van Rossum diese nicht mag. Stattdessen bevorzugt er die Listen-Abstraktion, die meist auch im Deutschen als "List Comprehension" bezeichnet wird. Die Listen-Abstraktion wurde mit der Version 2.0 in Python eingeführt.

Die Listen-Abstraktion, eigentlich auch im Deutschen besser als "List Comprehension" bekannt, ist eine elegante Methode Mengen in Python zu definieren oder zu erzeugen. Die List-Comprehension kommt der mathematischen Notation von Mengen sehr nahe. In Mathematik definiert man die Quadratzahlen der natürlichen Zahlen beispielsweise als { x2 | x ∈ ℕ } oder die Menge der komplexen ganzen Zahlen { (x,y) | x ∈ ℤ ∧ y ∈ ℤ }.
Die Listen-Abstraktion kann man als vollständigen Ersatz für den Lambda-Operator, sowie die Funktionen map, filter und reduce ansehen. Die Syntax der List-Comprehension ist im allgemeinen leichter verständlich.

Beispiele

Im Abschnitt über die map-Funktion hatten wir die Wandlung einer Liste mit Werten in Grad Celsius in Fahrenheit-Werte mit der map-Funktion gelöst. Mit der List-Comprehension lässt sich dies sehr einfach lösen:
>>> Celsius = [39.2, 36.5, 37.3, 37.8]
>>> Fahrenheit = [ ((float(9)/5)*x + 32) for x in Celsius ]
>>> print Fahrenheit
[102.56, 97.700000000000003, 99.140000000000001, 100.03999999999999]
>>> 
Ebenso leicht lassen sich auch die pythagoreischen Tripel mittels der List-Comprehension berechnen, wie das folgende Beispiel zeigt:
>>> [(x,y,z) for x in range(1,30) for y in range(x,30) for z in range(y,30) if x**2 + y**2 == z**2]
[(3, 4, 5), (5, 12, 13), (6, 8, 10), (7, 24, 25), (8, 15, 17), (9, 12, 15), (10, 24, 26), (12, 16, 20), (15, 20, 25), (20, 21, 29)]
>>> 
Im folgenden Beispiel berechnen wir das Kreuzprodukt aus zwei Mengen:
>>> colours = [ "red", "green", "yellow", "blue" ]
>>> things = [ "house", "car", "tree" ]
>>> coloured_things = [ (x,y) for x in colours for y in things ]
>>> print coloured_things
[('red', 'house'), ('red', 'car'), ('red', 'tree'), ('green', 'house'), ('green', 'car'), ('green', 'tree'), ('yellow', 'house'), ('yellow', 'car'), ('yellow', 'tree'), ('blue', 'house'), ('blue', 'car'), ('blue', 'tree')]
>>> 

Anspruchsvolleres Beispiel

Berechnung der Primzahlen bis 100 nach dem Sieb des Sieb des Eratosthenes:
>>> noprimes = [j for i in range(2, 8) for j in range(i*2, 100, i)]
>>> primes = [x for x in range(2, 100) if x not in noprimes]
>>> print primes
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
>>> 
Das vorige Beispiel wollen wir nun in einer etwas allgemeineren Form schreiben, damit es die Primzahlen für eine beliebige Zahl n berechnet:
>>> from math import sqrt
>>> n = 100
>>> sqrt_n = int(sqrt(n))
>>> no_primes = [j for i in range(2,sqrt_n) for j in range(i*2, n, i)]
Wenn wir uns no_primes ausgeben lassen erkennen wir, dass es bei der Konstruktion dieser Liste ein Problem gibt. Diese Liste beinhaltet Doppeleinträge, was die Berechnung der Liste der Primzahlen ineffizient werden lässt, da auch alle Doppeleinträge jeweils betrachtet werden müssen:
>>> no_primes
[4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 96, 99, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, 80, 84, 88, 92, 96, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, 78, 84, 90, 96, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99]
>>>
Am besten wäre es diese Doppeleinträge bereits gar nicht zu erzeugen. Dazu müsste man jedoch in der List Comprehension auf die Liste zugreifen können, die gerade erzeugt wird. Dies ist mittels eines Tricks möglich. Der Interpreter benutzt während der Erzeugung der List-Comprehension eine interne Variable, die eine Referenz auf die Liste ist:
locals()['_[1]'] 
Mittels dieser Systemvariablen lässt sich nun die Berechnung der no_primes ohne Doppeleinträge bewerkstellen:
>>> no_primes = [j for i in range(2,sqrt_n) for j in range(i*2, n, i) if j not in locals()['_[1]']]
>>> no_primes
[4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 9, 15, 21, 27, 33, 39, 45, 51, 57, 63, 69, 75, 81, 87, 93, 99, 25, 35, 55, 65, 85, 95, 49, 77, 91]

Rekursive Funktion zur Berechnung der Primzahlen

Eine effizientere Berechnung der Primzahlen bis zu einer natürlichen Zahl n stellen wir in der folgenden rekursiven Implementierung in Python vor. Wir berücksichtigen darin, dass man sich nur die Vielfachen der Primzahlen von 1 bis zur Quadradwurzel von n anschauen muss:
from math import sqrt
def primes(n):
	if n == 0:
		return []
 	elif n == 1:
  		return [1]
	else:
	 	p = primes(int(sqrt(n)))
   	no_p = [j for i in p for j in range(i*2, n, i) if j not in locals()['_[1]']]
   	p = [x for x in range(2, n) if x not in no_p]
	return p