Video 8-8: Dynamische Arrays

0:02 Jetzt hatten wir eine verkettete Darstellung gesehen, die für einige Bereiche gut funktioniert hat. Insbesondere dieses Blibig Einfügen. Irgendwo in der Mitte der Liste war ein großer Vorteil von der verketteten Darstellung. Äh im nächsten Abschnitt möchte ich Ihnen noch eine eine klassische Datenstruktur vorstellen, die ein bisschen ungeschickte Namen hat. Ähm, ich habe sie mal hier jetzt dynamische Arrays genannt. Äh, manchmal heißt sie auch resizable Arrays oder Doubling Arrays oder ähm diverse andere Namen, die so ein bisschen grenzwertig irreführend sind. Die Motivation ist das Szenario, dass man tatsächlich häufig hat, dass dieser tolle Vorteil von verketteten Listen gar nicht gebraucht wird. Also ähm wir müssen nicht unbedingt in der Liste irgendwo einfügen. Es reicht uns, dass wir hinten anhängen können. Wir können uns aber auch nicht irgendwie mit einer festen Gesamtlänge vorab anfreunden und äh möchten also all diese Dinge zusammen haben. Dynamische Größe, ich kann also wachsen lassen oder vielleicht auch wieder schrumpfen. Äh, ich würde gerne den Overhead von Verkett und Listen vermeiden oder ich brauche eben diesen Zugriff per Index.

1:18 All in all diesen Fällen kann ich ähm verkettete Listen eigentlich nicht gut verwenden. Stattdessen hätten wir eigentlich wirklich gern ein Array. Das ist das einzige, was wirklich diesen Random Access direkt unterstützt und am schnellsten unterstützt, aber das kann halt nicht mitwachsen. Also sind wir irgendwie in dem Dilemma gefangen. Aber das Dilemma ist ja nur ein scheinbares, denn ich kann ja immer, wenn ich mehr Platz brauche, einfach ein neues Array anlegen, dann habe ich meinen wahlfreien Zugriff. Das kommt natürlich äh mit gewissen Zusatzkosten. Ich muss dann schon, wenn ich das aufrechterhalten will, alle Daten in dieses neue Array umkopieren, damit ich das alte freigeben kann. Äh, das heißt, das ist eventuell teuer, je nachdem, wie viele Elemente ich in diesem Array habe. Wir sollten also, wenn wir das machen, wenigstens dafür sorgen, dass das nur selten passiert. Dieser Anwendungsfall ist so häufig, dass quasi alle Programmiersprachen fast für den optimiert sind, möchte ich sagen. Das vielleicht ein bisschen übertrieben, aber sie haben zumindest eine Datenstruktur, die dafür optimiert ist. Über die Java Implementierung werden wir im Anhang gleich noch mal sprechen. Ähm werden Sie dann sehen, dass es da auch zur Verwendung kommt. Spoiler ich mal jetzt noch nicht.

2:37 Äh, erstmal für Sie als vorabden Denkfrage. Angenommen, ich möchte das machen. Ich möchte ähm meine Array vergrößern, sobald ich keinen Platz mehr habe. Was heißt denn vergrößern?

2:53 Also, wenn ich aktuell Größe N habe, wie groß sollte die neue Größe werden? Da hat man ja erstmal Freiheit. Äh, wir wollen ein bisschen Platz lassen, damit wir vielleicht nicht jedes Mal direkt kopieren müssen, aber welche Größe würden Sie wählen?

3:17 Ist Freitext, das heißt, sie können auch ähm sich länger austoben, wenn sie mögen, aber es ist also diese Wordcloud ist relativ beschränkt. Sie können ein paar Zeichen schicken, glaube ich. Vielleicht wissen sie ja, was Java macht. Ich werde sie nachher auch zeigen. M.

