Abstandsberechnung über 2 Listen (Performanceoptimierung)

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.
etienne77
User
Beiträge: 15
Registriert: Freitag 4. März 2005, 18:38
Wohnort: Baden-Württemberg

Abstandsberechnung über 2 Listen (Performanceoptimierung)

Beitragvon etienne77 » Mittwoch 26. Dezember 2007, 19:57

Hallo und frohe Weihnachten,

per Skript suche ich zu Objekten in einer Objektliste die geometrisch nächstgelegene Adresse. Mit 2 for schleifen durch die Listen komme ich auch auf das gewünschte Ergebnis.
Nun möchte die Suche für große Datenmengen noch beschleunigen.
Geht sowas auch mit der map-Funktion?

Code: Alles auswählen

objekte = ((obj_id1, X,Y),(obj_id2,X,Y),(obj_id3,X,Y),(.,.,.))
adressen = ((adr_id1, X,Y),(adr_id2,X,Y),(adr_id3,X,Y),(.,.,.))

ergebnis = [(obj_id1,adr_id2,abstand),(obj_id2,adr_id45,abstand),(.,.,.)]


Ciao
Stefan
schlangenbeschwörer
User
Beiträge: 419
Registriert: Sonntag 3. September 2006, 15:11
Wohnort: in den weiten von NRW
Kontaktdaten:

Beitragvon schlangenbeschwörer » Mittwoch 26. Dezember 2007, 20:08

ja
(Bei genauerer Problembeschreibung und Fragenstellung kann die Antwort dann auch genauer ausfallen)
etienne77
User
Beiträge: 15
Registriert: Freitag 4. März 2005, 18:38
Wohnort: Baden-Württemberg

Beitragvon etienne77 » Samstag 29. Dezember 2007, 09:47

Hallo schlangenbeschwoerer,

also hier ist mein bisheriges Skript:

Code: Alles auswählen

from math import sqrt

def abstand(x1,x2,y1,y2):
    dx = float(x1) - float(x2)
    dy = float(y1) - float(y2)
    return sqrt(dx*dx+dy*dy)

def min_abstand(rechts,hoch,objektliste):
    "Ermittelt die 2 minimalsten Abstaende der Koordinate x,y zu Punkten aus einer Objektliste(id,x,y)"
    min_ab = [(0,100000),()]
    for i in xrange (len(objektliste)):
        dist = abstand(rechts,objektliste[i][1],hoch,objektliste[i][2])
        if dist < min_ab[0][1]:
            min_ab[1] = min_ab[0]
            min_ab[0] = (objektliste[i][0],dist)
        elif dist < min_ab[1][1]:
            min_ab[1] = (objektliste[i][0],dist)
    return min_ab

adressen = ((5001,3473190,5452999),(5002,3473200,5452959),(5003,3475290,5481909),(5004,3470700,5489099),(5005,3474990,5482189),(5006,3474900,5496899),(5007,3474490,5497099))
objekte = (("1c5263",3473201.4,5452986.2),("1c5283",3475286.6,5481886.0),("5e237c",3475008.3,5482203.9),("1b90ae",3470711.4,5489106.9),("3c99ac",3474496.9,5497098.3),("3c99ad",3474497.9,5497086.5))
ergebnis = []

for j in xrange (len(objekte)):
    mapping = min_abstand(objekte[j][1],objekte[j][2],adressen)
    ergebnis.append((objekte[j][0],mapping[0][0], mapping[0][1],mapping[1][0], mapping[1][1]))



Ergebnis:

Code: Alles auswählen

('1c5263', 5001, 17.140595088651626, 5002, 27.236005581029538)
('1c5283', 5003, 23.24994623648336, 5005, 424.00537732445707)
('5e237c', 5005, 23.59872877941276, 5003, 407.82459464863649)
('1b90ae', 5004, 13.869751259621152, 5005, 8134.110791598916)
('3c99ac', 5007, 6.9354163536860245, 5006, 449.67777352233099)
('3c99ad', 5007, 14.787156589369321, 5006, 443.66728524883922)


Ciao
Stefan
BlackJack

Beitragvon BlackJack » Samstag 29. Dezember 2007, 11:33

Als erstes fällt mir auf, dass Du mit Indexen statt Namen arbeitest. Das macht das Programm schwerer verständlich als es sein müsste. So etwas wie ``for i in xrange(len(obj)):`` wobei `i` dann nur als Index für ``obj[i]`` benutzt wird, ist unübersichtlicher als direkt über die Elemente von `obj` zu iterieren und denen einen vernünftigen Namen zu geben.

Das Programm (fast) "indexfrei": http://paste.pocoo.org/show/18242/

Es gibt übrigens keinen "minimalsten" Abstand, sondern nur einen "minimalen". Wobei das bei zwei unterschiedlichen Werten dann eher "die 2 kleinsten Abstände" heissen müsste.

Wer ist online?

Mitglieder in diesem Forum: Bing [Bot]