Vorlesungsskript 23

Tupel und Sets

Wir erinnern uns: Sammeldatentypen sind Datentypen, deren Objekte wiederum mehrere Objekte enthalten können. Bisher haben wir die folgenden Sammeldatentypen kennengelernt:

Typname Sequenziell? Elemente (Werte) Direktzugriff auf Elemente via Veränderlich?
str ja Zeichen Indizes (0, 1, 2…) nein
list ja beliebige Objekte Indizes (0, 1, 2…) ja
dict nein beliebige Objekte Schlüssel (beliebige unveränderliche Objekte) ja

In dieser Vorlesung lernen wir zwei weitere Sammeldatentypen kennen:

Typname Sequenziell? Elemente (Werte) Direktzugriff auf Elemente via Veränderlich?
tuple ja beliebige Objekte Indizes (0, 1, 2…) nein
set nein beliebige unveränderliche Objekte ja

Tupel

Wie Sie in den obigen Tabellen sehen können, sind Tupel wie Listen, nur, dass sie unveränderlich sind. Ist ein Tupel einmal kreiert, bleiben seine Länge und sein Inhalt immer gleich, da kein Element hinzugefügt oder entfernt werden kann.

Tupel-Literale sind wie Listen-Literale, nur mit runden statt eckigen Klammern. Tupel-Literale mit nur einem Element müssen ein Komma enthalten, damit Python sie von einem Ausdruck unterschieden kann, der einfach nur eingeklammert ist:

>>> t = (23, 42)
>>> t
(23, 42)
>>> t[0]
23
>>> t[1]
42
>>> u = (23)
>>> u
23
>>> u[0]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'int' object is not subscriptable
>>> u = (23,)
>>> u
(23,)
>>> u[0]
23

Tupel enthalten also wie Listen beliebig viele Elemente in einer bestimmten Reihenfolge, sind aber nicht veränderlich. Braucht man keine Veränderlichkeit, bietet das Arbeiten mit Tupeln statt mit Listen zum einen den Vorteil, dass man sie nicht aus Versehen verändern kann, und zum anderen, dass Tupel etwas effizienter sind als Listen.

Listen sind oft lang und ihre genaue Länge steht meist erst zur Laufzeit des Programms fest. Typischerweise enthalten sie viele Objekte des gleichen Typs. Z.B. haben wir oft die Wörter eines Romans (alles Strings) in Listen gespeichert, deren genaue Länge von der Inputdatei abhing. Tupel sind dagegen meist kurz und ihre Länge steht von vornherein fest, weil jedes Element eine festgelegte Rolle spielt. Oft haben die Elemente von Tupeln auch unterschiedliche Typen.

Beispiel 1: Minutenangaben

Das folgende Beispiel zeigt eine Liste von Tupeln, die im Programm uhr.py nützlich sein könnte. Jedes Tupel hat zwei Elemente. Das erste ist ein String mit einer ungefähren Minutenangabe auf Deutsch. Das zweite ist eine Ganzzahl, die angibt, bis zu welcher Minute diese Minutenangabe gültig ist:

minutenangaben = [('Punkt', 0),
    ('kurz nach', 7),
    ('gleich zehn nach', 9),
    ('zehn nach', 10),
    ('gleich viertel nach', 14),
    ('viertel nach', 15),
    ('gleich zwanzig nach', 19),
    ('zwanzig nach', 20),
    ('gleich kurz vor halb', 24),
    ('kurz vor halb', 29),
    ('halb', 30),
    ('kurz nach halb', 35),
    ('gleich zwanzig vor', 39),
    ('zwanzig vor', 40),
    ('gleich viertel vor', 44),
    ('viertel vor', 45),
    ('gleich zehn vor', 49),
    ('zehn vor', 50),
    ('gleich kurz vor', 54),
    ('kurz vor', 59)]

Beispiel 2: Namen parsen

Im folgenden Beispiel nimmt die Funktion parse_name einen Namen als Argument, und zwar entweder in der Form Vorname Nachname oder in der Form Nachname, Vorname. In jedem Fall gibt sie ein Tupel (vorname, nachname) zurück. Auch intern benutzt die Funktion Tupel: für jedes der beiden Muster hat sie ein Tupel mit drei Elementen. Das erste ist ein Pattern-Objekt, mit dem das Muster erkannt wird. Das zweite ist die Nummer der Gruppe im regulären Ausdruck, die dem Vornamen entspricht. Und das dritte ist die Nummer der Gruppe im regulären Ausdruck, die dem Nachnamen entspricht:

>>> def parse_name(name):
...    name_formats = [(re.compile('(\w+) (\w+)'), 1, 2),
...                    (re.compile('(\w+), (\w+)'), 2, 1)]
...    for pattern, first_index, last_index in name_formats:
...        match = pattern.match(name)
...        if match:
...            return (match.group(first_index), match.group(last_index))
...    raise ValueError('invalid name format')
...
>>> parse_name('Oprah Winfrey')
('Ophrah', 'Winfrey')
>>> parse_name('Winfrey, Oprah')
('Oprah', 'Winfrey')
>>> parse_name('Oprah')
Traceback (most recent call last):
  File "", line 1, in 
  File "", line 8, in parse_name
ValueError: invalid name format

Wie wir in diesem Beispiel auch sehen, erlauben for-Schleifen es, mehrere Iterationsvariablen zu verwenden. Das ist sehr nützlich, um wie hier über Listen von Tupeln gleicher Länge zu iterieren: jedes Tupel hat drei Elemente, entsprechend verwenden wir drei Iterationsvariablen, in denen die Elemente dann in jedem Schleifendurchlauf gespeichert werden. Auch Variablenzuweisungen unterstützen das gleichzeitige Zuweisen aller Elemente eines Tupels an verschiedene Variablen. Wir können zum Beispiel schreiben:

>>> vorname, nachname = parse_name('Winfrey, Oprah')
>>> vorname
'Oprah'
>>> nachname
'Winfrey'

Sets

Sets (auch Mengen genannt) sind Sammeldatentypen, für deren Elemente das gleiche gilt wie für die Schlüssel von Dictionarys: sie müssen unveränderlich (genauer: hashable) sein, sie sind einzigartig (ein Set kann das gleiche Element nicht zweimal enthalten) und sie liegen in keiner bestimmten Reihenfolge vor. Im Gegensatz zu Dictionary-Keys sind Set-Elementen aber keine Werte zugeordnet.

Set-Literale sind wie Dictionary-Literale von geschweiften Klammern umschlossen. Durch Kommata getrennt stehen darin statt Schlüssel-Wert-Paaren nur einzelne Elemente. Für leere Sets funktioniert das nicht, da {} schon das leere Dictionary erzeugt. Man kann ein leeres Set stattdessen mit der eingebauten set-Funktion erzeugen:

>>> {'Herz', 'Karo', 'Pik', 'Kreuz'}
{'Pik', 'Kreuz', 'Karo', 'Herz'}
>>> {'Herz', 'Herz', 'Karo', 'Pik', 'Kreuz', 'Karo'}
{'Pik', 'Kreuz', 'Karo', 'Herz'}
>>> set()
set()

Sets sind veränderlich. Fügt man einem Set ein Element hinzu, das darin bereits enthalten ist, hat das keinen Effekt: Sets deduplizieren automatisch. Wenn die Reihenfolge der Elemente einer Liste keine Rolle spielt und sie unveränderlich sind, ist es daher sehr einfach, sie zu deduplizieren: einfach die Liste mit der eingebauten set-Funktion in ein Set umwandeln:

>>> names = ['Anna', 'Otto', 'Lara', 'Lara', 'Otto', 'Hans']
>>> set(names)
{'Otto', 'Anna', 'Hans', 'Lara'}

Außer dem automatischen Deduplizieren haben Sets gegenüber Listen vor allem einen Vorteil: der in-Operator, mit dem man prüft, ob ein Element in einer Sammlung vorhanden ist, ist im Allgemeinen bei Sets effizienter als bei Listen:

>>> numbers_list = list(range(10))
>>> numbers_list
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> 6 in numbers_list # 7 Vergleichsoperationen
True
>>> 10 in numbers_list # 10 Vergleichsoperationen
False
>>>
>>> numbers_set = set(range(10))
>>> numbers_set
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
>>> 6 in numbers_set # ca. 1-2 Vergleichsoperationen
>>> 10 in numbers_set # ca. 0-1 Vergleichsoperationen