4:46 Also gebe mal noch ähm ein paar Sekunden unbeinflusst von Antworten anderer was zu schicken, dann zeige ich Ihnen mal, was wir so bekommen. mal Was man hier wieder nicht gut sehen kann, ist wie viele Leute welche Antwort geschickt haben. zweimal n haben neun Leute geschickt. Das ist äh also nicht ganz repräsentativ groß. Äh was haben wir noch so für Vorschläge? Okay, 2 hoch n ist krass. Ähm okay. Also, viele von ihnen kennen das schon. Ähm, weiß wie wie genau sie drüber nachgedacht haben, welche Größe warum vielleicht eine gute Idee ist. Ich hatte vorhin auch schon gesagt, die Dinger heißen Doubling Arrays. Das ist vielleicht auch ein Hinweis gewesen, nicht?

6:03 Also, ich verwende die verschiedenen Namen so ein bisschen austauschbar. Es gibt nichts Magisches an dieser Zahl 2. Äh, tatsächlich sehe ähm macht Java auch nicht das. Äh, kommen wir gleich noch mal zu. Also die Lösung ist, wir halten ein Array vor, das eine gewisse Kapazität C hat und die soll immer ein bisschen Platz lassen. Wenn wir aktuell N Elemente speichern, dann möchten wir, dass diese zwei Größen, die Anzahlelemente und diese Kapazität um und beiden konstanten Faktoren nur aufeinander abweichen. Die Anzahlelemente muss natürlich höchstens C sein, sonst würden sie nicht in den in das Array passen, aber es soll auch nicht zu weit weg sein. Äh, das ist aber erstmal eine Invariante ist ja immer ein Wunsch. Ich hätte das gerne, dass das immer der Fall ist. Da muss ich mich aber auch drum kümmern, dass dem so ist. Ähm, ich habe das hier formuliert so in der Notation von einem Stack, denn dafür passt das im Prinzip gut. Was wir hier bauen mit diesen Operationen oder in diesem Szenario ist im Wesentlichen ein Stack, auf den ich auch zugreifen kann per Index, um Elemente zu lesen oder zu schreiben. Aber einfügen darf ich eben nur ganz am Ende oder einfügen und löschen darf ich nur ganz am Ende.

7:17 Also, wenn wir diese Invariante irgendwie aufrechterhalten können, dann ist alles gut. Dann haben wir ja immer Platz, um Elemente einzufügen. Natürlich muss ich dafür irgendwann mal was tun. Und was wir dafür tun ist, wann immer wir eine Operation haben, die die Anzahl Elemente verändert, Push oder Pop, prüfen wir, ob wir an der Grenze sind. Wenn bei Push die Kapazität erreicht ist schon vor diesem neuen Element, dann muss ich Platz schaffen und ich lege eine Ray der Größe 2 x N an und kopiere meine Elemente. Äh, witzigerweise mache ich genau das gleiche, wenn meine Ray zu klein ist. Ich lege auch eine Ray der Größe 2 x n an, aber natürlich ist das n jeweils ähm relativ zur Akt zur alten Kapazität ein anderes. Hier ist sozusagen dieses 2n 2 x c, weil ich an der Grenze bin, während hier ist es ce.

8:21 Aber im Code sieht das dann so aus, als würde ich den gleichen Aufruf machen. Wie schon erwähnt, die Konstanten 2 an der Stelle ähm hat den schönen Effekt, dass wir hier die gleiche Konstante stehen haben, aber da gibt's keine magische äh Bedeutung von der zwei. Sie könnt es durch andere Zahlen ersetzen, solange die ein bisschen Abstand von voneinander haben.

8:50 äh sage ich gleich noch mal was dazu. Ähm erstmal hier kurz ähm in in kompaktem Code, wie man das bauen könnte. Also, ich habe meine meine Doubling Arraystruktur. Ich habe ein ein internes Array, das die Objekte speichert. Das hat irgendein initiale Länge, das ist wesentlichen beigestellt, wie Sie das wählen. Und es speichert sich, wie viele Elemente ich tatsächlich verwende. Und dann gibt's diese ähm diese private Methode, die dafür sorgt, dass die Invariante wieder erfüllt ist. Die rufe ich hier einfach vor Push und Pop auf und die kümmert sich dann sozusagen um den Rest, das rund umsorglospaket. Äh, die aktuelle Kapazität ist C, falls C nicht mehr in dem Bereich ist, den wir es hätten oder das N zu C nicht mehr in dem Verhältnis ist, wie wir es gerne hätten. Also C äh zu klein oder zu groß. Ähm, das hier ist der Fall, dass es noch gut ist. Ja, n erfüllt die Invariante, dann belassen wir alles wie es war. Ansonsten legen wir ein neues Array der Länge 2 x n an. Egal in welchem Fall wir sind. Das ist der der einzig magische Teil von der 2, dass hier in diesem Fall das gleiche passiert. Brauche ich keine Fallunterscheidung, aber ich muss dann natürlich alle Daten in das neue Array kopieren und das hat hier Kosten proportional zur Anzahlelemente.

