Gemeinsame Punkte meherer Listen bestimmen

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Jeremy
User
Beiträge: 48
Registriert: Samstag 29. November 2008, 19:05

Hallo Python-Gemeinde,
ich arbeite mit der FEM-Software Abaqus und nutze Python als Script-Sprache. Soviel zum Hintergrund.
Mein Problem ist: ich habe mehrere Dateien mit Koordinaten (Tupel der Form (x, y)) vorliegen und möchte diese auf Schnittpunkte miteinander vergleichen. Die Reihenfolge der Koordinatenpaare muss unbedingt erhalten bleiben!
Die Koordinaten habe ich in Listen eingelesen (sieht dann so aus: [(x1, y1), (x2, y2)] usw. ). Die Schnittmenge zwischen den einzelnen Listen in einer neuen Liste speichern. Momentan arbeite ich mit einer if-Bedingung, würde aber lieber mit Mengen arbeiten (Zeitersparnis?!), Problem ist nur, dass bei set und frozenset die Reihenfolge der Koordinatenpaare nicht mehr gegeben ist (die brauche ich aber zum Zeichnen).

Habt ihr einen Tip für mich?
Danke und schönen ersten Advent.
ichbinsisyphos
User
Beiträge: 120
Registriert: Montag 4. Juni 2007, 19:19

Naja, mit sets ist die Reihenfolge dahin ...
Also entweder du verzichtest auf sets oder du machst aus dem set wieder eine Liste und sortierst sie unter Verwendung der alten Liste.

Ist aber wahrscheinlich nur bei extrem langen Listen sinnvoll. Kommt jeder Punkt pro Liste höchstens einmal vor?
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Ob es unter Verwendung von sets zu einer Zeitersparnis kommt, dürfte vom Einzelfall abhängen, da nach meiner Erfahrung gerade set-Operationen nicht zu den schnellsten gehören.

Ich würde es an deiner Stelle einfach mal ausprobieren.

Wie ichbinsisyphos schon angemerkt hat, machst du dir bei Verwendung von sets die Reihenfolge kaputt, aber die ließe sich abschließend ja wieder herstellen, indem du z.B. die kürzeste der Ausgangslisten durchläufst, für jedes Listenelement prüfst, ob es in der Schnittmenge aller sets enthalten ist und damit dann eine neue Liste fütterst.
Jeremy
User
Beiträge: 48
Registriert: Samstag 29. November 2008, 19:05

Zunächst Danke für eure Antworten.
Aus den koordinaten werden in Abaqus Bauteile hergestellt, im Allgemeinen kann eine Liste bis zu 1000 und mehr Koordinatenpaare enthalten. Das Gesamtkonstrukt enthält z.B. 220 Einzelhauteile. Also kommt da schon was zusammen.

@ ichbinsispyphos
Ja, jeder Punkt kommt in einer Liste nur einmal vor

@ numerix
Um die Zeitersparnis zuerfassen, bräuchte ich eine Funktion um den Start und Endezeitpunkt der Schleife/ set-Funktion zu erfassen. Gibt es sowas?
DeJe
User
Beiträge: 39
Registriert: Sonntag 23. November 2008, 19:38

An deiner Stelle würde ich statt der Tuple komplexe Zahlen nutzen.
Beim Einlesen complex(x, y), damit kannst du direkt Differenzen berechnen oder 'in' testen:

Code: Alles auswählen

a = complex(1, 2)
b = complex(2, 4)
c = complex(3, 5)
d = complex(1, 1)
list1 = [a, b, c, d]
e = complex(5, 6)
f = complex(10, 20)
list2 = [e, f, d]
s = [item for item in list1 if item in list2]
Ich hoffe ich habe das richtig verstanden was du vorhast, gleiche Punkte finden und in einer neuen Liste speichern.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Jeremy hat geschrieben:Um die Zeitersparnis zuerfassen, bräuchte ich eine Funktion um den Start und Endezeitpunkt der Schleife/ set-Funktion zu erfassen. Gibt es sowas?

