Abschlussprojekt FIAE (Optimierung von Algorithmen) -> Vergleich von Polygonen

[TiGü]

Zitat von Gyrospeter:

Zitat von TiGü:

Bei RemoveIdenticalFromList musst du anhand deiner Testdaten prüfen, wie oft es wirklich vorkommt, dass wirklich doppelte und aufeinanderfolgende Einträge existieren.

Durch das Delete wird TListHelper.InternalDoDeleteN aufgerufen und das sorgt durch den Move Befehl für teure Speicheroperationen.
Vielleicht wäre hier ein Ansatz mit temporärer Liste mit vor initialisierter Länge besser, in der du nur die Elemente packst, die nicht doppelt sind.

Das ist eine gute Idee, müsste also dementsprechend nur jedes Element einzeln in die neue Liste packen und die Capacity der temporären Liste vordefinieren. Wie weiß ich denn dennoch, wie viele Elemente ich da reinpacken muss? Oder muss ich die Capacity nach jedem neu hinzugefügten Element um 1 erweitern?

Die Capacity der temporären Liste würde ich so wählen, dass ohne große Neuallokation von Speicher der Inhalt der zu überprüfenden Liste reinpasst.
Also NewCapacity := Round(1.5 * OldList.Count) so als Startwert, man kann sich rantasten.
Damit ist der Platz schonmal vor reserviert und es kann ja durchaus vorkommen, dass keine Doppelungen vorkommen.
Immer wenn not IsListItemEqual dann wahr wird, kann der aktuelle Eintrag hinzugefügt werden.

[Gyrospeter]

Zitat von TiGü:

Die Capacity der temporären Liste würde ich so wählen, dass ohne große Neuallokation von Speicher der Inhalt der zu überprüfenden Liste reinpasst.
Also NewCapacity := Round(1.5 * OldList.Count) so als Startwert, man kann sich rantasten.
Damit ist der Platz schonmal vor reserviert und es kann ja durchaus vorkommen, dass keine Doppelungen vorkommen.
Immer wenn not IsListItemEqual dann wahr wird, kann der aktuelle Eintrag hinzugefügt werden.

Reicht es nicht einfach die NewCapacity einfach auf OldList.Count zu setzen, immerhin wird die neue Liste nie größer werden als die alte Liste, nur kleiner?
Deshalb zu Beginn mit NewCapacity := OldList.Count allokieren und nach dem Hinzufügen ein TrimExcess?
Oder sollte die Allokation besser blockweise (256, 512, 1024) geschehen?

[Stevie]

Ein paar Anmerkungen:
Es benötigt ein bisschen mehr als den oben von dir skizzierten Test, denn diese Testdaten verursachen nicht die durchaus teuren Operationen in deinem Code (z.B. Liste rotieren)
Generell sei gesagt, dass es nur schneller werden kann, wenn du auf die temporäre Liste verzichtest und sowohl identische Vektoren als auch unterschiedliche Startpositionen direkt abhandelst.

Bei Code, der auf jeden Fall garantiert, dass du auf gültige List Indizes zugreifst (durch eine 0 to Count-1 Schleife gegeben), kann es durchaus einen kleinen Schub geben, wenn du AList.List[i] benutzt, dadurch wird der getter übergangen, der noch einen Index in range check durchführt und deshalb obwohl geinlined den Code etwas aufbläht.

IsListItemEqual auf jeden Fall als inline markieren (daran denken, diese Funktion vor die anderen zu setzen, da der Compiler nur dann wirklich inlined)


Zum Profilen würde ich dir SamplingProfiler für den Anfang empfehlen (funktioniert am besten mit map file also unter Projektoptionen->Compiler->Linking diese auf detailed setzen). Obwohl der Profiler in der Oberfläche die neusten Delphi Versionen nicht auflistet funktioniert er tadellos. Für Fortgeschrittene empfehle ich Intel VTune (oder uProf, sollte man eine AMD CPU haben, das ist aber nicht ganz so cool wie VTune), dafür muss man aber eine pdb Datei erzeugen, dafür benötigt man map2pdb.

Zum Benchmarken möchte ich benchmark empfehlen, damit kannst du sehr einfach verschiedene Tests bauen, ohne groß mit Stopwatch und Co zu messen.

