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 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 extrem 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]
>>>
Die Lösung für dieses nicht akzeptable Verhalten besteht in der Mengen-Abstraktion, die wir im nächsten Abschnitt behandeln werden.

Mengen-Abstraktion (set comprehension)

Die Mengen-Abstraktion (set comprehension) verhält sich analog zur Listen-Abstraktion (list comprehension), aber sie liefert - wie der Name andeutet - eine Menge und nicht eine Liste zurück. Zur syntaktischen Unterscheidung zur Listen-Abstraktion benutzen wir geschweifte Klammern, also "richtige Mengenklammern".

Mit der Mengen-Abstraktion sind wir nun in der Lage das vorige Problem zu lösen, also die Nicht-Primzahl ohne Doppelte zu kreieren: 
>>> 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)}
>>> no_primes
{4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 98, 99}
>>> primes = {i for i in range(n) if i not in no_primes}
>>> print(primes)
{0, 1, 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}
>>>


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