Code: Alles auswählen

import time, platform

timer = time.time if platform.system()=="Linux" else time.clock
t0 = timer()
for k in range(1000000):
    k**0.5
t1 = timer()
print "Dauer: %f Sekunden" %(t1-t0)
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

DeJe hat geschrieben:An deiner Stelle würde ich statt der Tuple komplexe Zahlen nutzen.
Beim Einlesen complex(x, y), damit kannst du direkt Differenzen berechnen oder 'in' testen:
Da es hier nicht um Differenzen geht, kann man Tupel ebenso verwenden wie komplexe Zahlen. Allerdings geht es mit komplexen Zahlen schneller als mit Tupeln:

Code: Alles auswählen

import time, platform
from random import randrange

timer = time.time if platform.system() == "Linux" else time.clock

# using tuples
list1 = [(randrange(99),randrange(99)) for k in xrange(3000)]
list2 = [(randrange(99),randrange(99)) for k in xrange(3000)]
t0 = timer()
intersect = [item for item in list1 if item in list2]
t1 = timer()
print "%i gemeinsame Punkte, Rechenzeit: %f Sekunden" %(len(intersect),t1-t0)

# using complex
list1 = [complex(randrange(99),randrange(99)) for k in xrange(3000)]
list2 = [complex(randrange(99),randrange(99)) for k in xrange(3000)]
t0 = timer()
intersect = [item for item in list1 if item in list2]
t1 = timer()
print "%i gemeinsame Punkte, Rechenzeit: %f Sekunden" %(len(intersect),t1-t0)
Liefert bei mir:

Code: Alles auswählen

752 gemeinsame Punkte, Rechenzeit: 2.254562 Sekunden
808 gemeinsame Punkte, Rechenzeit: 1.462153 Sekunden
Jeremy
User
Beiträge: 48
Registriert: Samstag 29. November 2008, 19:05

@ DeJe,
die Tupel kann ich auch über"in" testen, so mache ich es jetzt. Ja, du hast mich richtig verstanden, es gibt aber noch die Bedingung, dass die Reihenfolge der Punkte erhalten bleiben muss.

Zu deinem Vergleich stellt sich mir noch die Frage, warum unterschiedlich viele gemeinsame Punkte gefunden wurden.


@ numerix,
danke, ich werde es mal ausprobieren.
Zuletzt geändert von Jeremy am Samstag 29. November 2008, 22:19, insgesamt 1-mal geändert.
DeJe
User
Beiträge: 39
Registriert: Sonntag 23. November 2008, 19:38

numerix hat geschrieben:Da es hier nicht um Differenzen geht, kann man Tupel ebenso verwenden wie komplexe Zahlen.
Wieder was gelernt, Tuple kann man auch 'in' testen. Ich bin noch nicht so lange bei Python. ;) Zumindest ist complex aber deutlich fixer. :D
Jeremy hat geschrieben:... es gibt aber noch die Bedingung, dass die Reihenfolge der Punkte erhalten bleiben muss.
Das verstehe ich nicht so richtig. Welche Reihenfolge willst du einhalten? So wie die gleichen Punkte in Liste 1 erscheinen oder in Liste 2 oder was?
Jeremy
User
Beiträge: 48
Registriert: Samstag 29. November 2008, 19:05

Die Punkte in der Liste beschreiben in Wirklichkeit einen Linienzug an dem sich 2 Bauteile berühren. welche Reihenfolge (von Liste 1 oder 2) eingehalten wird, ist egal, da die Punktfolge der Schnittmenge in beiden die gleiche ist.

Komplex ist deulich schneller, stimmt. Später muss ich die Koordinaten wieder als Punkte setzen, brauche also 2mal eine Umformung. Dürfte aber nicht so so lange dauern.
DeJe
User
Beiträge: 39
Registriert: Sonntag 23. November 2008, 19:38

