Abstandsberechnung über 2 Listen (Performanceoptimierung)

[etienne77]

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]

ja
(Bei genauerer Problembeschreibung und Fragenstellung kann die Antwort dann auch genauer ausfallen)

[etienne77]

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]

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`` 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.