10:10 Ansonsten ist der Code ähm relativ harmlos. Ähm, gibt's irgendwas noch sonst zu sagen? Das sieht sehr nah aus an dem Code, den wir für den Array basierten Stack haben. Das natürlich auch äh kein Zufall, denn wir das ist im wesentlichen ein Arraybasierter Stack, nur dass wir jetzt noch die Option haben, auf per Index adressierte Elemente zuzugreifen.

10:36 Also funktioniert problemlos. Ähm, auch mit der mit der Größe hier von zwei und so geht alles gut, aber dieses Kopieren ist natürlich teuer. Wenn wir also zu oft diesen Kopaufruf hätten, dann wäre diese Datenstruktur nicht wirklich verwendbar.

10:51 Äh, kleiner Vorg wesentlichen ist was Javas Array List tut, um und bei das hier. Ähm, mit einem kleinen Unterschied werde ich nach noch was zu sagen und sie verdoppeln nicht, sondern nehmen 50% extra, also mal 1,5 statt mal 2. Das macht aber keinen so großen Unterschied. Das einfach ein bisschen anderer Trader von verschwendetem Speicherplatz zu Anzahl kopieren. Aber ich muss irgendwie sicherstellen, dass ich nicht zu oft kopiere. Und wir haben hier das Problem, dass jeder einzelne Aufruf von Push und Pop dieses Kopieren auslösen könnte. Das heißt, im Worst Case kann ich das nicht irgendwie besser haben.

11:41 Im Worst Case gilt für sowohl Push und Pop, sowohl Push als auch Pop, eine Laufzeit von thata von N. linear in der Anzahl Elemente können wir jetzt genauer sagen, was wir zählen wollen. Wir könnten sagen Schreibzugriffe, dann wäre es im Wesentlichen N, weil ich hier für das Kopieren die Schreibzugriffe zähle. Das ist sehr teuer im Vergleich zu dem, was wir sonst mit den Listen erreicht hatten, aber da gibt's keinen Weg drum rum. Worst case bleibt genau das. Ähm, was wir brauchen ist eine andere Sichtweise auf die Analyse. Wenn wir diese pessimistische Worst case Brille aufziehen, dann kommen wir nicht weiter. Und die richtige Brille hier heißt amortisierte Analyse. Amortisieren letztlich ein Buchhaltungsbegriff sagt ähm ich habe Investitionskosten jetzt, aber ich profitiere von der Investition über die Zeit. Das heißt, diese Kosten, die ich jetzt habe und die jetzt erstmal direkt zu Buche schlagen, die amortisieren sich über die Zeit, weil ich dann keine Ausgaben habe in den nächsten 5 Jahren, wo ich nicht noch einen Transporter kaufen muss.

12:44 Ähm, amortisierte Analyse in der Buchhaltung ist also dann ein eine buchhalterische Maßnahme, wie man diese Kosten über die Zeit äh aufteilt, obwohl sie eigentlich jetzt anfallen. Und genau diese gleiche Idee können wir auf die Datenstrukturen übertragen.