[Gyrospeter]

Zitat von Stevie:

Ein paar Anmerkungen:
Es benötigt ein bisschen mehr als den oben von dir skizzierten Test, denn diese Testdaten verursachen nicht die durchaus teuren Operationen in deinem Code (z.B. Liste rotieren)
Generell sei gesagt, dass es nur schneller werden kann, wenn du auf die temporäre Liste verzichtest und sowohl identische Vektoren als auch unterschiedliche Startpositionen direkt abhandelst.

Bei Code, der auf jeden Fall garantiert, dass du auf gültige List Indizes zugreifst (durch eine 0 to Count-1 Schleife gegeben), kann es durchaus einen kleinen Schub geben, wenn du AList.List[i] benutzt, dadurch wird der getter übergangen, der noch einen Index in range check durchführt und deshalb obwohl geinlined den Code etwas aufbläht.

IsListItemEqual auf jeden Fall als inline markieren (daran denken, diese Funktion vor die anderen zu setzen, da der Compiler nur dann wirklich inlined)


Zum Profilen würde ich dir SamplingProfiler für den Anfang empfehlen (funktioniert am besten mit map file also unter Projektoptionen->Compiler->Linking diese auf detailed setzen). Obwohl der Profiler in der Oberfläche die neusten Delphi Versionen nicht auflistet funktioniert er tadellos. Für Fortgeschrittene empfehle ich Intel VTune (oder uProf, sollte man eine AMD CPU haben, das ist aber nicht ganz so cool wie VTune), dafür muss man aber eine pdb Datei erzeugen, dafür benötigt man map2pdb.

Zum Benchmarken möchte ich benchmark empfehlen, damit kannst du sehr einfach verschiedene Tests bauen, ohne groß mit Stopwatch und Co zu messen.

Erst einmal vielen Dank für die Tipps bzgl. des Profilings.
Den Programmen werde ich mich morgen bzw. das Wochenende an meinem privaten Rechner zuhause widmen.
Hat denn AQtime auch in der Standard-Version aus dem GetIt-Manager einfache Profiling-Strukturen wie
z.B. das Aufzeigen von Speicherressourcen, oder muss ich dafür die PRO-Version erwerben?
Oder ist gar der SamplingProfiler kostenlos? Sieht mir etwas altbacken aus, funktioniert der gar mit
Delphi 10.4?

[Gausi]

Ich würde hier nicht mit Profiling ansetzen, um irgendwo ein paar Takte zu sparen, sondern an dem Algorithmus an sich ...

Wenn ich nicht komplett danebenliege, würde ich an der (ziemlich teuren) RotateList-Funktion ansetzen - die kann doch so ziemlich ersatzlos weg!

Diese Rotation um den StartIndex wird doch nur benutzt, damit du in der Schleife ListA[i] mit ListB[i] vergleichen kannst. Warum lässt du das nicht weg, und vergleichst ListA[i] mit ListB[(StartIdx + i) mod ListB.Count]? Dann ersparst du dir sämtliches Umkopieren der Listen (nach dem "Aufräumen"), und dein Algorithmus dürfte um ein Vielfaches schneller werden, da du damit einen Faktor von O(n^2) aus der Laufzeit rausnimmst (solange dauert das Rotate nämlich im Mittel!)

Dazu musst du ggf. die beiden Polygondarstellungen auf "offen" normieren (dazu hats du ja die passenden Funktionen), damit Start/Endpunkt auf keinen Fall doppelt vorkommen.

Interessant wird da höchstens noch der Fall, wenn du Kantenzüge zulässt, die sich selbst kreuzen, und somit ggf. eine Koordinate mehr als einmal auftauchen darf. Aber dann wird das Problem ohnehin schwieriger, weil du an diesen Kreuzungen ggf. anders "abbiegen" kannst, was letztlich auf Graphisomorphie rausläuft. Und das ist dann so schwierig, dass man nichteinmal weiß, ob es NP-vollständig ist oder nicht. (Wobei es für den Spezialfall "Graphen mit Eulerweg" auch eventuell effiziente Tests geben könnte, da bin ich jetzt aber überfragt).

[Stevie]

Zitat von Gyrospeter:

Oder ist gar der SamplingProfiler kostenlos?

