Ankündigung

Einklappen
Keine Ankündigung bisher.

Algorithmus zur Distanzberechnung Laufzeit minimieren

Einklappen

Neue Werbung 2019

Einklappen
X
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • Algorithmus zur Distanzberechnung Laufzeit minimieren

    Ich habe folgendes Problem. Ich habe ein Objekt Buchstabe, welcher aus vielen kleinen Koordinate Objekten besteht die in einem Array gespeichert sind.


    PHP-Code:
    class Buchstabe{

    private 
    $koordinaten = array(); // Jeder Buchstabe kann x mengen an Koordinaten haben die in dem Array gespeichert sind

    }

    class 
    Koordinate{

    private 
    int $x;
    private 
    int $y;



    nun habe ich zwei Buchstaben im Raum und möchte den kürzesten Abstand voneinander berechnen. Sprich ich vergleiche jede Koordinate des einen Buchstaben mit jeder Koordinate des anderen Buchstaben.



    PHP-Code:

    $koordinaten1 
    $buchstabe1->getKoordinaten();
    $koordinaten2 $buchstabe2->getKoordinaten();
    $FinalDistance 10000// Einfach nur ein hoher startwert

    foreach( $koordinaten1 as $k1){
                foreach( 
    $koordinaten2 as $k2){
                  
    $distance distance($k1->getX(),
                                               
    $k1->getY(),
                                               
    $k2->getX(),
                                               
    $k2->getY());
                  if(
    $distance<$Adistance){
                        
    FinalDistance $distance;
                  }
                 }
    }


    function 
    distance(float|int $x1,
                                
    float|int $y1,
                                
    float|int $x2,
                                
    float|int $y2){
            
    $yValue pow($y2-$y12);
            
    $xValue pow($x2-$x12);
            
    $distance =sqrt($yValue+$xValue);
            return 
    $distance;
        } 
    Das funktioniert auch soweit alles. Allerdings habe ich ein riesiges Problem mit der Laufzeit. Ein Buchstabe hat im Durchschnitt 500 Koordinaten. Somit werden bei zwei Buchstaben 250.000 Durchläufe in den Schleifen gemacht- Wenn ich also in einem Text jeden Buchstabe mit dem Nachfolgenden Buchstaben vergleiche komme ich extrem schnell in eine hohe Laufzeit. Gibt es eine andere Möglichkeit das besser zu löesen?

  • #2
    Ein Ansatz: Berechne nicht direkt die Distanz, pow und sqrt sind relativ kostspielig, wenn sie so oft ausgeführt werden. Ich würde erstmal die Koordinaten grob filtern/sortieren.
    Also z.B. Sortierung nach abs(X1 - X2) + abs(Y1 - Y2) und dann die ersten 10% der Liste durcharbeiten oder so, das dürfte die Berechnung schon wesentlich eingrenzen.


    Gibt es sonst weitere Infos zu den Koordinaten die sich irgendwie nutzen lassen? Länder, Seiten, Bereiche, jenachdem wofür die da sind z.B., dass man nach nebeneinanderliegenden Ländern/Bereichen filtern kann oder sowas. Dann gibts auch Maximaldistanzen? Wenn eine Koordinate 1.5/2 ist und die andere 40/40, können dass dann die nähsten sein oder kann man da schon iwie filtern?

    Zusätzlich kannst du noch schauen, ob es vllt bessere Möglichkeiten gibt die Entfernung zu berechnen. Wenn du mit ein paar Prozent Abweichung leben kannst, gibt es vllt noch andere Algorithmen die schneller sind.

    Kommentar


    • #3
      Zitat von jobo Beitrag anzeigen
      Allerdings habe ich ein riesiges Problem mit der Laufzeit. Ein Buchstabe hat im Durchschnitt 500 Koordinaten. Somit werden bei zwei Buchstaben 250.000 Durchläufe in den Schleifen gemacht
      Verwende eine passende Datenbank (vermutlich kommen die Daten eh aus einer DB) und nutze deren Funktionen. PostgreSQL/PostGIS hat z.B. passende und indexbasierte Funktionen zur Berechnung des kürzesten Weges (KNN - Algorithmus).
      PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

      Kommentar


      • #4
        Ich bin mir nicht sicher ob es das ist was du suchst, aber PHPml kann auch eine Klassifizierung nach KNN machen: https://php-ml.readthedocs.io/en/0.4...rest-neighbors

        Kommentar


        • #5
          Mein Ziel ist es Buchstaben so auszurichten, dass die untereinander und seitlich immer die den Gleichen Abstand haben. Das ganze brauche ich für eine Gui die nachher die Buchstaben zeichnet.

          Ich konnte die Laufzeit um fast 80% verringern. Ich habe vor dem zweiten Schleifendurchlauf nochmal eine If abfrage gemacht. mir ist nämlich aufgefallen das die Distance nur voin den X Wert abhängt. Ich vergleiche nämlich vorher in meinem Code nur Koordinaten die den gleichen Y-Wert bei mir haben Wenn also der X-Wert der ersten Koordinate schon größer ist als die Gesamtlänge, brauche ich gar nicht die zweite schleife durchgehen




          PHP-Code:
          $FinalDistance 10000// Einfach nur ein hoher startwert

          foreach( $koordinaten1 as $k1){
                       if(
          $k1<FinalDistance){   // Verhindert  unnötige Schliefen Durchgänge.
                            
          foreach( $koordinaten2 as $k2){
                                        
          $distance distance($k1->getX(),
                                                     
          $k1->getY(),
                                                     
          $k2->getX(),
                                                     
          $k2->getY());
                                        if(
          $distance<$Adistance){
                                               
          FinalDistance $distance;
                                       }
                            }
                      }

          Kommentar

          Lädt...
          X