Seite 1 von 1
Laufzeit des in Keywords
Verfasst: Mittwoch 2. Oktober 2013, 10:02
von snow
Hallo, ich bin gerade dabei zu versuchen eine Liste von Wörtern mit einer weiteren Liste von Wörtern zu erweitern. Dabei soll kein Wort der Ausgangsliste hinzugefügt werden, welches bereits enthalten ist. Natürlich bin ich als erstes auf folgende Idee gekommen:
Code: Alles auswählen
for word in words2:
if word not in words:
words.append(word)
Ich bin mir zwar ziemlich sicher, dass das eine Laufzeit von O(n^2) haben wird, konnte aber leider nichts im Netz zu der Laufzeit von "in" finden. Vielleicht kann mir dazu jemand etwas konkretes sagen. Danke schon einmal im Voraus
Re: Laufzeit des in Keywords
Verfasst: Mittwoch 2. Oktober 2013, 10:09
von kbr
Definiere Deine Wortlisten als Sets und vereinige dann diese.
Re: Laufzeit des in Keywords
Verfasst: Mittwoch 2. Oktober 2013, 10:20
von BlackJack
@snow: Bei Listen ist die Laufzeit in der Tat linear. Ansonsten hängt sie von den Typen ab, denn was genau beim ``in``-Operator passiert hängt vom Typ des Objekts auf der rechten Seite ab. Dieses Objekt wird befragt ob das auf der linken Seite enthalten ist. Wie konkret passiert bestimmt der Programmierer des Typs von dem Objekt. Entweder weil er sich entscheidet eine `__contains__()`-Methode zu schreiben, oder das Objekt iterierbar macht.
Re: Laufzeit des in Keywords
Verfasst: Mittwoch 2. Oktober 2013, 12:23
von snow
Ok danke für die Erklärung Blackjack und danke kbr für die Alternative. Werde auf jeden Fall davon Gebrauch machen
