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

[Gyrospeter]

Guten Abend werte Delphi-Gemeinde,

nun ist es für mich auch soweit, ich befinde mich gerade in den Vorbereitungen meines Abschlussprojektes und dabei geht es um Umgestaltung bzw. das effizienter Gestalten eines schon vorhandenen bzw. schon vorhandener Algorithmen.
Hierbei wird Wert auf die Laufzeit-, Speichereffizienz und kognitive Effizienz als drei Hauptkriterien gelegt.
Vorab, die Algorithmen die verbessert werden sollen hinlänglich der Effizienz, habe ich vor längerer Zeit selbst geschrieben.
In der Praxis hat sich herausgestellt, dass diese Algorithmen leider sehr langsam arbeiten und bei großen Listen auch ziemlich viel Speicher fressen.
Problem dabei ist, dass ich auf den ersten Blick nicht wirklich erkennen kann, wo Verbesserungspotential ist (außer z.B. auf die Listen als Feldvariablen zu verzichten und diese eben lokal zu erstellen und wieder wegzuräumen).
Ich möchte hier keine 1:1 Lösung angeboten bekommen, aber einige Tipps wo ich was verbessern könnte bzw. wo welche Stellen ich mir noch anschauen sollte, bei denen Verbesserungspotential herrscht

Kurzum was mein Code macht:
Es gibt 2 generische Listen die aus Records bestehen, vielleicht wären hier sogar generische Listen aus Vektoren besser diese Listen beinhalten Vektoren (Koordinaten) aus denen sich dann ein Polygon zeichnen lässt. Diese Polygone sollen nun verglichen werden. Es gibt Fälle in denen der Startpunkt bei Polygon 1 der Endpunkt bei Polygon 2 und umgekehrt ist, dann sind die Polygone dennoch gleich. Nur eben in der Liste von den umgedreht, diese wird dann durch eine Funktion rotiert. Weiterhin gibt es die Möglichkeit geschlossene oder offene Polygone als Parameter in die Listen zu übergeben. Auch auf doppelte Einträge wird geachtet und diese aus der Liste entfernt.

Als einen guten Lösungsansatz zur Vorbereitung fand ich:
https://stackoverflow.com/questions/...lygons-is-same

Und hier der Code:

Delphi-Quellcode:

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

  TCadVec3List = TList<TCadVec3>;

  TCADVecListHelperMainFrm = class(TForm)
    procedure FormCreate(Sender: TObject);
    procedure FormDestroy(Sender: TObject);
  private
    { Private-Deklarationen }
    FFirstCADList: TCadVec3List;
    FSecondCADList: TCadVec3List;
  public
    { Public-Deklarationen }
  end;

var
  CADVecListHelperMainFrm: TCADVecListHelperMainFrm;

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

  function IsListItemEqual(AFirstRecord, ASecondRecord: TCadVec3): Boolean;
  function CompareOpenPolygons(AFirstList, ASecondList: TCadVec3List; ADirectional: Boolean): Boolean;
  function CompareClosedPolygon(AFirstList, ASecondList: TCadVec3List; AStartIdx: Integer; ADirectional: Boolean): Boolean;
  function CompareBothLists(AFirstList, ASecondList: TCadVec3List; ADirectional, AFirstListOpen, ASecondListOpen: Boolean): Boolean;

implementation


{$R *.dfm}

function CompareBothLists(AFirstList,
  ASecondList: TCadVec3List; ADirectional, AFirstListOpen, ASecondListOpen: Boolean): Boolean;
