Problem mit verschachtelter for-Schleife

[Bambi]

Hallo liebe User,
zunächst einmal "sorry" wenn das in euren Augen wieder einer dieser Posts von blöden Studenten ist die keine Ahnung haben aber ich habe ein riesen Problem :K

Ich sitze seit Tagen an einem Programm oder besser gesagt an einer Stelle des Programms wo ich echt nicht mehr weiter weiß. Ich werde mal versuchen es so genau zu erklären wie es nur geht:

Das Programm soll aus einer Liste von Nomen jedes Wort überprüfen, ob dieses nochmal in dieser Liste vorkommt, aber diesmal innerhalb eines anderen Wortes. Dieses "andere" Wort was also aus dem überprüften und einem anderen Wort zusammengesetzt ist, soll das Programm in eine neue Liste schreiben.
Nochmal genauer: Also z.B. findet das Programm das Wort "Milch" und wenn jetzt "Vollmilch" auch in dieser Liste der Nomen steht, soll Vollmilch an eine neue Liste angefügt werden.

Den Anfang des Programms habe ich mal weggelassen da es hier eigentlich nur um die Schleife unten geht. Ich habe vorher den Text (ca 250.000 Token) eingelesen, tokenisiert und dann eben eine Liste an Nomen erstellt (ca 20.000, kein Nomen doppelt).


Hier mal der Code:

Code: Alles auswählen

neu = []

for wort in nomen:
    for andereswort in nomen:
        if (andereswort.startswith(wort) or andereswort.endswith(wort.lower())) and andereswort != wort:
            if not andereswort in neu: neu.append(andereswort)

print neu

Das Programm soll also jedes Wort in der Liste Nomen durchgehen, dann soll er für jedes andere Wort in dieser Liste überprüfen, ob dieses Wort mit "wort" beginnt oder aber mit "wort" (kleingeschrieben, da vorher ja groß weil Nomen) endet. Außerdem darf dieses "anderewort" nicht dasselbe Wort sein wie "wort". Das gefundene "anderewort" soll er dann zu einer neuen Liste hinzufügen. Dies klappt auch soweit alles nur leider DAUERT das ganze ca. 20 Minuten. Ich denke dass es an den verschachtelten for-Schleifen liegt da das Programm immer wieder vorne in der Liste beginnt.

Hat evtl. jemand eine Idee woran es liegen könnte dass es soooo lange dauert und was man machen könnte um die for-Schleifen zu vermeiden?

[Sirius3]

Hallo Bambi,

das kannst Du Dir ja selbst ausrechnen:
Bei 20000*20000 Schleifendurchgängen in 20min gibt das ungefähr 1Mio vergleiche pro Sekunde.
Die Komplexität des Problems läßt sich auf n*log(n) reduzieren, wenn Du die Liste der Nomen sortierst,
und zwar von vorne wie von hinten. Das Programm müßte dann unter 1s brauchen.

[Bambi]

Hallo Sirius3,
danke für deine schnelle Antwort.
Was genau meinst du denn mit "von vorne wie von hinten" ? Meinst du damit, dass man gucken soll ob das "wort" einmal vorne in "andereswort" vorkommt und dann gucken ob die Zeichenkette von hinten sortiert in einem zweitem Wort, ebenfalls von hinten gesehen auftritt? Ich hoffe du verstehst was ich damit meine .

Tut mir leid, dass ich solche Umstände bereite.

[Sirius3]

Genau, jedes Wort rückwärts (trow) sortiert, dann unterscheiden sich nämlich die Fälle 'Wort' steht am Anfang und 'wort' steht am Ende nicht mehr, und man muß nur zweimal am Anfang
das Wort 'Wort' bzw. 'trow' suchen, was in einer sortierten Liste, einem Suchbaum, etc., mit log(n) Komplexität geht.

[Bambi]

Ok gut ich werde das direkt mal ausprobieren.
Nochmal tausend Dank für die schnelle Hilfe

Liebe Grüße,
Bambi