4. Laufzeitoptimierung

Laufzeitoptimierung

  • O

    Hallo!

    Aktuell muß ich die Zuweisung von Koordinaten zu bestimmten Einträgen mit den "brute force" Ansatz machen, d.h. ich loope durch alle Einträge und suche nach einer Übereinstimmung

    for (i=0;i<AnzEntity;i++){
      for (j=0;j<8;j++){
        if (Entity[i].GID[j] > 0){
          for (k=0;k<AnzGrid;k++){
            if (Entity[i].Module == Grid[k].Module && Entity[i].GID[j] == Grid[k].ID ){
              Entity[i].GIDCoord[j][0] = Grid[k].XYZ[0];
              Entity[i].GIDCoord[j][1] = Grid[k].XYZ[1];
              Entity[i].GIDCoord[j][2] = Grid[k].XYZ[2];
              continue;
            }
          }
        }    
      }
    }

    Für große Datenmengen habe ich da logischerweise ein Laufzeitproblem.
    Kann man den obigen Code noch weiter optimieren?

    Oder hat jemande eine Idee wie man das grundsätzlich anders (=schneller) machen kann als mit den verschachtelten loops?

    0
  • O

    -funroll-loops

    0
  • B

    Ob es besser geht, kann man aus dem Code nicht ablesen, ohne die Struktur der Daten zu kennen. "Grid" deutet irgendwie darauf hin, dass es möglicherweise eine geometrische Struktur gibt?

    oenone schrieb:

    -funroll-loops

    Kann man probieren, das dürfte aber eher kontraproduktiv sein.

    0
  • O

    Bashar schrieb:

    Ob es besser geht, kann man aus dem Code nicht ablesen, ohne die Struktur der Daten zu kennen. "Grid" deutet irgendwie darauf hin, dass es möglicherweise eine geometrische Struktur gibt?

    oenone schrieb:

    -funroll-loops

    Kann man probieren, das dürfte aber eher kontraproduktiv sein.

    Aus der Geometrie kann ich leider nichts zuverlässiges ableiten.

    Würde ich nur auf Entity[i].GID[j] == Grid[k].ID prpüfen wärs einfach:
    Ich lege ein großes Array an und verwende als Index in dem Array Grid[i].ID.
    Dann kann ich bei der Zuweisung Entity[i].GID[j] gleich als Array-Index nehmen.
    Ist zwar Speicherintensiv, dafür "flutscht" es.

    Evt. kann man mit Hashtabellen o.ä. was machen... Aber mir fehlt da eine Idee.

    und ja: -funroll-loops verlangsamt die Schleiferei...

    0
  • ?

    Kannst du uns etwas über die Daten verraten?

    Also Wertebereich (wie gross sind ID, GID), wie statisch die sind bzw. wie oft und wie du sie updatest, etc.

    Wenn man die Liste sortieren könnte wäre binäre Suche gut geeignet.

    Man könnte auch aus Grid[k].Module und Grid[k].ID einen Hash basteln und dann Hashtables verwenden.

    Hängt aber alles davon ab, was garantiert ist und gebraucht wird.

    0
  • O

    bogosort schrieb:

    Kannst du uns etwas über die Daten verraten?

    Also Wertebereich (wie gross sind ID, GID), wie statisch die sind bzw. wie oft und wie du sie updatest, etc.

    Wenn man die Liste sortieren könnte wäre binäre Suche gut geeignet.

    Man könnte auch aus Grid[k].Module und Grid[k].ID einen Hash basteln und dann Hashtables verwenden.

    Hängt aber alles davon ab, was garantiert ist und gebraucht wird.

    Ein kompletter Datensatz besteht aus mehreren Modulen in denen die Eintiäten und die Grids stehen
    - pro Modul stehen die zusammengehörigen Grids und Entitäten zusammen
    - es können Grid und Entitäten IDs von 1-99999999 auftreten
    - die IDs sind nicht fortlaufend nummeriert und auch sonst nicht sortiert
    - es können mehrere hundert Module auftreten
    - jede Module ID ist innerhalb eines Datensatzes eindeutig mit Ausnahme von Modul 0, das eine besondere Rolle spielt
    - die Einlesereihenfolge ist wichtig, da sich die Module-ID aus bestimmten Einträgen ergibt.

    Pseudodatensatz(zum besseren Verständnis mit Zeilennummern):

    01 Entität 1 25
    02 Entität 2 33
    03 Grid 25 1. 2. 3.
    04 Grid 33 1. 2. 3.
    05 Begin Modul 1
    06 Entität 1 25
    07 Grid 25 1. 2. 3.
    08 Entität 2 33
    09 Grid 33 1. 2. 3.
    10 End Modul
    11 Entität 4 34
    12 Grid 34 1. 2. 3.
    13 Grid 66 1. 2. 3.
    14 Entität 5 66

    Jetzt wirds kompliziert:
    Die Entitäten 1 mit Grid 25 (Zeile 01), 2 mit Grid 33 (Zeile 02), 4 mit Grid 34 (Zeile 11) und 5 mit Grid 66 (Zeile 14) gehören zum Modul 0
    Die Entitäten 1 mit Grid 25 (Zeile 06) und 2 mit Grid 33 (Zeile 08) gehören zum Modul 1
    Bei den Grids entsprechend.

    Aber da die Nummerierung nur innerhalb eines Modules eindeutig sein muß, können im Modul 0 und im Modul 1 dieselben IDs auftreten.

    Nun muß die Zuweisung der Grid-Koordinaten zu den Entitäten IDs erfolgen...

    0
  • ?

    Wenn ich das richtig verstanden habe, würde ich das so angehen.

    1. Grids sortieren.

    // Sortiere eine Indexliste