13:00 Normal sieht das dann immer so aus, dass wir immer eine Folge von Operationen uns anschauen. Jede einzelne Operation kann ich keine Garantien geben. Wenn ich aber eine Folge von Operationen habe, die direkt nacheinander ausgeführt werden, dann kann ich was drüber sagen. In diesem Fall kann ich sagen, eine beliebige Folge von M Operation Pushpop gets set was immer das Dubling Array anbietet. Die Spannenden sind nur Push und Pop. Die anderen haben einen Zugriff, da passiert Lides Kopieren. Also eine beliebige Folge von solchen Operationen auf einem Doubling Array, der das Initialgröße N hat, hat Gesamtkosten von O von N + M. Wenn wir mal ein bisschen vereinfachen und sagen, wir fangen mit einem leeren Doubling Array an, dann ist n 0 oder 1. Das heißt, das können Sie hier ignorieren. Was heißt das dann? Das bedeutet, für die M Operation habe ich Kosten M, also gemittelt über die Operation konstante Kosten pro Operation. Aber dieses Mittel ist halt nur ein Mittel. Ich kann das nur über eine Folge von Operationen ansetzen. Jede einzelne Operation könnte viel viel teurer sein.

14:13 Das ist, was man dann ausdrückt als eine Operation hat amierte Kosten von Oven 1. Einzelner konkreter Aufruf könnte teurer sein, aber wenn ich eine Folge habe, dann im Mittel diese Kosten.

14:30 Also ich versuche das fünf mal zu unterstreichen, weil einfach ähm es vielleicht ein bisschen verwirrender Begriff ist als die Arten von Analysen, die wir bisher so gemacht haben. No ein schöner voller Beweis ähm zu diesem Theorem äh habe ich tatsälich auf meiner Website. Ähm mache ich aber in im Detail in effiziente Algorithmen mit der Potenzialmethode, wenn Sie das sehen wollen, müssen Sie da noch mal kommen oder sich die Videos anschauen oder den Blogpost lesen. Äh, was ich Ihnen hier zeigen möchte, ist eine intuitivere Variante, wo das Argument einfacher ist, wo wir die Pop Aufrufe streichen. Das heißt, unser Array kann immer nur wachsen. Ich erlaube nur Pushhaufrufe und die anderen Get und Set sind harmlos, aber kein Pop. Okay, das heißt, ähm verfeinertes Theorem hier eine beliebige Folge von Push aufrufen und noch mal vereinfacht, damit wir das das endlich auch noch als zweiten Parameter haben. Anfangsleeres Doubling array kostet O von M Array Zugriffe.

15:36 Wir können sogar die Konstante angeben. Wie analysiert man sowas? Oder wie beweist man so ein so eine Aussage? Äh die die Anschauung hier ist, dass wir ähm jedem Aufruf einen gewisses Budget geben und die ähm Datenstruktur muss mit diesem Budget haushalten. Also noch mal äh die Fakten etablieren. Wir haben diese Pushaufrufe in zwei Ausführungen. nämlich im Code kann ich entweder in Insure Capacity dieses Kopieren haben oder ich habe den frühen Absprung, ich habe noch die Inviariante erfüllt. Das heiß, es gibt eine günstige und eine teure Version von Push und ich weiß in im Allgemeinen noch äh vorher nicht, welcher der beiden eintreten wird.

16:29 Beim günstigen Fall habe ich keine Vergrößerung vom Array. Das heißt, meine Schreitzugriffe sind genau eins, um dieses neue Element in das Array einzutragen. In dem teuren Fall muss ich die Größe von A verdoppeln. Wenn ich im teuren Fall bin, dann ist A genau in der Kapazität. Das heißt, das 2 x N ist die Größe von 2 x C. Dann habe ich n Schreibzugriffe für das Kopieren der Elemente in das neue Array und einen zusätzlichen für das zusätzliche Element, dass ich natürlich dann auch noch irgendwo hinschreiben muss. Wenn ich mir jetzt vorstelle, ich gebe jedem Push Aufruf, egal ob er teuer oder billig ist, drei Münzen mit auf den Weg. Äh und sie können sich vorstellen, das ist so ein so ein Gleitzeit Arbeitskonto. Sie können mal ein paar Überstunden aufbauen und dann wieder abbauen. Das genau, was wir hier mit den Münzen abbilden. Ein günstiges Push hat zwei Münzen übrig. Eine muss es bezahlen, um den Schreibzugriff auf das Array zu bezahlen, den den es selbst auslöst. Dann hat das aber noch zwei Münzen übrig. Eine davon behält das aktuelle Element.