Jeremy hat geschrieben:Später muss ich die Koordinaten wieder als Punkte setzen, brauche also 2mal eine Umformung. Dürfte aber nicht so so lange dauern.
Für die Umformung in kartesische Koordinaten brauchst du doch einfach nur complex.real (ist x) und complex.imag (ist y). Das ist nicht umständlicher als tuple[0] bzw. tuple[1]. ;)
Jeremy
User
Beiträge: 48
Registriert: Samstag 29. November 2008, 19:05

Ja sicher, aber ich kann die Funktion intersect wie im numerix's Beispiel nicht nutzen, da es auch mehr als einen kontaktbereich zwischen 2 Teilem geben kann. Ich tüftele an einem passenden Vorgehen. Mit "in" klappt das schon ganz gut.
BlackJack

@DeJe: ``obj_a in obj_b`` ist sozusagen syntaktischer Zucker für ``obj_b.__contains__(obj_a)``. Ob da nun Tupel, komplexe Zahlen oder sonstwas vor dem ``in`` stehen, ist fast egal, für den Test ist das `list`-Objekt zuständig. Das geht linear seine Elemente durch und vergleicht die mit `obj_a`.
bords0
User
Beiträge: 234
Registriert: Mittwoch 4. Juli 2007, 20:40

numerix hat geschrieben:

Code: Alles auswählen

intersect = [item for item in list1 if item in list2]
kann man ersetzen durch

Code: Alles auswählen

s = set(list2)
intersect = [item for item in list1 if item in s]
Reihenfolge bleibt gleich, Geschwindigkeit ist um Größenordnungen höher.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

bords0 hat geschrieben:
numerix hat geschrieben:

Code: Alles auswählen

intersect = [item for item in list1 if item in list2]
kann man ersetzen durch

Code: Alles auswählen

s = set(list2)
intersect = [item for item in list1 if item in s]
Reihenfolge bleibt gleich, Geschwindigkeit ist um Größenordnungen höher.
Ja, in der Tat - da liegen Welten zwischen.
Interessanterweise wird dann die Tupel-Variante sogar etwas schneller als die complex-Variante.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Jeremy hat geschrieben:Ja sicher, aber ich kann die Funktion intersect wie im numerix's Beispiel nicht nutzen, da es auch mehr als einen kontaktbereich zwischen 2 Teilem geben kann. Ich tüftele an einem passenden Vorgehen. Mit "in" klappt das schon ganz gut.
So zum Beispiel:

Code: Alles auswählen

from random import randrange

# Erzeugung von 20 Listen mit je max. 2000 verschiedenen Punkten
punktlisten = [list(set([(randrange(30),randrange(30)) for k in xrange(2000)])) for i in xrange(20)]

# Erzeugung einer Liste mit gemeinsamen Schnittpunkten in richtiger Reihenfolge
s = set(punktlisten[0])
for liste in punktlisten[1:]:
    s.intersection_update(liste)
schnittpunkte = [punkt for punkt in min(punktlisten) if punkt in s]
Sollte sich das von dir gewünschte "Beibehalten der Reihenfolge" nicht nur auf die Ausgangslisten beziehen, sondern auf das Ergebnis, dann macht das natürlich nur Sinn, wenn in allen deinen Listen die Reihenfolge der gemeinsamen Punkte gleich ist. Falls letzteres nicht zutrifft, müsstest du eine der Listen angeben, die die Reihenfolge vorgibt.
Jeremy
User
Beiträge: 48
Registriert: Samstag 29. November 2008, 19:05

Wenn sich zwei Teile berühren, haben die Punkte in beiden Listen die gleiche Reihenfolge.
Ich habe das Problem mit "in" gelöst und speichere meine Schnittpunkte als Listen in einem dict. Mit der Adressierung über die keys geht das sehr gut. Später kann ich die Listen dann mit dem key aufrufen und zeichnen lassen.

PS: Die Feinheiten von Python kenne ich noch nicht, ich arbeite erst seit ca. 4 Wochen mit Python.

Danke für eure Ratschläge!
Antworten