Stringvergleich und Multiprocessing

[Popkultur]

Hallo!

Ich vergleiche eine Dict von Strings miteinander (jedes mit jedem und Unter-Dicts ebenfalls jedes mit jedem). Wenn ein Gleiches gefunden wird, wird eine Funktion aufgerufen, die einen Eintrag in einem anderen dict anlegt. Das Ganze läuft ewig, und leider nur auf einem Prozessor, also nicht skalierbar.

Lässt sich sowas mit multiprocessing beschleunigen? Grade der Stringvergleich mit Funktionsaufruf könnte locker gleichzeitig für mehrere Strings gemacht werden mit mehreren Prozessoren denke ich.

Code: Alles auswählen

                brich = False
                for i in range(0, len(alltokens)):
                    for j in range(i, len(alltokens)):
                        for k in range(0, len(alltokens[i]['subtokens'])):
                            for l in range(0, len(alltokens[j]['subtokens'])):
                                if (len(alltokens[i]['subtokens'][k]['token']) == len(alltokens[j]['subtokens'][l]['token'])):
                                    if (alltokens[i]['subtokens'][k]['token'] == alltokens[j]['subtokens'][l]['token']):
                                        addNode(token)
                                        brich = True
                                if brich: break
                            if brich: break
                        brich = False

[Dav1d]

Ich verstehe deine Frage und Datenstruktur nicht, suchst du Set-Intersection?

Code: Alles auswählen

In [1]: A = set(['a', 'b', 'c'])

In [2]: B = set(['a', 'e', 'f'])

In [3]: C = set(['a', 'g', 'h'])

In [4]: D = set(['i', 'j'])

In [5]: A & B & C
Out[5]: {'a'}

In [6]: A & B & C & D
Out[6]: set()

In [7]: a = {'a': 1}

In [8]: b = {'a': 1, 'b': 2}

In [9]: set(a.items()) & set(b.items())
Out[9]: {('a', 1)}

[BlackJack]

@Popkultur: Das sieht komisch aus. Um es mal vorsichtig auszudrücken.

Diese ganze Laufindizes sind in Python überflüssig, man kann direkt über Elemente von Sequenzen iterieren.

Bei `brich` kommt mir fast das brechen. SCNR. Das sollte weg. Bei den vielen verschachtelten Schleifen könnte man beispielsweise eine Funktion heraus”brechen” (SCNR again) die an der entsprechenden Stelle mit ``return`` verlassen wird.

Die innerste Schleife macht keinen Sinn, da `l` nirgends vewendet wird.

Ich habe mal so die Vermutung, dass man bei den inneren Schleifen was mit Mengen und Mengenoperationen machen kann, um da nicht so viele Schleifendurchläufe zu haben. Und für die äusseren beiden Schleifen gibt's was im `itertools`-Modul.

Edit: Das der Code bereits so weit eingerückt ist, sieht auch nach einem „code smell“ aus.

[BlackJack]

Der ganze Schleifenindex-Wust und die langen Indexzugriffsverkettungen mal beseitigt, sieht das was Du da machst so aus:

Code: Alles auswählen

from itertools import combinations, product
# ...
    for token_a, token_b in combinations(alltokens, 2):
        for subtoken_a, subtoken_b in product(
            token_a['subtokens'], token_b['subtokens']
        ):
            if subtoken_a['token'] == subtoken_b['token']:
                add_node(token)
                break

Dabei gehe ich mal davon aus das wenn die Werte von ``subtoken_a['token']`` und ``subtoken_b['token']`` gleich sind, auch deren Längen gleich sind, und das diese Prüfung implizit das erste ist, was die Objekte bei dem Vergleich intern machen.

Wie man sieht braucht man jetzt kein Flag zu abbrechen mehr. Und nun sollte man noch über die Mengen(operationen) nachdenken.

[Popkultur]

schön und gut, aber ist Deine Variante denn schneller? Ich teste es mal, bezweifle aber, dass es außer schönerer Schreibweise einen großen Einfluss auf die Rechenzeit hat. Die Datenstruktur ist vereinfach gesagt eine Wortliste, wo jedes Wort mit jedem Wort verglichen wird.

[Dav1d]

Die Datenstruktur ist vereinfach gesagt eine Wortliste, wo jedes Wort mit jedem Wort verglichen wird.

Dann sind wir wieder bei Sets/Mengen.

[Popkultur]

komplizierter ausgedrückt wird aber von jedem Wort noch zusätzlich die Silbe verglichen um eine Gemeinsamkeit festzustellen. Die Silben wurden vorher generiert und im dict gespeichert. Ich glaube, das ist im Endeffekt schneller und Speicherintensiver als den Silbenvergleich in die Schleife mit aufzunehmen.

Was wäre, wenn man einen Integer-Hash von den Wörtern berechnet und diesen vergleicht? Müsste doch schneller gehen...

[Dav1d]

Was wäre, wenn man einen Integer-Hash von den Wörtern berechnet und diesen vergleicht? Müsste doch schneller gehen...

Dann sind wir wieder bei Sets/Mengen.

[BlackJack]

@Popkultur: Weniger Python-Bytecode, also ist es auf jeden Fall auch schneller. Und es geht hier auch nicht nur um ”schöner” sondern um *lesbarer*. Deins war viel zu umständlich ausgedrückt, so dass man schlechter verstanden hat was da gemacht wird.

Ungetestet (jetzt sogar ohne ``break``):

Code: Alles auswählen

    for token_a, token_b in combinations(all_tokens, 2):
        if not set(token_a['subtokens']).isdisjoint(token_b['subtokens']):
            add_node(token)

Hier könnte man sich eventuell noch was sparen wenn man die ”subtokens” von vornherein als Mengen speichert.

[Popkultur]

Ja, aber ich sehe bei dir nirgends die Abbruchbedingungen, die einen großen Teil der Schleife verhindern und Zeit sparen. Zum Beispiel den Längenvergleich.

[BlackJack]

@Popkultur: Wo soll denn da ein Längenvergleich etwas bringen? Bei Deinem Code war der überflüssig, hat also *zusätzlich* Zeit gekostet.

[Popkultur]

Ganz einfach. Wenn es zwei Wörter sind, die unterschiedliche Länge haben, braucht man gar nicht erst einen Stringvergleich starten.

[BlackJack]

@Popkultur: Genau darum testet der Stringvergleich das auch bevor er anfängt die Buchstaben zu vergleichen. Wenn Du das vorher explizit selber *noch mal* machst ist das im besten Fall nicht schneller. Da aber zwei Funktionsaufrufe nötig sind (2 × `len()`), ist das real *langsamer*.

Edit:

Code: Alles auswählen

In [20]: %timeit 'abc' == 'foobar'
10000000 loops, best of 3: 37.5 ns per loop

In [21]: %timeit len('abc') == len('foobar')
10000000 loops, best of 3: 109 ns per loop