17:31 Ich versuch das mal bisschen zu skizzieren. Wir haben hier den Füllstand bisher. Jetzt fügen wir ein neues Element hier ein. Das bezahlt mit einer Münze dafür, dass es hier reingeschrieben wird. Und es behält aber auch eine Münze hier noch als Vorrat. Und jetzt hat's noch eine Münze, die es abgeben kann an ein Element weiter vorne im Array. Wer dann gleich sehen, warum wir das brauchen. Wenn ich einen teures Push habe, dann ist die Behauptung, ich gehe einfach alle Münzeln einsammeln. all diese grünen und die bezahlen genau die Schreibzugriffe, die ich fürs Kopieren brauche. Wenn diese Rechnung also aufgeht, dann habe ich amisiert drei Schreibzugriffe pro Operation, denn jede Operation zahlt drei Münzen und die Münzen werden umgesetzt in Schreibzugriffe. Reingenommen habe ich sogar nur höchstens, weil es könnte auch mal noch Münzen übrig bleiben am Ende, aber ich gebe nie mehr Schreibzugriffe aus, als ich Münzen bekommen habe. Wenn wir das zeigen können, dass das sozusagen immer ausreicht, dann ist die Aussage bewiesen.

18:46 Und um das zu zeigen, muss man sich anschauen, was zwischen dem letzten Kopieren und dem jetzigen, dem nächsten kopieren passieren kann. mich das vielleicht auch noch mal kurz ähm versuchen grafisch festzuhalten.

19:04 Wir sind jetzt in dem Zustand, dass das Array komplett voll ist, sonst werden wir nicht in dem teuren Pushzustand. Also, wir würden gerne hier ein neues Element einfügen, aber da ist gar kein Platz. Das heißt, ich muss verdoppeln.

19:19 Dann habe ich all diese Elemente hier zu kopieren und das neue Element hier einzufügen. Was war die Situation beim letzten kopieren? Und das ist die Stelle, an der wir uns das Leben einfacher machen, weil es nur Einfügungen gibt. Das letzte Kopieren war, wenn das letzte Mal, als das letzte Mal das Array voll war und wir verdoppelt hatten, da war das Array eben halb so groß, wie es jetzt gerade ist. Sonst hätten wir es nicht auf diese Größe jetzt gebracht. Das heißt, damals waren wir hier angekommen. Alles, was danach kommt müssen neue Pushes gewesen sein, die also nach diesem Kopierschritt kamen. Ja, jeder von diesen enhalbe Push Aufrufen hatte zwei Münzen übrig. Eine Münze bleibt hier und eine gibt er an den Nachbarn. Eine Münze bleibt hier, eine gibt er an den Nachbarn. sodass auf magische Weise, sobald ich hier hinten angekommen bin mit dem letzten, ich genau für jeden auf der linken Seite auch eine Münze angespart habe. Wenn es also dann hier zu diesem nächsten Push kommt, der das Kopieren auslöst, hat jedes Element im Array eine Münze vor sich liegen.

20:47 Dementsprechend kann ich die alle einsammeln und für das Kopieren damit bezahlen. Eine neue Münze kriege ich dann noch von dem roten Element. An der Stelle sind die ah doch die zwei die zwei zusätzlichen Münzen von dem zusichtelement hier. Die muss ich auch direkt wieder einsetzen. Ja, Und das geht ja auch mal so weit. Die Rechnung geht auf, weil diese hier diese Pushes werden doppelt belastet. Jeder von diesen n halbe Pushes muss quasi für zwei zukünftige Schreibzugriffe zahlen. So ein bisschen Schneeballsystem, aber ähm eins in dem insofern aufgeht äh na ja, es wächst exponentiell, insofern ist es ein Schneeballsystem. Ich denke, das ist äh ist so der Punkt, aber trotzdem sind die Kosten für jeden einzelnen äh konstant. Natürlich gibt's hier diese Initiatoren des Schneeballsystems, die sozusagen auf Kosten der anderen ganz oft bewegt werden. Wenn Sie mögen, ist da eine Parallele äh da. Aber das System geht auch ähm ich habe nie eine Operation, eine Kopieoperation, für die ich nicht bezahlen kann von dem angesparten Kapital.