Ja

Zitat von Gyrospeter:

funktioniert der gar mit Delphi 10.4?

Ja, das habe ich mit

Zitat:

Obwohl der Profiler in der Oberfläche die neusten Delphi Versionen nicht auflistet funktioniert er tadellos.

aussagen wollen.

Zitat von Gausi:

Wenn ich nicht komplett danebenliege, würde ich an der (ziemlich teuren) RotateList-Funktion ansetzen - die kann doch so ziemlich ersatzlos weg!

Zu diesem Schluss war ich in den ersten beiden Sätzen meiner Anmerkungen auch gekommen.

Die Anmerkung zum Profiling war zur Unterstützung und Bestätigung, denn bei entsprechenden Testdaten (die ebend nicht die sind, die weiter oben im Thread gezeigt wurden) dürfte man ziemlich schnell und einfach sehen, dass das befüllen der temp Liste und das rotieren nen dicken Anteil der Laufzeit beansprucht. Nicht jeder sieht seinem Code gleich sein asymptotisches Verhalten an

[Gausi]

Zitat von Stevie:

Zu diesem Schluss war ich in den ersten beiden Sätzen meiner Anmerkungen auch gekommen.

Ups, sorry, das habe ich anscheinend überlesen.

Aber vielleicht als Ergänzung: Das haut natürlich besonders stark in dieser Zeile des Originalcodes rein, wenn AStartIdx = 0 ist.
RotateList(LTmpList, (LTmpList.Count - 1) - AStartIdx); Dann wird die Liste mit 1000 Einträgen 1000 mal im Speicher hin und her kopiert, bevor mit der Überprüfung auf Gleichheit der beiden Listen begonnen wird.

Das mit der Index-Rechnerei mag zwar aufwändiger erscheinen, ist es aber nicht. Schon alleine deswegen, weil bei ungleichen Polygonen es sehr schnell zu einem Abbruch kommen wird, während sich die Rotation grade erst warmgelaufen hat.

[Blup]

Bitte für das Formular eine eigene Unit.
Damit kannst du dir eine Bibliothek schreiben, die wenger Abhängigkeiten hat.
Das erleichtert auch die Implementation von Testfällen.

Mal ein erster Ansatz:

Delphi-Quellcode:

unit CadVec3;

interface

uses
  Generics.Collections;

type
  TCadVec3 = record
    x: Integer;
    y: Integer;
    z: Integer;
  end;

  TCadVec3List = TList<TCadVec3>;

// Globale Methoden.
  procedure RemoveIdenticalFromList(AList: TCadVec3List; AOpen: Boolean);

  function IsListItemEqual(AItem1, AItem2: TCadVec3): Boolean;
  function IsListEqual(AList1, AList2: TCadVec3List; AOffset: Integer): Boolean;

  function CompareOpenPolygons(AFirstList, ASecondList: TCadVec3List): Boolean; overload;
  function CompareOpenPolygons(AFirstList, ASecondList: TCadVec3List; ADirectional: Boolean): Boolean; overload;
  function CompareClosedPolygon(AFirstList, ASecondList: TCadVec3List): Boolean; overload;
  function CompareClosedPolygon(AFirstList, ASecondList: TCadVec3List; ADirectional: Boolean): Boolean; overload;

  function CompareBothLists(AFirstList, ASecondList: TCadVec3List; ADirectional, AFirstListOpen, ASecondListOpen: Boolean): Boolean;

implementation


function CompareBothLists(AFirstList, ASecondList: TCadVec3List; ADirectional, AFirstListOpen, ASecondListOpen: Boolean): Boolean;
var
  LFirstTmpList, LSecondTmpList: TCadVec3List;
