Wir brauchen datenstrukturen mit denen wir gut und günstig Daten organisieren können
Die Antiken kulturen haben laut Buchin auch schon arrays und Listen genutzt, zwar auf steintafeln oder so, aber ich weiss nicht: der compiler war bestimmt interessant
in diesen Knoten sind zwei simple sachen gespeichert
Inhalt
Der Pointer zum nachfolgeknoten
Wenns keinen nachfolger gibt, dann pointen wir ins narnia, auch bekannt als "nullpointerexception thown in 0x993a492f938d74e892"
Es gibt mehrere "Simple" Implementationen von den dingern
Man kann praktisch einen ewigen Loop mahen, indem man den ersten Knoten mit einem "Dummy-Knoten" ersetzt
Wenn man dann einfach etwas hinzufügt und in den nullpointer runnen würde, landet man einfach wieder beim Dummy-Knoten! BOAH WIE BRILLIANT ICH KANN DAS FAST ALLES NICHT MEHR GLAUBEN ICH BIN JA SO ERSTAUNT
Der Vorteil daran ist, dass man das Relativ einfach modifizieren kann usw.
Um sachen aus der Liste zu löschen muss man einfach nur die pointer neu setzen, was halt schön einfach ist, weils einfach Variablen von konstanter größe sind, deswegen läuft der kram auch in konstanter Zeit
Leider kann man in einer verketteten Liste leider nicht direkt auf Element 9203748243 zugreifen, sondern man muss sich halt ein wenig "durchhangeln"
ausser man heisst Lua, oder buchin, some of the time
In der vorlesung fangen wir einfach da an was gerade passt, also 0 oder 1, das ist aber hart doof weil das massiv unübersichtlich ist und alles nur für verwirrung sorgt
In beschränkten arrays hängen die Kosten davon ab, ob der kram sortiert ist oder nicht
wenn das unsortiert ist, ist das Price-to-Performance Ratio meisstens schlechter
Häufig sind unbeschränkte arrays wünschenswert, aber die gibt es nicht, wenn man nciht gerade eine komische dynamische programmiersprache ist oder natürlich T-Script ist.
Man kann unbeschränkte Arrays mit beschränkten arrays "emulieren", indem man den kram halt immer in größere oder kleinere arrays überschreibt usw.
Das ist lustig, weil man dann sehr viel code extra schreiben muss dafür, aber das ist dann halt lustig
Die kosten dafür sind aber nen bissl doof, denn wenn man
Einfügen auch O(1) wenns unsortiert ist, in sortierten arrays dann O(n) weil man ja dann die restlichen tiele immer wieder neu sortieren muss bzw. dann halt passend einfügen muss
wenn man das "Halbieren und verdoppeln" betrachtet, sieht man dass das sehr teuer ist.
wenn wir aber nicht so viele Jetons ausgben wollen, kann man sich bewusst machen, dass das ja nicht so soft passiert, weil das ja am ende einfach immernoch relativ selten passiert
Wir schauen uns da mal anhand von dem tollen k-bit binärzähler an
Was wir jetzt machen:
Wir legen uns neben jede eins einen jeton
Das ist okay, weil wir ja immer nur eine eins pro operation schreiben
Das ist gut, weil wir diese "angesparten" Jetons dann nutzen können, um die wieder zu nullen zu machen, wenn wir das dann irgendwann unweigerlich machen wollen
Wir müssen jetzt duese Invariante dann so zeigen
Jeder bit der auf 1 steht ist ein Jeton Guthaben
jeden bit den wir von 0 auf 1 flippen kostet diesen Jeton Guthaben
So können wir nie weniger als 0 einsen haben, was toll ist
wenn wir also eine 0 zu einer 1 machen, "belohnen" wir das mit Jetons
Wir haben bei jeder operation kosten, aber nur das was wirklich "schlimm" ist berechnen wir irgendwie
Das wollen wir uns wieder krass überlegen, und das machen wir dann am besten mit der "tollen" bankkontomethode, damit wir weiterhin alles mit unserer lieblingswärung: Jetons tracken können, denn das macht das ja alles so viel einfacher und spaßiger
wenn wir hier die bankkonto methode nutzen, dann sind die operationen das hier:
Einfügen ist +2 Jetons
Löschen ist -1 Jeton
Kopieren pro eintrag dann auch -1 Jeton
So sichern wir, dass wir immer genug jetons zum Kopieren haben