22:24 Okay, das sind also diese verdoppelt Verdopplungsarrays. Ähm, lassen Sie mich nur noch einen Kommentar anbringen, weil unser Code hier ja auch mal das Array wieder verkleinert. Ich hatte gesagt, die Analyse machen wir nicht im Detail, aber ich möchte auf einen Punkt hinweisen. Sie müssen hier mit dieser Invariante ein bisschen Luft lassen. Also, man könnte hier versucht sein, ein halb C hinzuschreiben. Dann wäre ich nicht so großzügig mit dem Speicherplatz und würde also nicht so viel leeren Platz vorhalten. Wenn ich das mache, dann kann es mir aber passieren, dass ich in der Abwechslung abwechselnden Folge von Push und Pop vergrößere, dann wieder verkleinere, weil vielleicht, wenn sie es nicht ganz so extrem machen, muss ich zwei dreimal Push machen, dann bin ich zu groß, dann mache ich zwei dreimal Pop, dann bin ich wieder unter der Grenze. Das heißt, dann geht die ganze Amortisierung kaputt, weil Sie eine kleine eine Folge von Operationen finden, die ganz oft dieses dieses Kopieren auslöst.

23:23 Hier funktioniert das trotzdem, weil wir genug Platz lassen. Also, wenn ich ein Array verdoppelt habe, dann bin ich von dieser ähm, wenn ich es vergrößert habe, dann bin ich von dieser Untergrenze immer noch Faktor 2 weg. Also von dieser Größe zu der doppelten und zu der halben Größe, da ist jeweils hier so ein so ein Sicherheitspuffer an billigen Operationen, die dann für das nächste kopieren zahlen können. Deswegen muss man hier mit der Wahl der Konstanten ein bisschen aufpassen, auch wenn sozusagen die die der Faktor 2 nicht magisch ist. Es geht nicht beliebige Zahlen.

24:09 Das nur so als ähm als Warnung, weil wir die Analyse nicht im Detail gemacht haben. Äh im Zweifel nehmen Sie z.B. Z und ein Viertel oder die Lösung, die Java macht. dazu dann gleich nach der Pause.

24:45 Das ist mal ausnahmsweise eine etwas vie Frage, wo Sie ganz genau lesen sollen. Da geht's um die Formulierung und um die Inhalte. Das soll keine Fangfrage sein, aber sie müssen sehr präzise lesen. Ähm, dafür dürfen Sie beliebige sind eine multiple Choice Frage, wo sie mehrere Antworten antworten können.

26:45 Also, vorhin hatten wir ein paar mehr. Äh, ich gebe ihn mal noch eins eine Minute. Okay, noch jemand aktiv am Denken oder Tippen? und äh wenn man genau liest, ist auch nur eine richtig.

27:18 Das nämlich kurz erklären, was ich damit meine. Also die erste ist ist nicht richtig, weil es nicht immer genau 2n ist. Das stimmt beim Kopieren gerade oder beim beim Verkürzen oder beim Verlängern, aber dazwischen kann sich n ja ähm verändern, während die die Kapazität gleich bleibt. Einfügen und löschen löschen am Ende der Liste kostet von eins Zeit. Wenn das ohne irgendeinen eine qualifizierendes Adverb oder sowas da steht, dann meint das immer worst case und das ist natürlich nicht richtig, denn worst case muss ich ja kopieren. Das Dritte ist genau, was im Theorem stand, äh eine Folge von M Einfügungen am Ende der Liste. Wir hatten das da Push genannt, aber ansonsten ist das das Statement aus dem Theorem. Ähm kostet O von N + M. dass das ähm ja über die Analyse, wie gesagt, zu dem allgemeinen ähm würde uns vielleicht bisschen zu weit führen. Ähm der letzte Punkt ist auch wieder, das ist das fiese formuliert gewesen. Da steht irgendein Einfügen, nicht nur am Ende. Das kann ich in Marinay natürlich nicht machen.