Grid_t *SortedGridPtrs[] = malloc(AnzGrids*sizeof(*SortedGridPtrs));
for (int i=0; i<AnzGrids; i++)
  SortedGridPtrs[i] = &Grid[k];
qsort(SortedGridPtrs, AnzGrid, sizeof(*SortedGridPtrs), compare_grids);

// Wobei die Vergleichsfunktion
int compare_grids(const void *a, const void *b)
{
  const Grid_t *g1 = *(const Grid**)a;
  const Grid_t *g2 = *(const Grid**)b;
  if (g1->Module != g2->Module) return g1->Module - g2->Module;
  if (g1->ID != g2->ID) return g1->ID - g2->ID;
  return (int)(g1-g2); // Sortiere Modul 0 nach der Einlesereihefolge
}

    2. Binäre Suche statt linearer Suche bei deiner Schleife

    for (i=0;i<AnzEntity;i++){
      for (j=0;j<8;j++){
        if (Entity[i].GID[j] > 0){
          Grid_t tmp;
          tmp.ID=Entity[i].GID[j];
          tmp.Module=Entity[i].Module;
          Grid_t *tmpPtr = &tmp;
          Grid_t **Found = bsearch(&tmpPtr, SortedGridPtrs, AnzGrids, sizeof(*SortedGridPtrs), compare_grids);
          if (Found==NULL) continue; // kein passendes Grid
          int k=*Found - Grid;
          // dann dein alter code
          Entity[i].GIDCoord[j][0] = Grid[k].XYZ[0];
          Entity[i].GIDCoord[j][1] = Grid[k].XYZ[1];
          Entity[i].GIDCoord[j][2] = Grid[k].XYZ[2];
        }    
      }
    }

free(SortedGridPtrs);

    (Code ungetestet)

    Mit Hashmaps oder Radix Sort geht es tatsächlich noch schneller, aber O(n log n) sollte eigentlich ausreichend sein, zumal du die Daten ja einlesen musst.

    Ich weiss nicht, wie viel Ahnung du von C und Algorithmen hast, deshalb hier mal eine ausführliche Version. Frag ruhig nach, wenn was unklar ist.

    0
  • O

    Huhä 🙂

    Erstmal danke für den ausführlichen Code.

    bsearch habe ich noch nie benutzt, das muß ich erstmal verstehen.
    Mein Lehrbuch ist da leider sehr kryptisch

    Ich habe noch nicht so ganz durchschaut wonach Du mit qsort sortierst.
    Erst nach Modul ID und dann nach Grid ID vermute ich.

    Wenn ich das korrekt verstanden habe, dann legst Du vorher eine Kopie von Grid in SortedGridPtrs? Siehe allererste for-Schleife. Was ist hier das k? Ich vermute, da sollte i stehen?
    Ehrlicherweise habe ich aber das mit den Zeigern nicht ganz durchschaut... der Adressoperator vor Grid irritiert mich. Vermutlich alles damit besearch korrekt befüllt werden kann?

    Wenn ich i statt k setze, meckert der compiler noch die Zeile mit der Speicherallozierung an: ungültige Initialisierung. Da kann ich mir jetzt keinen Reim drauf machen...

    0
Anmelden zum Antworten