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

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

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

[freimatz]

Hoi,
gemeint ist das.
Gemeint ist also das Messen der Zeiten in Deinen alten Code um herauszufinden wo es klemmt.

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

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