Elemente einer Liste in anderer Liste finden - Multiprocess?

[Stoli]

Hallo zusammen,
ich habe folgenden Code:
Die Elemente aus b werden in a gesucht (nicht nur die genauen Elemente, sondern auch ob sie teilweise enthalten sind).

Code: Alles auswählen

a = ['abc','a b c', 'd f g','zyk', 'z']
b = ['a','z']

lst_neu = [i for e in b for i in a if e in i]
print ("\n".join(map(lambda x: str(x), lst_neu)))

Dieses lst_neu soll für sehr sehr große Listen durchgeführt werden, also Dateien >5MB. Bei einer Testdatei von 0,5MB dauert dieser Vorgang bereits ca. 25sec auf einem Kern.

Ist es möglich diesen Einzeiler auch auf verschiedene Kerne aufzuteilen? Momentan hat mein PC nur 2 Kerne, aber kann das Script auch auf beispielsweise 8 Threads verteilt werden?

Viele grüße,
Stoli

[BlackJack]

@Stoli: Ich würde als erstes mal hinterfragen ob das was Du da programmiert hast wirklich das ist was Du haben möchtest. Dir ist klar das für jedes Element aus der einen Liste jedes Element aus der anderen getestet wird und dadurch Elemente auch *mehrfach* im Ergebnis landen können?

Code: Alles auswählen

In [12]: a = ['abc','a b c', 'd f g','zyk', 'z', 'az']

In [13]: b = ['a','z']

In [14]: lst_neu = [i for e in b for i in a if e in i]

In [15]: lst_neu
Out[15]: ['abc', 'a b c', 'az', 'zyk', 'z', 'az']

Wie man sieht ist 'az' jetzt zweimal im Ergebnis enthalten weil beide Elemente aus `b` in 'az' vorkommen.

Falls das *nicht* so sein soll, kannst Du schon mal Zeit sparen in dem beim ersten Treffer abgebrochen und keine weiteren Elemente aus `b` mehr getestet werden müssen:

Code: Alles auswählen

In [16]: lst_neu = [e for e in a if any(x in e for x in b)]

In [17]: lst_neu
Out[17]: ['abc', 'a b c', 'zyk', 'z', 'az']

Falls es sich tatsächlich um Zeichenketten und ``in``-Tests handelt, könnte es eventuell auch effizienter sein aus den Elementen von `b` einen regulären Ausdruck zu erstellen und mit dem `re`-Modul zu testen. Da ersetzt man dann sozusagen Python-Bytecode durch den `re`-Interpreter in der Hoffnung dass der schneller ist.

Erst wenn das nicht hilft, würde ich zu `multiprocessing` greifen. Wobei man sich klar machen muss, dass das je grösser die Datei wird, man einen grösseren Kommunikationsoverhead und/oder deutlich mehr Speicherverbrauch hat, weil die gleichen Daten aus `a` mehreren Prozessen zur Verfügung stehen müssen.

[sparrow]

Je nach Anwendungsfall könnte ich mir vorstellen, dass auch ein Index Zeit sparen könnte.

Der Aufbau kostet zwar einmalig Zeit, die rentiert sich aber wenn man ihn hinterher mehrmals benutzt.


Gruß
Sparrow

[Stoli]

@BlackJack, dein Vorschlag reduziert die Zeit für den Vorgang natürlich um die Hälfte - super,danke!

Ich will das in einer While True loop durchführen unter einer gewissen Bedingung dann stoppen. Die liste 'b' ändert sich allerdings in der Schleife, 'a' bleibt immer gleich - die größere Liste.

Gibt es vielleicht eine Möglichkeit die Zeit für den Vorgang nochmals zu verringern? Also das Öffnen von 'a' könnte ich ja bereits vor dem Loop machen, aber könnte ich die Liste evtl auch teilweise davor verarbeiten?

Gruß
Stoli

[BlackJack]

@Stoli: Was genau von meinem Vorschlag hast Du denn jetzt probiert? `any()` oder `re`?

