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;