Während in bei Listen über die Liste iterieren und jedes Element mit dem gesuchten vergleichen muss, bis dieses gefunden wurde oder bis das Ende der Liste erreicht ist, sorgen Sets mit Hilfe von Hashfunktionen dafür, dass sehr viel weniger Vergleiche vorgenommen werden müssen. Das kann bei Sammlungen mit vielen Elementen stark ins Gewicht fallen. Ein Beispiel für ein Programm, das auf diese Weise effizienter gemacht werden kann, ist freq.py. Bisher hat es für jedes Wort im Input-Text geprüft, ob es in der Liste der Stopwörter vorhanden ist. Besser wäre es, die Liste der Stopwörter in ein Set umzuwandeln, da die Prüfung mit in dann effizienter ist.

Vergleichsoperatoren für Sets

Für zwei Sets gibt der Vergleichsoperator == True zurück, wenn sie die gleichen Elemente enthalten, sonst False. Die Reihenfolge spielt dabei natürlich keine Rolle:

>>> {'boy', 'girl'} == {'girl', 'boy'}
True
>>> {'boy', 'boy', 'girl'} == {'girl', 'boy'}
True
>>> {'boy', 'girl'} == {'girl'}
False

Die Operatoren >, <, >= und <= prüfen bei Sets, ob das eine eine (echte) Teilmenge bzw. Obermenge des anderen ist. Zum Beispiel:

>>> {'boy', 'girl'} > {'girl'}
True
{'boy', 'girl'} > {'other'}
False
{'boy', 'girl'} > {'boy', 'girl'}
False
{'boy', 'girl'} >= {'boy', 'girl'}
True

Nicht-destruktive Operationen auf Sets

Hier sind die wichtigsten nicht-destruktiven Operationen für Sets:

Ausdruck Gibt zurück
len(s) Anzahl der Elemente im Set s
x in s True, wenn das Set s das Element x enthält, sonst False
x not in s True, wenn das Set s das Element x nicht enthält, sonst False
s.copy() ein neues Set mit denselben Elementen wie das Set s
list(s) eine Liste mit allen Elementen des Sets s (in willkürlicher Reihenfolge)
set(l) ein Set mit den Elementen des Liste l
a & b die Schnittmenge der Sets a und b, also ein Set mit den Elementen, die in beiden vorkommen
a | b die Vereinigungsmenge der Sets a und b, also ein Set mit allen Elementen, die in einem oder beiden vorkommen
a - b die Differenz der Sets a und b, also ein Set mit allen Elementen von a, die in b nicht vorkommen
a ^ b die symmetrische Differenz der Sets a und b, also ein Set mit allen Elementen, die in genau einem der beiden Sets vorkommen

Destruktive Operationen auf Sets

Und hier die wichtigsten destruktiven:

Anweisung Wirkung
s.add(x) Fügt dem Set s das Element x hinzu.
s.update(xs) Fügt dem Set s alle Elemente der Sammlung xs hinzu.
s.remove(x) Entfernt das Element x aus dem Set s. Ein KeyError tritt auf, wenn das Element nicht vorhanden ist.
s.discard(x) Entfernt das Element x aus dem Set s. Wenn das Element nicht vorhanden ist, passiert nichts.
s.clear() Entfernt alle Elemente aus dem Set s

Zum Beispiel:

>>> sek = {'Tim', 'Lena', 'Anna'}
>>> 'Lena' in sek
True
>>> 'Mona' in sek
False
>>> 'Mona' not in sek
True
>>> sek2 = sek.copy()
>>> sek2.add('Mona')
>>> sek
{'Tim', 'Anna', 'Lena'}
>>> sek2
{'Mona', 'Tim', 'Anna', 'Lena'}
>>> sek.update(sek2)
>>> sek
{'Anna', 'Lena', 'Tim', 'Mona'}
>>> sek2.remove('Mona')
>>> sek2
{'Tim', 'Anna', 'Lena'}
>>> sek2.remove('Mona')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'Mona'
>>> sek2.discard('Mona')
>>> sek2
{'Tim', 'Anna', 'Lena'}
>>> sek2.clear()
>>> sek2
set()
>>> namen_mit_l = {'Lena', 'Laura', 'Ludwig'}
>>> sek
{'Anna', 'Lena', 'Tim', 'Mona'}
>>> sek & namen_mit_l
{'Lena'}
>>> sek | namen_mit_l
{'Laura', 'Anna', 'Lena', 'Ludwig', 'Tim', 'Mona'}
>>> sek - namen_mit_l
{'Mona', 'Tim', 'Anna'}
>>> sek ^ namen_mit_l
{'Mona', 'Ludwig', 'Laura', 'Anna', 'Tim'}