Was ist ein Array? | mit Animationen leicht erklärt | Algorithmen und Datenstrukturen
developbär
https://www.youtube.com/watch?v=VAc6y0m7CQU

Transkript (automatisch erstellt)

0:00 in diesem Video erkunden wir die erste von insgesamt 8 Datenstrukturen dieser Videoreihe und heute dreht sich alles um race
0:07 sind wichtig da sie sehr schnell im Zugriff auf Elemente durch die Angabe eines Index sind wenn ich aus einem Array das Element an den X2 haben will
0:14 kann ich auf diese sofort zugreifen das Element an den Index muss nicht erst wie bei anderen Datenstrukturen gesucht werden dafür besitzen andere Nachteile
0:22 aber nach diesem Video wirst du die Vor- und die Nachteile in der Tiefe verstehen kennst du die drei Eigenschaften die in Array ausmachen das Erics linear sind
0:30 ist die erste Eigenschaft das bedeutet dass die Elemente eine Reihenfolge haben es gibt also ein Element an der ersten Position an der zweiten und so weiter
0:37 viel häufiger als Position wirst du aber einen anderen Begriff hören und zwar Index oder die Mehrzahl davon Indizes die Zählweise der Indizes ist etwas
0:46 gewöhnungsbedürftig der erste Index startet nämlich bei Null und nicht intuitiver Weise bei eins der Index das letzte Elements ist die Anzahl der
0:52 Elemente -1 die -1 kommt daher da wir das erste Element mit den x0 angeben und nicht mit eins die zweite Eigenschaft ist dass die Größe eines Aeros statisch
1:02 ist damit ist gemeint dass die Größe und veränderbar ist dann wenn wir ein area erzeugen gehen wir die Größe mit an sie lässt sich danach aber nicht mehr
1:08 verändern dass alle Elemente vom gleichen Datentypen sind ist die dritte und die letzte Eigenschaft in Eric kann also nur
1:14 Zahlen oder stringsspeichern aber nicht beides gleichzeitig falls ihr das etwas abstrakt vorkommt hilft dir vielleicht die Vorstellung eines Arrays als
1:21 Federtasche denn ja eine Federtasche erfüllt die drei Eigenschaften eines Arrays alle Stifter haben einen festen Platz und du weißt welcher Stift an der
1:29 ersten Position zweiten und so weiter ist die Größe einer Federtasche variiert nicht sie besitzt nur Platz für eine bestimmte Anzahl an Stifte diese
1:37 Eigenschaften gelten für Sprachen WC Java und viele weitere aber falls du in der Vergangenheit vielleicht mit Javascript oder Pfeifen programmiert
1:43 hast könntest du dich vielleicht wundern warum die Eigenschaften nicht auch auf sie zu treffen denn sie erlauben es in einem Array unterschiedlich viele
1:49 Datentypen zu speichern und sogar unbegrenzt viele davon zumindest scheint es auf den ersten Blick so denn unter der Haube erfüllen sie alle die gleichen
1:55 Eigenschaften die wir uns verfolgenden genauer anschauen werden und übrigens hi ich bin Roman von developer weißt du wie Daten gespeichert werden
2:04 ein Speicherplatz ist ein bald groß unterschiedliche Datentypen benötigen unterschiedlich viele Bytes zum Beispiel ist ein bulien
2:13 beide ist eine eindeutige Adresse zugeordnet die ein Hexadezimalzahlen angegeben ist die Adresse gibt die Position im Speicher an
2:21 wenn wir ein Array definieren wird im Speicher genau so viel Platz für das definierte Array reserviert wie wir angegeben haben wollen wir ein Array und
2:27 das drei intergepassen werden also drei mal vier Bytes pro integer reserviert wir greifen wir jetzt auf die Elemente zu wenn wir ein Index angegeben
2:39 dafür gibt es eine Formel die sofort die richtige Adresse im Speicher berechnet und sie ist auch der Grund weshalb der Zugriff auf die Elemente so performante
2:46 ist dafür nehmen wir die erste Adresse die das Array im Speicher belegt und addieren das mit dem Ergebnis der
2:52 Multiplikation aus der Anzahl an beides die ein Datentyp braucht und dem Index auf dem bezugreifen wollen
2:59 ich will auf den 6.0 zugreifen ich nehme also die erste Adresse als nächstes die Anzahl an beides in diesem Fall 4 dein integer für weit groß ist
3:08 dann brauche ich noch den Index also die 0 nun rechne ich alles zusammen und erhalte die erste Adresse des Elements an Index 0
3:17 das funktioniert auch wenn ich auf Next 2 zugreifen will ich nehme wieder die erste Adresse die für beides und den Index also die zwei multipliziere und
3:25 addiere alles zusammen und springe zum Element an den nächsten zwei und warum können wir nur Elemente des gleichen Datentyp speichern das hängt
3:35 mit der Formel zusammen wenn die Elemente unterschiedlicher weit groß sind ist unklar mit wie vielen beides für die Adresse des Elements berechnen
3:40 sollen das komische aber ist das Pfeifen und Javascript das hinbekommen dass sie
3:47 unterschiedliche Datentypen speichern hast du eine Idee wie sie das machen in Javascript ist es so dass das Element mit dem größten Datentyp die Anzahl an
3:56 Bytes bestimmt die kleinen Elemente müssen sich also an das größte anpassen dadurch dass dann alle Elemente wieder gleich viele Beiz haben geht die Formel
4:03 wieder auf Python auf der anderen Seite löst das ganz anders sie speichern in dem Array nicht die Elemente selbst sondern die
4:09 Adressen der Elemente wenn wir ein Element also auslesen wollen lesen wir die Adresse aus und springen dann im Speicher zum jeweiligen Element
4:17 und wieso sind Arrays nun statisch das hängt auch wieder mit der Formel zusammen aber auch damit wie Daten im Speicher hinterlegt werden dennoch
4:23 andere Daten werden gespeichert und vielleicht auch direkt an einem an würden wir jetzt ein weiteres Element speichern geht die Formel nicht mehr auf
4:30 da die Elemente im Speicher verteilt liegen wie funktionieren die typischen Operation mit Erics beginnen wir mit dem
4:37 Zugreifen auf ein Element das ist das was so besonders macht da wir sofort auf ein Element an einem Index zugreifen das liegt an der Formel die wir uns gerade
4:44 erst angeschaut haben die Laufzeit des Zugreifens ist auch von eins also sehr schnell falls du mitlaufzeiten noch nicht vertraut bist verlinke ich dir ein
4:52 Video von mir indem ich erkläre was Laufzeiten sind wenn wir Elemente einem area hinzufügen wollen können zwei worst cases Eintreffen der erste Worst Case
4:59 ist dass wir am Anfang des Airways ein neues Element hinzufügen denn in diesem Fall müssen alle Elemente die danach kommen verschoben werden
5:10 der zweite Worst Case ist dass unser Array voll ist und wir ein weiteres Element zu diesem Array hinzufügen wollen in diesem Fall müssen wir ein
5:16 neues Array erstellen das größer ist als das alte dann müssen wir alle Elemente übertragen
5:23 und können das neue Element hinzufügen ich will dir noch mal kurz zeigen was ein Speicher passiert und zwar haben wir
5:31 unser Ray aber auch andere Daten die gespeichert sind jetzt wollen wir unser Ray um eins größer haben und müssen im Speicher nach Speicherplatz suchen wo
5:38 dieses reinpassen würde durch die beiden worst cases kann das Hinzufügen von neuen Elementen so
5:47 langsam sein konkret sprechen wir hier von N kommen wir zum Löschen hier ist das wieder so dass wir Elemente verschieben
5:54 müssen wenn wir das erste Element löschen müssen alle Elemente die danach kommen nach links verschoben werden
6:03 deshalb ist die Laufzeit des Löschens wieder hoch von innen die letzte Operation die ich zeigen will ist das suchen wenn wir ein bestimmtes Element
6:10 suchen müssen wir Element für Element abfragen ob es das ist welches besuchen im Worst Case müssen wir alle Elemente überprüfen weshalb die Laufzeit ovn ist
6:22 insgesamt lässt sich sagen dass Airways nicht besonders flexibel sind doch eigentlich müsste ich sagen dass statische Arrays nicht flexibel sind
6:28 denn dynamische Eric sind es zumindest ein bisschen denn dynamische Arrays und statische Arrays die ihre Größe automatisch
6:36 Anpassung ohne dass du es merkst während wir bei statischen Größe immer manuell anpassen müssen und genau das ist das Geheimnis von Programmiersprachen wie
6:43 Pfeifen oder Javascript sie verwenden dynamische Arrays sie funktionieren so dass sie zwei unterschiedliche Größen haben einmal die Kapazität das ist quasi
6:51 der reservierte Speicherplatz und dann ist dann noch die Länge das ist die Anzahl der Elemente die bereits gespeichert sind
6:57 ist die Länge genauso groß wie die Kapazität ist das dynamische Array voll das bedeutet dass die Kapazität nun erhöht werden muss manche
7:04 Programmiersprachen verwenden da den Faktor 1,5 und andere zwei beim Vergrößern wird im Hintergrund also im Speicher einfach nur ein neues
7:11 statisches Array erzeugt was nun die Länge der neuen Kapazität hat nun werden alle Elemente aus dem alten statischen Array in das neue übertragen deshalb ist
7:19 die Laufzeit von N da wir die Kapazität und damit auch die Größe des statischen Race deutlich erhöht haben müssen wir dieses eventuell gar nicht mehr
7:26 vergrößern man spricht dann von einer Amortisierung das bedeutet dass ich einen Aufwand irgendwann für eine bessere Laufzeit
7:33 ist es so dass wenn wir ein neues Element hinzufügen solange das Array nicht voll ist und wir keine Elemente in der Mitte oder am Anfang hinzufügen
7:40 müssen keine Elemente verschoben werden deshalb ist die Laufzeit von 1 und das auch nur wenn man hofft dass das dynamische area inzwischen groß genug
7:47 ist also nicht mehr wachsen muss um neue Elemente hinzuzufügen das ist sicher um eine amortisierte Laufzeit handelt wird durch das Plus symbolisiert
7:55 in diesem Video hast du zwei Datenstrukturen kennengelernt das statische und das dynamische sind super schnell wenn es um den Zugriff auf einen
8:02 Element an einem bestimmten Index geht dafür sind andere Operationen relativ langsam dynamische haben den Vorteil dass sie mit der Anzahl der Elemente
8:10 mitwachsen das Hinzufügen neuer Elemente am Ende eines dynamischen Arrays hat eine amortisierte Laufzeit von 1 im nächsten Video zeige ich dir was
8:19 LinkedList sind