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 der 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.7, 99.14, 100.03999999999999]
>>> 
Ein pythagoreisches Tripel oder pythagoreisches Zahlentripel besteht aus drei positiven ganzen Zahlen mit der Eigenschaft
a2 + b2 = c2.
Ein solches Tripel wird üblicherweise mit (a, b, c) notiert. Ein Beispiel stellen die Zahlen 3,4 und 5 dar, also das Tripel (3, 4, 5).
Die pythagoreischen Tripel lassen sich leicht mittels 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')]
>>> 



Generatoren-Abstraktion (generator comprehension)

"Generator comprehension" wurde mit Python 2.6 eingeführt. Sie sehen wie Listen-Abstraktionen aus, außer, dass sie in runde KLammern statt in eckige Klammern eingebettet sind. Ansonsten ist die Syntax gleich wie bei der "list comprehension", aber es wird ein Generator statt einer Liste zurückgeliefert.
>>> x = (x **2 for x in range(20))
>>> print(x)
<generator object <genexpr> at 0xb7307aa4>
>>> x = list(x)
>>> print(x)
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361]


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 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.

Mengen-Abstraktion

Die Mengen-Abstraktion, auch Mengen-Comprehension (set comprehension) genannt, verhält sich analog zur Listen-Abstraktion (list comprehension), aber sie liefert - wie der Name andeutet - eine Menge und nicht eine Liste zurück. Als syntaktische 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 erzeugen:
>>> 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 beliebigen 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 []
    else:
        p = primes(int(sqrt(n)))
        no_p = {j for i in p for j in range(i*2, n+1, i)}
        p = {x for x in range(2, n + 1) if x not in no_p}
    return p

for i in range(1,50):
    print(i, primes(i))


Unterschiede zwischen den Python-Versionen 2.x and 3.x

In den 2.x-Versionen von Python ist die Kontrollvariable einer Abstraktion, egal ob Listen- oder Mengenabstraktion, nicht lokal. Existiert eine Variable gleichen Namens außerhalb der Abstraktion, kann und wird im allgemeinen deren Wert nach Anwendung der Abstraktion verändert sein. Wir demonstrieren dies im folgenden Beispiel:
>>> x = "This value will be changed in the list comprehension"
>>> res = [x for x in range(3)]
>>> res
[0, 1, 2]
>>> x
2
>>> res = [i for i in range(5)]
>>> i
4
>>> 

Guido van Rossum bezeichnete diesen Effekt als "eines der 'kleinen dreckigen Geheimnisse' seit Jahren".1 Der Grund für diese Vorgehensweise war Effizienz. "Es begann als absichtlicher Kompromiss, um die Listenabstraktion berauschend schnell zu machen, und obwohl es kein üblicher Fallstrick für Anfänger war, traf es gelegentlich Leute schmerzlich" 2

Dieses "dreckige kleine Geheimnis" ist in Python3 behoben, wie man im folgenden Code sehen kann:
$ python3
Python 3.2 (r32:88445, Mar 25 2011, 19:28:28) 
[GCC 4.5.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> x = "Python 3 fixed the dirty little secret"
>>> res = [x for x in range(3)]
>>> print(res)
[0, 1, 2]
>>> x
'Python 3 fixed the dirty little secret'
>>> 


Footnotes:

1 Guido van Rossum: From List Comprehensions to Generator Expressions
wörtlich: "one of Python's 'dirty little secrets' for years"

2 dto.
wörtlich: "It started out as an intentional compromise to make list comprehensions blindingly fast, and while it was not a common pitfall for beginners, it definitely stung people occasionally."