Falls die Tests hier tatsächlich dem entsprechen was Du testest, und die Tests nicht nur symbolisch für etwas anderes stehen, könnte man die `a`-Liste in eine Baumstruktur ähnlich eines Suffixbaums überführen. Und hoffen das der Speicher- und Laufzeitmehraufwand den Gewinn nicht auffrist.

[Stoli]

@Stoli: Was genau von meinem Vorschlag hast Du denn jetzt probiert? `any()` oder `re`?

Falls die Tests hier tatsächlich dem entsprechen was Du testest, und die Tests nicht nur symbolisch für etwas anderes stehen, könnte man die `a`-Liste in eine Baumstruktur ähnlich eines Suffixbaums überführen. Und hoffen das der Speicher- und Laufzeitmehraufwand den Gewinn nicht auffrist.

Ich habe jetzt:

Code: Alles auswählen

lst_neu = [e for e in a if any(x in e for x in b)]

verwendet.

Die Sachen 'abc' stehen eher symbolisch für so eine Liste 'a':

Code: Alles auswählen

 a = '    900,        7,        5,      846,      847,     1920,     1922,     1074,     1075,' , '     901,        9,        6,        5,        7,     1918,     1921,     1922,     1920,' , usw.

Diese Liste entsteht durch line.rstrip() aus einer Datei, die fortlaufend (in diesem Fall) von 900-XXX Zeilen nummeriert ist (das entspricht einer "Hexaeder-ID". Die 8 weiterne Zahlen sind Eckpunkte dieser "Hexaeder" und die dazugehörigen "Knoten-IDs"

und 'b' (zufällige Zahlen inkl. eines Kommas!)

Code: Alles auswählen

b = ' 7,' , ' 6,' , ' 1922,' , usw.

Das sind berechnete "Knoten-IDs". Nun möchte ich die Sachen von b (deswegen das Komma) in den jeweiligen Elementen der Liste 'a' finden, es ist ausreichend, wenn ein Element aus b in a vorkommt.

[BlackJack]

@Stoli: Du operierst da auf Zeichenketten die eigentlich für komplexere Datenstrukturen stehen. Das sieht mir nach keiner guten Idee aus, und ausserdem ineffizient. Wenn Du die Zeilen aus `a` tatsächlich in eine Liste mit Zahlen umwandelst, dann kannst Du vor der ``while``-Schleife ein Wörterbuch aufbauen was jede Zahl auf eine Liste mit den Listen mit diesen Zahlen abbildet in denen die jeweilige Zahl vorkommt. Und dann bekommst Du alle Listen auf die eine Zahl zutrifft quasi im Direktzugriff ohne lange danach suchen zu müssen. Wenn die Zeilen aus `a` in Tupel umgewandelt werden, dann könnte man sehr einfach mit `set()` Mehrfachtreffer ausfiltern. Oder man schreibt sich einen Datentyp für so eine Zeile mit entsprechender `__hash__`- und `__cmp__`-Methode falls die erste Zahl innerhalb der Daten eindeutig ist.

Zum Aufbau des Wörterbuchs würde sich `collections.defaultdict()` anbieten.

[snafu]

Code: Alles auswählen

In [16]: lst_neu = [e for e in a if any(x in e for x in b)]

In [17]: lst_neu
Out[17]: ['abc', 'a b c', 'zyk', 'z', 'az']

Alternativ:

Code: Alles auswählen

a = ['abc','a b c', 'd f g','zyk', 'z', 'az']
b = set(['a','z'])
filter(b.intersection, a)

Die `set()`-Variante ist für das obige Beispiel bei mir mehr als doppelt so schnell wie die `any()`-Version. Zudem finde ich sie lesbarer.

[BlackJack]

@snafu: Es mag schneller sein, aber es funktioniert nicht. In `b` sind ja nicht nur einzelne Buchstaben. Hier…

Code: Alles auswählen

In [11]: a = ['abc','a b c', 'd f g','zyk', 'z', 'az']

In [12]: b = set(['a','yk'])

In [13]: filter(b.intersection, a)
Out[13]: ['abc', 'a b c', 'az']

…hätte 'zyk' im Ergebnis sein müssen.

[snafu]

Stimmt, das hatte ich nicht bedacht.

Jedenfalls sollte bezogen auf die eigentlich Aufgabenstellung folgendes funktionieren:

Code: Alles auswählen

#!/usr/bin/env python2
import re

def lines_to_numbers(data):
    for line in data:
        yield map(int, re.findall(r'\d+', line))

def find_matches(data, required_nodes):
    get_intersection = set(required_nodes).intersection
    return filter(get_intersection, lines_to_numbers(data))

def run_test():
    a = [
        '    900,        7,        5,      846,      847,     1920,     1922,     1074,     1075,',
        '    901,        9,        6,        5,        7,     1918,     1921,     1922,     1920,',
        '    902,       42,       23,      104,       96,       11,       55,     1019,     2048,',
    ]
    b = [7, 6, 1922]

    print find_matches(a, b)


if __name__ == '__main__':
    run_test()

Außer, ich habe an der Aufgabe was missverstanden...

[BlackJack]

@snafu: Das sollte funktionieren, da aber mehr als mit nur einem `b` innerhalb einer Schleife `a` mehrfach durchsucht werden soll, ist das *sehr* wahrscheinlich immer noch schlechter als wenn man aus `a` ein Wörterbuch erstellt das die einzelnen Zahlen auf Listen mit Tupeln mit den Zahlen abbildet um dann alle Treffer zu einem Element aus `b` mit einem einfachen Schlüsselzugriff auf das Wörterbuch zu bekommen, statt da immer linear durch ganz `a` zu suchen wobei `a` nach den bisherigen Angaben *mindestens* 50k Elemente hat.

Wenn man einen deutlich effizienteren Algorithmus oder eine Datenstruktur hat, macht es nicht so viel Sinn sich am optimieren der schlechteren Lösung aufzuhalten.

[Stoli]

Danke, snafu & BlackJack für die Hilfe, ich werde mich die nächsten Tage hinsetzen und die effizientere Vorgehensweise suchen

Sobald ich Lösungen hab und auch Performance-Gegenüberstellungen, werde ich berichten!

Viele Grüße,
Stoli

[snafu]

Dann hier nochmal die Variante, wenn sich die zu findenen Knoten-IDs ändern:

Code: Alles auswählen

#!/usr/bin/env python2
import collections
import re

class NodeMatcher(object):
    def __init__(self, data):
        self.matches = collections.defaultdict(list)
        self.store_matches(data)

    def store_matches(self, data):
        for line in data:
            numbers = tuple(int(elem) for elem in re.findall(r'\d+', line))
            for num in numbers:
                self.matches[num].append(numbers)

    def get_matches(self, required_nodes):
        result = set()
        for node_number in required_nodes:
            match = self.matches.get(node_number)
            if match:
                result.update(match)
        return result

def run_test():
    data = [
        '    900,        7,        5,      846,      847,     1920,     1922,     1074,     1075,',
        '    901,        9,        6,        5,        7,     1918,     1921,     1922,     1920,',
        '    902,       42,       23,      104,       96,       11,       55,     1019,     2048,',
    ]
    nodes_to_match = [7, 6, 1922]

    matcher = NodeMatcher(data)
    print matcher.get_matches(nodes_to_match)


if __name__ == '__main__':
    run_test()

Selbstverständlich sollte hier nur einmal eine Instanz des `NodeMatchers` erzeugt werden und auf dieser können dann passende `.get_matches()`-Aufrufe gemacht werden.

Die Initialisierung wird für große Datenmengen sicher recht lange dauern. Folglich sollte man eine mögliche Verteilung auf verschiedene Prozesse (damit mehrere Kerne genutzt werden können) dementsprechend in `.store_matches()` machen. Da können sich die Prozesse dann immer einen ganzen Schwung Zeilen holen und diese verarbeiten. In dem Fall müsstest du darauf achten, dass du keinesfalls nur einzelne Zeilen auf die Prozesse verteilst, denn dann macht der Overhead für die Kommunikation wieder alles zunichte. Sinnvollerweise würden die Prozesse dann vielleicht auch erstmal ihre eigenen `defaultdict`s für die Treffer füllen und am Ende werden die Ergebnisse wieder vereinigt. Das kann alles etwas tricky werden...

[pillmuncher]

Das Ergebnis soll anscheinend die Teilmenge von b sein, für die es Überschneidungen mit Listen aus a gibt. Dazu würde es doch genügen, die Elemente aller Listen aus a in ein set zu packen und dann die Schnittmenge mit b zu bilden, oder nicht?

Und das Einlesen der Datei würde ich mittels des csv-Moduls erledigen, dann müssen nicht Strings durchsucht werden und erst recht nicht irgendwelche Kommas an Suchstrings angefügt werden.

Der Code hätte dann ungefähr diese Struktur:

Code: Alles auswählen

import csv
with open('myfile.txt', r) as myfile:
    myreader = csv.reader(myfile)
    a = set(int(field) for record in myreader for field in record[1:])  # ignore id-field
b = set([7, 6, 1922, ...])
result = a & b

Zum Schluss noch die Frage an Stoli. Du schreibst: "Die liste 'b' ändert sich allerdings in der Schleife" - Warum ändert sich die? Ist das abhängig davon, welche Daten du bereits gesehen hast? Oder sind das Zufallsdaten? Und wenn nun ein neues Element dazukommt, das nur in Listen vorkommt, die bereits durchsucht wurden, aber nicht in den noch zu durchsuchenden - was dann?

Ich denke, es handelt sich hier um ein XY-Problem und du solltest nochmal versuchen zu erklären, was das genaue Ziel deines Programms sein soll, und das solltest du auf nicht-prozedurale Weise erklären. Also nicht sowas wie: "Ich will eine While-True-Schleife programmieren, um Strings, die ich mittels line.rstrip() aus einer Datei...".

[BlackJack]

@pillmuncher: Also ich hatte das so verstanden dass das Ergebnis Zeilen aus `a` sein sollen und nicht nur die einzelnen Zahlen die übereinstimmen.

[snafu]

Das Ergebnis soll anscheinend die Teilmenge von b sein, für die es Überschneidungen mit Listen aus a gibt. Dazu würde es doch genügen, die Elemente aller Listen aus a in ein set zu packen und dann die Schnittmenge mit b zu bilden, oder nicht?

Dann weißt du aber nur, welche der Zahlen irgendwo in den Daten vorkommen. So wie ich die bisherigen Schilderungen verstanden habe, soll aber die Zeile, wo es einen Treffer gab, identifizierbar sein. Wenn ich einfach alle in den Daten vorhandenen Zahlen in ein Set packe, dann geht die Möglichkeit der Identifizierbarkeit verloren.

[pillmuncher]

@BlackJack, @snafu: Achso. Dann vielleicht:

Code: Alles auswählen

import csv
b = set([7, 6, 1922, ...])
with open('myfile.txt', r) as myfile:
    myreader = csv.reader(myfile)
    a = (set(int(field) for field in record[1:]) for record in myreader)
    result = [record for record in a if record & b]

Irgendwie habe ich den Eindruck, dass uns Stoli entscheidende Informationen vorenthält, und dass er in Wirklichkeit eine Pfad- oder Komponentensuche in einem Graph durchführen möchte. Ist jedenfalls meine Vermutung.

[snafu]

@pillmuncher: Hast du deinen Code mal an dem hier gezeigten Beispiel ausprobiert? Die Zeilen enden nämlich mit einem Komma, wodurch der `csv.reader` einen leeren String als letztes Element zurückliefert. Dies führt dann bei der Umwandlung via `int()` zu einem `ValueError`. Man muss daher also immer testen, ob auch tatsächlich ein String mit Inhalt geliefert wurde und nur dann dieses Element als Integer zurückliefern. Oder man nutzt einen regulären Ausdruck, wie ich das gemacht habe, um sich den Test zu ersparen.

Auch deine Idee mit den Sets wurde hier schon geäußert und BlackJack hatte seine berechtigte Kritik bezüglich des Laufzeitverhaltens geäußert, wenn man bedenkt, dass `b` sich anscheinend häufig ändert. Dann macht es nämlich mehr Sinn, in einem Rutsch alle Treffer zu jeder vorkommenden Zahl in einem `dict` zu sammeln (was natürlich entsprechend zeitaufwändig sein kann) und für Abfragen der Treffer dann nur noch dieses `dict` zu verwenden. Falls sich `b` nicht ganz so häufig verändert, dann kann die Set-Variante aber durchaus schneller sein. Das ist aber jetzt ein reines Bauchgefühl, welches erstmal durch Messungen mit realen Daten überprüft werden müsste.

[pillmuncher]

@snafu: Nein, ausprobiert habe ich es nicht. Ich wollte auch nur ungefähr die Struktur des Codes illustrieren und kein fertiges Programm zeigen. Ich dachte, ich hätte das zum Ausdrck gebracht.

Dann also so:

Code: Alles auswählen

...
    a = (set(int(field) for field in record[1:-1]) for record in myreader)
...

Es würde mich auch nicht wundern, falls das abschließende Komma gar nicht in der Datei selbst steht, sondern von Stoli nachträglich angefügt wurde, damit seine Stringsuche funktioniert, bei der er ja ebenfalls je ein Komma anfügt.

Und ja, ich hatte gesehen, dass du schon eine set-Variante gepostet hattest. Sie ist allerdings anders als meine ursprüngliche, die darauf beruhte, dass ich die Frage nicht richtig verstanden hatte. Nachdem ihr mich auf mein Missverständnis aufmerksam gemacht hattet, habe ich meine Lösung modifiziert. Dabei entstand dann etwas, das im Wesentlichen der von dir geposteten und von BlackJack kritisierten Lösung entsprach.

Bzgl. der Änderung von b:

Ich will das in einer While True loop durchführen unter einer gewissen Bedingung dann stoppen. Die liste 'b' ändert sich allerdings in der Schleife, 'a' bleibt immer gleich - die größere Liste.

Wenn sich b in der Schleife ändert, dann vielleicht deswegen, weil die bereits gefundenen Knoten-Oktette zu b hinzugefügt werden sollen. Wie ich schon andeutete, ich vermute, Stoli möchte gar keine Suche nach Übereinstimmungen durchführen, sondern einen Pfad oder eine verbundene Komponente in einem Graphen finden. Sollte das zutreffen, sind die bisherige Diskussion und die geposteten Lösungen ziemlich hinfällig. Eine Lösung, die die mit den Knoten aus b verbundene Komponente erzeugt, ginge ungefähr so:

Code: Alles auswählen

import csv
from collections import defaultdict

def component_connected_with(nodes, neighbors):

    seen = set()

    def component(neighbors=neighbors, seen=seen, see=seen.add):
        todo = set(nodes)
        next_todo = todo.pop
        while todo:
            node = next_todo()
            see(node)
            todo |= neighbors[node] - seen
            yield node

    return set(component())

neighbors = defaultdict(set)
octets = defaultdict(list)

with open('myfile.txt', r) as myfile:
    for record in csv.reader(myfile):
        record = tuple(map(int, record[1:-1]))
        for field in record:
            neighbors[field].update(record)
            octets[field].append(record)

tmp = component_connected_with([7, 6, 1922, ...], neighbors)
result = set(tup for each in tmp for tup in octet[each])

(ungetestet)

[Stoli]

Ich danke euch allen für die Bemühungen und versuche hier jetzt nocheinmal das ganze Schritt für Schritt zu erklären. Ich möchte ein Optimierungstool für ein Programm schreiben, das Spannungen in einem Bauteil berechnet.

Das Bauteil gebe ich einmal über eine endliche Zahl von "Hexaedern" an mit jeweils 8 Knoten, sprich eine endliche Zahl von Zeilen (können aber 50k-100k sein.

Code: Alles auswählen

.
.
   10120,     3549,        7,     1924,     5585,     5571,     1920,     5579,     6574
   10121,     1924,        5,     3548,     5585,     5579,     1922,     5578,     6574
   10122,     3548,      846,     3550,     5585,     5578,     1074,     3906,     6574
   10123,     3550,      847,     3549,     5585,     3906,     1075,     5571,     6574
   10124,     1927,        9,     1926,     5583,     5573,     1918,     5575,     7320
   10125,     1926,        6,     1923,     5583,     5575,     1921,     5580,     7320
   10126,     1923,        5,     1924,     5583,     5580,     1922,     5579,     7320
.
.

Also folgendes Format: 'Hexaeder-ID' | 'Knoten-ID Nr. 1' | 'Knoten-ID Nr. 2' | 'Knoten-ID Nr. 3' | 'Knoten-ID Nr. 4' | 'Knoten-ID Nr. 5' | 'Knoten-ID Nr. 6' | 'Knoten-ID Nr. 7' | 'Knoten-ID Nr. 8'. (Die Kommas am ende jeder Zeile habe ich künstlich danach hinzugefügt um diese Knoten-IDs auch zu finden).
Ich habe den Umweg auch genommen, die Knoten-IDs gehen von 1 bis k .. die Hexaeder-IDs von k+1 bis n. Das ist für den letzten Schritt wichtig - somit werden nur nach den Knoten-IDs gesucht.

Nun fängt die While-True-Loop an.
- Das externe Programm ermittelt jetzt die Spannung an jedem Knoten und gibt folgende symmetrische Spannungsmatrix 3x3 aus:

Code: Alles auswählen

 -1         1 3.84184E-05 3.84278E-05 1.23590E-05 1.04524E-05 2.44347E-06-2.43066E-06
 -1         2 2.99835E+03-9.01701E+04-7.49139E+03-2.51101E+04 1.14856E+02-9.13784E+03
 -1         3 1.52681E+04 7.13507E+03 6.72099E+03-5.53559E+03-5.62050E+02 1.20147E+03
 -1         4-1.54632E+04-7.26260E+03-6.81779E+03-5.62534E+03-5.62893E+02-1.21344E+03
 -1         5-4.52890E+03-7.54432E+02-1.84319E+02-7.18039E+02 3.75005E+01 1.95846E+02
 -1         6-3.76346E+03-8.58813E+02-1.66918E+02-7.73586E+02 3.66762E+01 1.37278E+02
 -1         7-3.95179E+03-1.59346E+02-4.61522E+00-4.69564E+02 9.97944E+00 3.56487E+01
 -1         8-3.20461E+03-8.19883E+02-1.44846E+02-7.59709E+02 3.00482E+01 1.09170E+02
.
.

Dabei entsrpicht hier 1-8 der ID des Knoten und dann die Matrix-elemente. Über eine mathematische Beziehung berechne ich jetzt dann einen Quantitativen Wert 'XA' und speichere ihn in eine temporäre Datei, die folgendermaßen aussieht:

Code: Alles auswählen

-1.73932E-02
 8.24427E-02
 1.00211E-01
 1.22996E-01
 1.52645E-01
 1.88661E-01
 2.07566E-01
 2.40574E-01

Dabei nutze ich den Vorteil, dass die Knoten ab 1 beginnen. jetzt entspricht Zeile 1 dem Wert für Knoten 1, Zeile 2 dem Wert für Knoten 2 usw.

Jetzt berechne ich (XA_0 wird durch den User vorgegeben:

Code: Alles auswählen

if XA_0 <= XA_i:
b.write(' {0:},\n'.format(i+1))

Daraus kann ich jetzt die Ursprüngliche Liste 'b' ermitteln (man sieht hier habe ich die Kommas mit drin) und suche nach den 'Hexaedern'.

Jetzt kommt der vorherige Code:

Code: Alles auswählen

test1 = [e for e in a if any(x in e for x in b)]
#do something to test1

Alle Schritte benötigen 2-3 Sekunden bei einer 0,5-MB Ursprungsdatei. Lediglich der letzte dauert 10 Sekunden und mehr, das steigt proportional zur Dateigröße, genau das möchte ich beschleunigen.

Gruß
Stoli

Und danke für eure Hilfe!