Python-Optimierung der 3D-Gittersuche mit verschachtelten Schleifen

Question

Stellen Sie sich vor, wir haben ein 3D-Gitter mit diskreten Punkten. Die Bereiche für die drei Dimensionen (einschließlich der Intervallendpunkte) sind:

in x: [4000, 7000], Schrittweite 1000 in y: [0,0, 2,0], Schrittweite 1,0 in z: [-0,75, 0,75], Schrittweite 0.25

Die folgende Aufgabe sollte jetzt für alle Punkte im Bereich [4000, 7000, 100], [0,0, 2,0, 0,1], [-0,75, 0,75, 0,05] (etwa 20000 = 31 * 21 *) durchgeführt werden. 31 Punkte):

Finden Sie den kleinsten Quader, der den Punkt enthält. Allerdings gibt es Löcher im Gitter (jeder Punkt sollte ein "physisches" Gegenstück als Datei haben, aber einige nicht). Ich habe versucht, den folgenden wirklich einfachen Code (wo ich Quader ‚Würfel‘ genannt):

def findcubesnew(startvalues, endvalues, resols, \ 
    loopvalues, refvalues, modelpath): 

    cubearray = [] 
    startvalue1 = startvalues[0] 
    endvalue1 = endvalues[0] 
    resol1 = resols[0] 
    refvalue1 = refvalues[0] 
    loopstop1 = loopvalues[0][0] 
    loopstart1 = loopvalues[1][0] 
    startvalue2 = startvalues[1] 
    endvalue2 = endvalues[1] 
    resol2 = resols[1] 
    refvalue2 = refvalues[1] 
    loopstop2 = loopvalues[0][1] 
    loopstart2 = loopvalues[1][1] 
    startvalue3 = startvalues[2] 
    endvalue3 = endvalues[2] 
    resol3 = resols[2] 
    refvalue3 = refvalues[2] 
    loopstop3 = loopvalues[0][2] 
    loopstart3 = loopvalues[1][2] 
    refmass = refvalues[3] 
    refveloc = refvalues[4] 

    for start1 in numpy.arange(startvalue1, loopstop1 + resol1, resol1): 
    for end1 in numpy.arange(loopstart1, endvalue1 + resol1, resol1): 
     for start2 in numpy.arange(startvalue2, loopstop2 + resol2, resol2): 
     for end2 in numpy.arange(loopstart2, endvalue2 + resol2, resol2): 
      for start3 in numpy.arange(startvalue3, loopstop3 + resol3, resol3): 
      for end3 in numpy.arange(loopstart3, endvalue3 + resol3, resol3): 
       if glob.glob(*start1*start2*start3) and \ 
       if glob.glob(modelpath/*start1*start2*end3) and \ 
       if glob.glob(modelpath/*start1*end2*start3) and \ 
       if glob.glob(modelpath/*start1*end2*end3) and \ 
       if glob.glob(modelpath/*end1*start2*start3) and \ 
       if glob.glob(modelpath/*end1*start2*end3) and \ 
       if glob.glob(modelpath/*end1*end2*start3) and \ 
       if glob.glob(modelpath/*end1*end2*end3): 
        cubearray.append((start1, end1, start2, end2, start3, end3)) 
       else: 
        pass 
    return cubearray 

foundcubearray = findcubesnew([metalstart, tempstart, loggstart], \ 
    [metalend, tempend, loggend], [metalresol, tempresol, loggresol], \ 
    looplimitarray, [refmetal, reftemp, reflogg, refmass, refveloc], \ 
    modelpath) 
if foundcubearray: 
    bestcube = findsmallestcubenew(foundcubearray, \ 
    [metalresol, tempresol, loggresol]) 
    .... 

Daher gehe ich in einer Schleife in x-Richtung von der unteren Gittern Grenze zu dem größten Wert unter dem gewünschten Punkt, wo wir wollen Holen Sie den Quader und in einer anderen Schleife vom kleinsten Wert nach dem Punkt zum höheren Gitterrand. Ähnlich für die y- und die z-Richtung und die Schleifen sind ineinander geschachtelt. Der if-Teil ist ein Pseudocode ohne die Formatzeichenfolgen usw. und prüft, ob alle Dateien mit diesen Werten (und anderen Größen können auch im Dateinamen vorhanden sein) vorhanden sind (dass alle Ecken des Quaders vorhanden sind).

Dieser Code findet auch Punkte oder Linien oder Rechtecke, wenn eine oder mehrere Koordinaten des Punkts mit Werten in unserem Gitter übereinstimmen, aber es ist kein Problem (und eigentlich erwünscht).

Der Flaschenhals hier ist, dass die Suche nach den Quadern ziemlich lange dauert (der kleinste Quader kann einfach und schnell gefunden werden, wenn es mehrere mit derselben (kleinsten) Größe gibt, ist mir egal, welche man wählt) . Außerdem muss ich die Anfangs- und Endwerte des Gitters, die Schrittweiten, die Referenzwerte (Koordinaten) meines Punktes und einige andere Variablen einlesen. Irgendeine Möglichkeit, den Code zu optimieren? Es dauert ungefähr 1,4 Sekunden pro Punkt, also ~ 8 Stunden für die ~ 20000 Punkte und das ist zu lang.

Ich weiß, dass, wenn ich den kleinsten Würfel z. für den Punkt 4500, 0,5, 0,1 kann ich sofort sagen, dass alle anderen Punkte innerhalb des Würfels mit Grenzen [4000, 5000; 0,0, 1,0; 0, 0.25] haben den gleichen kleinsten Quader. Dennoch bin ich an einer Lösung interessiert, die die Berechnungszeit für alle 20000 Läufe optimiert. Die Anwendung davon ist eine Interpolationsroutine für stellare Modelle, bei der 8 Gitterpunkte mit einer Quaderform um den Interpolationspunkt benötigt werden.

P.S .: Ich hoffe, dass die Fortsetzungszeile bricht und Einrückungen korrekt sind. In meinem Code existieren sie nicht, obwohl es kein guter Stil ist, über 80 Zeichen pro Zeile zu gehen :).

Answer 1

Mein Vorschlag ist nicht, glob zu verwenden. Wenn ich die Zahlen richtig lese, könnte das Verzeichnis modelpath bis zu 20.000 Dateien enthalten, und es könnten 8 Globs auf diesen im inneren Schleifenkörper sein. Ich bin überrascht, dass es nur 1,4 Sekunden pro Punkt dauert!

Die Dateinamen werden nur als Booleans verwendet, richtig? Es kommt nur darauf an, ob die Datei existiert oder nicht.

Ich würde ein 3D-Array von Booleans mit den gleichen Dimensionen wie Ihr 3D-Raster, initialisiert auf False erstellen. Lesen Sie dann den Inhalt des Verzeichnisses durch, wandeln Sie jeden Dateinamen in einen 3D-Index um und setzen Sie diesen auf True.

Dann tun Sie Ihre Suche über die Punkte mit dem Array von Booleans, nicht das Dateisystem.

Hoffe, das hilft.