var
  i: Integer;
  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.
  LFirstTmpList := TCadVec3List.Create;
  LSecondTmpList := TCadVec3List.Create;

  try
    Result := False;

    if (AFirstList = nil) or (ASecondList = nil) then
      Exit;

    LFirstTmpList.AddRange(AFirstList);
    LSecondTmpList.AddRange(ASecondList);
    RemoveIdenticalFromList(LFirstTmpList, AFirstListOpen);
    RemoveIdenticalFromList(LSecondTmpList, ASecondListOpen);

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

    if not AFirstListOpen and not ASecondListOpen then
    begin
      for i := 0 to LSecondTmpList.Count - 1 do
      begin
        if IsListItemEqual(LFirstTmpList[0], LSecondTmpList[i]) then
        begin
          Result := CompareClosedPolygon(LFirstTmpList, LSecondTmpList, i, ADirectional);

          if Result then
            Break;
        end;
      end;
      Exit;
    end
    else if AFirstListOpen and ASecondListOpen then
      Result := CompareOpenPolygons(LFirstTmpList, LSecondTmpList, ADirectional)
    else if AFirstListOpen and not ASecondListOpen then
    begin
      if IsListItemEqual(LFirstTmpList.First, LFirstTmpList.Last) then
      begin
        LFirstTmpList.Delete(LFirstTmpList.Count - 1);

        for i := 0 to LSecondTmpList.Count - 1 do
        begin
          if IsListItemEqual(LFirstTmpList[0], LSecondTmpList[i]) then
          begin
            Result := CompareClosedPolygon(LFirstTmpList, LSecondTmpList, i, ADirectional);

            if Result then
              Break;
          end;
        end;
        Exit;
      end
      else
        Exit;
    end
    else
    begin
      if IsListItemEqual(LSecondTmpList.First, LSecondTmpList.Last) then
      begin
        LSecondTmpList.Delete(LSecondTmpList.Count - 1);

        for i := 0 to LFirstTmpList.Count - 1 do
        begin
          if IsListItemEqual(LSecondTmpList[0], LFirstTmpList[i]) then
          begin
            Result := CompareClosedPolygon(LSecondTmpList, LFirstTmpList, i, ADirectional);

            if Result then
              Break;
          end;
        end;
        Exit;
      end
      else
        Exit;
    end;
  finally
    LSecondTmpList.Free;
    LFirstTmpList.Free;
  end;
end;

function CompareClosedPolygon(AFirstList, ASecondList: TCadVec3List; AStartIdx: Integer; ADirectional: Boolean): Boolean;
var
  i: Integer;
  LEqual: Boolean;
  LTmpList: TCadVec3List;
begin
//  Vergleich von geschlossenen Polygonen bzw. einem offenen und einem geschlossenen Polygon.
  LTmpList := TCadVec3List.Create;

  try
    LEqual := True;
    LTmpList.AddRange(ASecondList);
    RotateList(LTmpList, AStartIdx);

    for i := 0 to AFirstList.Count - 1 do
    begin
      if not IsListItemEqual(AFirstList[i], LTmpList[i]) then
      begin
        LEqual := False;
        Break;
      end;
    end;

    if not LEqual and not ADirectional then
    begin
      LEqual := True;
      LTmpList.Clear;
      LTmpList.AddRange(ASecondList);
      LTmpList.Reverse;
      RotateList(LTmpList, (LTmpList.Count - 1) - AStartIdx);

      for i := 0  to AFirstList.Count - 1 do
      begin
        if not IsListItemEqual(AFirstList[i], LTmpList[i]) then
        begin
          LEqual := False;
          Break;
        end;
      end;
    end;
    Result := LEqual;
  finally
    LTmpList.Free;
  end;
end;

function CompareOpenPolygons(AFirstList, ASecondList: TCadVec3List;
  ADirectional: Boolean): Boolean;
var
  i: Integer;
  LEqual: Boolean;
  LTmpList: TCadVec3List;
begin
//  Vegleich von zwei offenen Polygonen.
  LTmpList := TCadVec3List.Create;

  try
    LEqual := True;
    LTmpList.AddRange(ASecondList);

    for i := 0 to AFirstList.Count - 1 do
    begin
      if not IsListItemEqual(AFirstList.Items[i], LTmpList.Items[i]) then
      begin
        LEqual := False;
        Break;
      end;
    end;

    if not LEqual and not ADirectional then
    begin
      LEqual := True;
      LTmpList.Clear;
      LTmpList.AddRange(ASecondList);
      LTmpList.Reverse;

      for i := 0 to AFirstList.Count - 1 do
      begin
        if not IsListItemEqual(AFirstList.Items[i], LTmpList.Items[i]) then
        begin
          LEqual := False;
          Break;
        end;
      end;
    end;
    Result := LEqual;
  finally
    LTmpList.Free;
  end;
end;