begin
// Vergleich der Listen bzw. der Polygone und ob diese geometrisch gleich, oder ungleich sind.
// Hierbei werden verschiedene Rahmenbedingungen und Szenarien aufgeführt -> geschlossene Polygone, offene Polygone, geschlossenes/offenes Polygon.
  if (AFirstList = nil) or (ASecondList = nil) then
    Exit(False);

  LFirstTmpList := TCadVec3List.Create;
  LSecondTmpList := TCadVec3List.Create;
  try
    LFirstTmpList.AddRange(AFirstList);
    LSecondTmpList.AddRange(ASecondList);
    RemoveIdenticalFromList(LFirstTmpList, AFirstListOpen);
    RemoveIdenticalFromList(LSecondTmpList, ASecondListOpen);

    if AFirstListOpen and ASecondListOpen then
    begin
      if LFirstTmpList.Count <> LSecondTmpList.Count then
        Exit(False);

      Result := CompareOpenPolygons(LFirstTmpList, LSecondTmpList, ADirectional)
    end
    else
    begin
      if AFirstListOpen then
      begin
        if not IsListItemEqual(LFirstTmpList.First, LFirstTmpList.Last) then
          Exit(False);

        LFirstTmpList.Delete(LFirstTmpList.Count - 1);
      end
      else if ASecondListOpen then
      begin
        if not IsListItemEqual(LSecondTmpList.First, LSecondTmpList.Last) then
          Exit(False);

        LSecondTmpList.Delete(LSecondTmpList.Count - 1);
      end
      else // if not AFirstListOpen and not ASecondListOpen then
      begin
        if LFirstTmpList.Count <> LSecondTmpList.Count then
          Exit(False);
      end;

      Result := CompareClosedPolygon(LFirstTmpList, LSecondTmpList, ADirectional);
    end;
  finally
    LSecondTmpList.Free;
    LFirstTmpList.Free;
  end;
end;

function CompareClosedPolygon(AFirstList, ASecondList: TCadVec3List): Boolean;
var
  i: Integer;
begin
  // Vergleich von geschlossenen Polygonen bzw. einem offenen und einem geschlossenen Polygon.
  for i := 0 to ASecondList.Count - 1 do
  begin
    if IsListItemEqual(AFirstList[0], ASecondList[i]) then
    begin
      if IsListEqual(AFirstList, ASecondList, i) then
        Exit(True);
    end;
  end;
  Result := False;
end;

function CompareClosedPolygon(AFirstList, ASecondList: TCadVec3List; ADirectional: Boolean): Boolean;
begin
  Result := CompareClosedPolygon(AFirstList, ASecondList);
  if (not Result) and ADirectional then
  begin
    ASecondList.Reverse;
    Result := CompareClosedPolygon(AFirstList, ASecondList);
    ASecondList.Reverse;
  end;
end;

function CompareOpenPolygons(AFirstList, ASecondList: TCadVec3List): Boolean;
begin
// Vegleich von zwei offenen Polygonen.
  Result := IsListEqual(AFirstList, ASecondList, 0);
end;

function CompareOpenPolygons(AFirstList, ASecondList: TCadVec3List;
  ADirectional: Boolean): Boolean;
begin
  Result := CompareOpenPolygons(AFirstList, ASecondList);
  if (not Result) and ADirectional then
  begin
    ASecondList.Reverse;
    Result := CompareOpenPolygons(AFirstList, ASecondList);
    ASecondList.Reverse;
  end;
end;

function IsListEqual(AList1, AList2: TCadVec3List; AOffset: Integer): Boolean;
var
  i1, i2, iCount: Integer;
begin
// AOffset .. StartIndex in List2,
  iCount := AList2.Count;
  i2     := AOffset;
  for i1 := 0 to AList1.Count - 1 do
  begin
    if not IsListItemEqual(AList1[i1], AList2[i2]) then
      Exit(False);

    i2 := (i2 + 1) mod iCount;
  end;
  Result := True;
end;

function IsListItemEqual(AItem1, AItem2: TCadVec3): Boolean;
begin
  Result := (AItem1.x = AItem2.x) and (AItem1.y = AItem2.y) and (AItem1.z = AItem2.z);
end;

procedure RemoveIdenticalFromList(AList: TCadVec3List; AOpen: Boolean);
var
  i: Integer;
begin
// Entferne doppelte, aufeinander Folgende Eintr�ge bzw. Elemente.
  for i := AList.Count - 1 downto 1 do
  begin
    if IsListItemEqual(AList[i], AList[i - 1]) then
      AList.Delete(i);
  end;

  if not AOpen then
  begin
    if IsListItemEqual(AList.First, AList.Last) then
      AList.Delete(AList.Count - 1);
  end;
  AList.TrimExcess;
end;

end.