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

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

[TurboMagic]

In manchen Delphi Versionen war eine Lite Version von AQTime dabei, es gibt aber auch andere Profiler.
Hat man ein neu genuges Delphi findet man glaube ich auch einen in GetIt, was ja aber in XE2 noch nicht
vorhanden ist, falls das wirklich die von dir genutzte Version ist.

Natürlich haben neuere Delphi versionen auch die eine oder andere Performance Verbesserung mit drin...

[Gyrospeter]

Zitat von freimatz:

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

Vielen Dank. Jetzt bin ich wieder etwas schlauer geworden =)

Zitat von TurboMagic:

In manchen Delphi Versionen war eine Lite Version von AQTime dabei, es gibt aber auch andere Profiler.
Hat man ein neu genuges Delphi findet man glaube ich auch einen in GetIt, was ja aber in XE2 noch nicht
vorhanden ist, falls das wirklich die von dir genutzte Version ist.

Natürlich haben neuere Delphi versionen auch die eine oder andere Performance Verbesserung mit drin...

Hab meine Delphi-Version korrigiert. Bei GetIt gibt es tatsächlich einen Profiler (AQTime). Muss ich beim hinzufügen etwas beachten oder gibt es ein gutes Manual über die Nutzung darüber?

Wäre den Threading einen Blick wert, z.B. beim Hinzufügen nicht doppelter Elemente zu den temporären Listen, also um das befüllen beider temporärer Listen zu parallelisieren oder macht es bei nur zwei Listen keinen Sinn?

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

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