Video 5-5: Kostenmodelle

0:03 Dann noch ein kleiner letzter Abschnitt zu dem, was eigentlich die ganze Zeit nur indirekt als Kosten beschrieben wurde. Was was ist denn jetzt die eigentlichen Kosten von dem Algorithmus?

0:14 Das hängt so ein bisschen davon ab, was wir uns anschauen. Allermeistens in allermeisten Zeit interessiert uns die Laufzeit. Das heißt, wir gucken uns die Worst Case Laufzeit auf einem bestimmten Computer mit einer bestimmten Eingabe an. Das ist das, was uns pragmatisch interessiert. In unserer asymptotischen Vergleichswelt vergleichen wir dann eben das asymptotische Wachstum von dieser Laufzeit. Äh und auch der Speicherbedarf kann relevant sein, insbesondere dann, wenn wir an die Grenzen vom Hauptspeicher stoßen. Wird aber in Algorithmen und Datenstrukturen nur so eine Nebenrolle spielen.

0:52 Jetzt woll ich noch ein bisschen reinzoomen in was Laufzeit denn heißen soll. Also eine Option, wir werden da am Mittwoch noch ein bisschen genauer reingucken in die Option, die man da hat. Eine Möglichkeit wäre, ich ich setze mich mit der Stoppuhr hin und äh zähle eben die Zeit, die Sekunden, bis mein Algorithmus fertig ist. Und das ist auch äh was, wozu sie ermutigt werden. Gleichweil gleich wohl ist es aber nicht immer das geeignete Mittel der Wahl, weil es eben von ganz vielen Dingen abhängt, die sehr spezifisch für ihre konkrete Ausführung sind und es sehr schwer machen zu prognostizieren auf einer anderen Eingabe oder nächstes Jahr auf den nächsten Architekturen. Wie lange da würde es dann dauern? Also präzise Laufzeit, was das heißt, ist einfach wir stoppen. Werden wir werden wir sehen. Ähm ist ein wichtiges Puzzlteil, aber kann nicht alles bleiben. Wenn wir verstehen wollen, was ein Algorithmus schnell oder langsam macht, auch um ihn zu verbessern, dann werden wir uns ein abstrakteres Kostenmaß vornehmen.

2:00 Das also äh vielleicht erstes Beispiel bei Union Fight hatten wir das schon gemacht. Ich hatte das nur nicht so sehr betont. Da hatten wir die Anzahl Array Zugriffe zum Kostenmaß erklärt. Wir haben uns nicht wirklich Gedanken macht gemacht, wie lange die Addition von irgendwelchen Indizes in dem Code dort dauern. Mussten wir auch nicht, denn die Anzahl Array Zugriffe ist im Wesentlichen proportional zur tatsächlichen Laufzeit in diesem in diesen Beispielen das Union Find Kapitel. ähm insbesondere ähm die Zugriffe auf dieses ID Array.

2:45 Warum machen wir das? Na ja, wenn man Array Zugriffe zählt, dann hängt das plötzlich nicht mehr von der ganzen Hardware und allen Details ab, sondern ähm wir wir haben jetzt etwas, das im Wesentlichen Hardware unabhängig ist und perfekt reproduzierbar ist. Das heißt, äh wir können ein abstraktes Maß zählen, wie hier diese Array Zugriffe und wir haben die Garantie, dass die um und bei die Laufzeit angeben, auch wenn das in den Nachkommastellen nicht immer stimmt, aber es ist exakt reproduzierbar auf jeder Hardware gleich und ich kann es leichter analysieren, zumindest ist die Hoffnung und werden es in vielen Beispielen tun, dass ich dann prognostizieren kann, wie lange dauert was auf einer größeren Eingabe, die ich nicht ausführen will oder welche hypothetischen Änderungen in meinem Algorithmus haben einen Einfluss auf die Laufzeit.

3:43 Damit wollen wir es belassen mit der mit der ganzen Modellierung. Also was wir heute besprochen haben, ist für alle Teile, die in so einem Algorithmus, in so einer Laufzeit Messung von dem Algorithmus eine Rolle spielen, ein mathematisches Modell zu finden, das ein bisschen aus der konkreten technologischen Instanzierung, die wir aktuell haben, abstrahiert, insbesondere für die Daten, Worst case und Eingabegröße für die Maschinen, WordRAM und die lange Diskussion, was wie lange dauert eine Addition und auch die Kosten selber.

4:15 haben wir abstrahiert zu einem abstrakten Kostenmaß und all das diese Modellierung ist eben die Voraussetzung dafür, dass wir wissenschaftlich fundiert Algorithmen vergleichen können. Und wie das dann im Detail aussieht, werden wir uns am Mittwoch anschauen. Da werden wir das dann auch noch mal ein bisschen konkreter machen.