procedure TCADVecListHelperMainFrm.FormCreate(Sender: TObject);
begin
//  Instanzen erzeugen.
  FFirstCADList := TList<TCadVec3>.Create;
  FSecondCADList := TList<TCadVec3>.Create;
end;

procedure TCADVecListHelperMainFrm.FormDestroy(Sender: TObject);
begin
//  Instanzen freigeben.
  FSecondCADList.Free;
  FFirstCADList.Free;
end;

procedure RotateList(AList: TCadVec3List; AIndex: Integer);
var
  i: Integer;
begin
//  Rotation der Liste zum vorgegebenen Startindex bzw. Startpunkt.
  if (AList = nil) or (AIndex < 0) or (AIndex > AList.Count - 1) then
    Exit;

  for i := 0 to AIndex  - 1 do
  begin
    AList.Move(0, AList.Count - 1);
  end;
end;

function IsListItemEqual(AFirstRecord, ASecondRecord: TCadVec3): Boolean;
begin
//  Vergleich der Elemente in der Liste.
  if (AFirstRecord.x = ASecondRecord.x) and (AFirstRecord.y = ASecondRecord.y) and (AFirstRecord.z = ASecondRecord.z) then
    Result := True
  else
    Result := False;
end;

procedure RemoveIdenticalFromList(AList: TCadVec3List; AOpen: Boolean);
var
  i: Integer;
  LCadActualItem,LCadNextItem: TCadVec3;
begin
//  Entferne doppelte, aufeinander Folgende Einträge bzw. Elemente.
  for i := AList.Count - 1 downto 1 do
  begin
    LCadActualItem := AList.Items[i];
    LCadNextItem := AList.Items[i - 1];

    if IsListItemEqual(LCadActualItem, LCadNextItem) then
      AList.Delete(i - 1);
  end;

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

[TiGü]

Ein paar Testdaten zum schnellen Ausprobieren wäre eine gute Idee, damit wir leicht die Fälle erkennen können, woran es genau scheitert.

Beim ersten drüber schauen lässt sich relativ leicht zum Beispiel das hier optimieren:

Delphi-Quellcode:

function IsListItemEqual(AFirstRecord, ASecondRecord: TCadVec3): Boolean;
begin
// Vergleich der Elemente in der Liste.
  if (AFirstRecord.x = ASecondRecord.x) and (AFirstRecord.y = ASecondRecord.y) and (AFirstRecord.z = ASecondRecord.z) then
    Result := True
  else
    Result := False;
end;

Nach:

Delphi-Quellcode:

function IsListItemEqual(const AFirstRecord, ASecondRecord: TCadVec3): Boolean;
begin
  // Vergleich der Elemente in der Liste.
  Result := (AFirstRecord.x = ASecondRecord.x) and (AFirstRecord.y = ASecondRecord.y) and (AFirstRecord.z = ASecondRecord.z);
end;

Durch die Verwendung von const in den Parametern werden beide Records nicht mehr kopiert (je nach verwendeten Compiler) und die Zuweisung vom Result lässt sich auch kürzen.
Ergibt in Debug Win32 auch sieben Zeilen weniger generierten Assembler (38 zu 31 Zeilen).

[freimatz]

Wie gross sind die Listen? Wie oft kommen die Equal vor?

[TiGü]

Wenn ich mich jetzt nicht verguckt habe, kann man die Hauptfunktion auch etwas verkürzen zu:

Delphi-Quellcode:

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

  function PleaseChangeToAMeaningfulName(const AList1, AList2: TCadVec3List; const ADirectional: Boolean): Boolean;
  var
      i: Integer;
  begin
    Result := False;
    for i := 0 to AList2.Count - 1 do
    begin
      if IsListItemEqual(AList1[0], AList2[i]) then
      begin
        Result := CompareClosedPolygon(AList1, AList2, i, ADirectional);

        if Result then
          Break;
      end;
    end;
  end;

  function PleaseChangeToAMeaningfulName2(const AList: TCadVec3List): Boolean;
  begin
    Result := IsListItemEqual(AList.First, AList.Last);

    if Result then
    begin
      AList.Delete(AList.Count - 1);
    end;
  end;

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.
  LFirstTmpList := TCadVec3List.Create;
  LSecondTmpList := TCadVec3List.Create;

  try
    Result := False;

    if (AFirstList = nil) or (ASecondList = nil) then
      Exit;

    LFirstTmpList.AddRange(AFirstList);
    LSecondTmpList.AddRange(ASecondList);
    RemoveIdenticalFromList(LFirstTmpList, AFirstListOpen);
    RemoveIdenticalFromList(LSecondTmpList, ASecondListOpen);

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

    if not AFirstListOpen and not ASecondListOpen then
    begin
      Result := PleaseChangeToAMeaningfulName(LFirstTmpList, LSecondTmpList, ADirectional);
    end
    else if AFirstListOpen and ASecondListOpen then
    begin
      Result := CompareOpenPolygons(LFirstTmpList, LSecondTmpList, ADirectional)
    end
    else if AFirstListOpen and not ASecondListOpen then
    begin
      if PleaseChangeToAMeaningfulName2(LFirstTmpList) then
      begin
        Result := PleaseChangeToAMeaningfulName(LFirstTmpList, LSecondTmpList, ADirectional);
      end;
    end
    else
    begin
      if PleaseChangeToAMeaningfulName2(LSecondTmpList)  then
      begin
        Result := PleaseChangeToAMeaningfulName(LSecondTmpList, LFirstTmpList, ADirectional);
      end;
    end;
  finally
    LSecondTmpList.Free;
    LFirstTmpList.Free;
  end;
end;

Ob jetzt Subroutinen oder eigene freistehende Funktionen ist Geschmackssache.

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

[Gyrospeter]

Zitat von TiGü:

Ein paar Testdaten zum schnellen Ausprobieren wäre eine gute Idee, damit wir leicht die Fälle erkennen können, woran es genau scheitert.

Da habe ich ganz stumpf Integer als kleine Testung hart in die Listen eingetragen und je nachdem einen bis mehrere Werte geändert damit sich die Polygone unterscheiden:

Delphi-Quellcode:

procedure TCADVecListHelperMainFrm.FillBothLists;
var
  LRecord,ChangedRec: TCadVec3;
  i: Integer;
begin
//  Fülle beide Listen mit random default Werten.

  if (FFirstCADList <> nil) and (FSecondCADList <> nil) and (FFirstCADList.Count = 0) and (FSecondCADList.Count = 0) then
  begin
    for i := 0 to 1000 - 1 do
    begin
      LRecord.x := RandomRange(0, 1000);
      LRecord.y := RandomRange(0, 1000);
      LRecord.z := RandomRange(0, 1000);
      FFirstCADList.Add(LRecord);
    end;

    ChangedRec.x := 100;
    ChangedRec.y := 100;
    ChangedRec.z := 100;
    FSecondCADList.AddRange(FFirstCADList);
//    FSecondCADList.Items[12] := ChangedRec;
  end;
end;

[Gyrospeter]

Zitat von freimatz:

Wie gross sind die Listen? Wie oft kommen die Equal vor?

Listen sind unterschiedlich groß, je nach Komplexität des Polygons. Kann aus 5 Einträgen bestehen, kann aber auch aus 5000 Einträgen bestehen. Siehe mein Code-Beispiel darüber, bei denen ich einfach testweise die Listen befüllt habe.

[freimatz]

Danke für Deine Ausführungen Gyrospeter. Genau deshalb fragte ich nach. Kommt das nur selten vor ist ein Delete direkt besser, wenn es mehr als nur selten vorkommt dann ist etwas anders besser. Man kann einen temporären Container nehmen oder zuerst nur mal die Einträge als zu löschen markieren und danach in einem Rutsch zu löschen.
Statt einer Liste wäre vermutlich auch Arrays performater.
Aber! Das ist alles Stochern im Nebel. Ein Profiling wäre richtig und wichtig.

[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?

[Gyrospeter]

Zitat von freimatz:

Ein Profiling wäre richtig und wichtig.

Ist mit dem Profiling das Testen im Bezug auf die Effizienz gemeint?
Leider habe ich ja z.B. bei der Laufzeiteffizienz noch keine richtige Referenz, da ich ja noch keinen Vergleich zwischen altem Code und den neuen, optimierteren Code habe