Data structures.docx

[**Unit Testing 2**](#unit-testing) [**Algoritmes 4**](#algoritmes) [**Datastructures 23**](#datastructures) [**.NET Datastructures 37**](#net-datastructures) Unit Testing ============ #### Wat is Unit Testing? Unit Testing is het proces van het testen van individuele eenheden van code (zoals...

[**Unit Testing 2**](#unit-testing) [**Algoritmes 4**](#algoritmes) [**Datastructures 23**](#datastructures) [**.NET Datastructures 37**](#net-datastructures) Unit Testing ============ #### Wat is Unit Testing? Unit Testing is het proces van het testen van individuele eenheden van code (zoals functies, methodes of klassen) om fouten te identificeren en de kwaliteit van de software te verbeteren. Het wordt uitgevoerd met behulp van Unit Testing Frameworks, zoals MSTest, xUnit en NUnit. #### Waarom Unit Testing? - - - #### Een Unit Test Schrijven Stap 1: Maak een Console App 1. Stap 2: Voeg een MSTest Project toe 1. 2. 3. 4. Stap 3: Stel Dependencies in 1. Stap 4: Voorbeeldcode Toevoegen Voeg een functie toe aan het hoofdproject (Program.cs): Stap 5: Schrijf de Unit Test Vervang de code in UnitTest1.cs in het testproject door de volgende code:  #### Tests Uitvoeren 1. 2. #### Resultaat: De Test Explorer toont of je tests geslaagd zijn of niet, waardoor je snel kunt verifiëren of je code correct werkt. #### Belangrijke Concepten - - Unit Testing Frameworks: MSTest, xUnit, NUnit. In deze samenvatting is MSTest gebruikt. #### Voorbeelden van Asserts - - - - - Algoritmes ========== Complexiteit & Big-O -------------------- #### Wat is een Algoritme? Een algoritme is een stappenplan dat beschrijft wat er moet gebeuren om een bepaald doel te bereiken. Elke stap moet duidelijk en ondubbelzinnig zijn. Algoritmes verwachten input(s), verwerken deze door middel van een reeks stappen en produceren een output. Voorbeeld: Hoogste waarde in lijst getallen - - 1. 2. 3. - #### Soorten Algoritmes 1. 2. 3. 4. #### Hoe \"goed\" is een Algoritme? De kwaliteit van een algoritme wordt beoordeeld op basis van zijn tijdcomplexiteit (hoeveel tijd het kost) en ruimtecomplexiteit (hoeveel geheugen het gebruikt). De groei van deze complexiteiten wordt geanalyseerd met behulp van Big O Notatie. #### Big-O notatie - - - - - - - #### Voorbeeld: CalculateSum } - #### Worst, Best en Average Case - - - #### Grafiek van Complexiteiten - - - #### Voorbeelden - } - -  #### Conclusie De beoordeling van algoritmes gebeurt op basis van hun tijd- en ruimtecomplexiteit, waarbij vooral de worst case (Big O notatie) belangrijk is. De complexiteit wordt gemeten in relatie tot de inputgrootte en geeft inzicht in de efficiëntie van het algoritme. Benchmarking ------------ #### Waarom Benchmarking? Benchmarking in C\# helpt de theoretische complexiteit van algoritmes te toetsen aan de praktijk. Dit is belangrijk omdat naast onze geschreven code ook processen zoals garbage collection invloed hebben op de prestaties. #### BenchmarkDotNet Setup Benodigde Software: - Stappenplan 1. - - - 2. - - - - 3. - #### Voorbeeldprojecten Main Project (Code to Benchmark): Voeg de functies die je wilt benchmarken toe aan Program.cs van ExampleProject. Benchmark Project: - Dit bestand start de benchmark. Het enige wat je hier hoeft te doen, is de BenchmarkDotNet runner aanroepen om de benchmarks uit te voeren. - Dit bestand bevat de benchmarks. We gebruiken de MemoryDiagnoser attributen om zowel tijd als geheugenverbruik te meten. De klasse definieert twee variabelen: - - - -  #### Tests Runnen en Resultaten 1. - - - 2. - - - Benchmarking helpt inzicht te krijgen in de daadwerkelijke prestaties van je code en maakt optimalisatie mogelijk. Recursie -------- #### Wat is recursie? recursie is een techniek waarbij een functie zichzelf aanroept om een probleem op te lossen. #### Base Case Elke recursieve functie moet een base case bevatten om te voorkomen dat deze eindeloos blijft doorgaan. #### Voorbeeld: Blikjes Toren Hoeveel blikjes zijn er nodig om een toren te bouwen met 4 blikjes op de onderste rij? - Tel alle getallen op die kleiner of gelijk zijn aan de onderste rij.  - Los het probleem op door de toren op te splitsen in een kleinere toren. #### Formule Oplossing Gebruik de formule voor driehoeksgetallen  #### Complexiteit: Iteratief vs Recursief vs Formule **Methode** **Tijdcomplexiteit** **Ruimtecomplexiteit** ------------- ---------------------- ------------------------ Iteratief O(n) O(1) Recursief O(n) O(n) Formule O(1) O(1) #### Indirecte Recursie Indirecte recursie treedt op wanneer twee of meer functies elkaar wederzijds aanroepen. #### Iteratief vs Recursief Voordelen en Nadelen **Recursief** **Iteratief** ---------------------------------------- ------------------------------------------- \- Traag \+ Sneller \- Meer geheugenverbruik \+ Minder geheugenverbruik \+ Korter \- Meer code \+ Leesbaarheid bij bepaalde problemen \- Minder leesbaar bij complexe problemen Recursie is vooral nuttig bij het werken met bepaalde datastructuren zoals boomstructuren. #### Conclusie Recursie kan een krachtige techniek zijn, maar het is belangrijk om de voor- en nadelen af te wegen. Voor sommige problemen biedt recursie een elegantere en eenvoudigere oplossing, terwijl iteratie vaak efficiënter is in termen van snelheid en geheugenverbruik. Sorteer Algoritmes ------------------ ### Bubble sort een algoritme waarbij je twee elementen met elkaar vergelijkt en van plaats wisselt indien nodig. ### Selection sort een algoritme waarbij je de lijst gaat opdelen in een *gesorteerd* en een *niet-gesorteerd* deel. Je gaat telkens op zoek naar het kleinste element in het *niet-gesorteerde* deel, en voegt dit toe aan het einde van het *gesorteerde* deel. ### Insertion sort ook dit is een algoritme waarbij je de lijst gaat opdelen in een *gesorteerd* en een *niet-gesorteerd* deel. Hier ga je telkens een nieuw element uit het *niet-gesorteerde* deel toevoegen aan het einde van het *gesorteerde* deel. Het nieuwe element gaat vervolgens op zoek naar de juiste plek in het *gesorteerde* deel. ### Quick sort een recursief zoek-algoritme, waarbij je de lijst telkens opdeelt in 2 lijsten: één lijst van alle elementen die kleiner zijn dan het laatste element, en één lijst van alle elementen die groter zijn dan het laatste element. Vervolgens pas je dit ook weer toe voor elke nieuwe lijst, tot elke lijst nog maar één element bevat. Zoek Algoritmes --------------- ### Linear search Linear Search is een eenvoudig zoekalgoritme dat werkt door elk element in een lijst één voor één te vergelijken met een zoekwaarde totdat het juiste element wordt gevonden. De uitkomst van een linear search kan variëren afhankelijk van de implementatie: - - - Voordelen - - Nadelen - -  ### Binary search Binary Search is een zoekalgoritme dat vertrekt vanuit een gesorteerde lijst. Het algoritme bekijkt steeds het middelste element in de lijst. Is de zoek-waarde groter,\ dan wordt de eerste helft vanaf dan genegeerd. Is de zoek-waarde kleiner,\ wordt de tweede helft genegeerd.\ Dit idee wordt recursief toegepast, tot de middelste waarde gelijk is aan de zoek-waarde. Wat je terugkrijgt van het linear search algoritme is afhankelijk van de implementatie: - In dit zoekalgoritme kan je geen LinkedList gebruiken, want een LinkedList heeft geen idee wat\ de *middelste* waarde is. Voordelen - Nadelen - ### Hashtables Een hashtable is geen zoek-algoritme. Het is een datastructure die het zoeken erg snel maakt. Een hashtable bestaat uit een arrray met een vooraf gedefinieerde grootte Daarna voeg je elke element een voor een toe: 1. 2. 3. #### Nadelen de lijst moet bestaan uit integers **Omgaan met Strings door een Hashtable te Gebruiken**  de integers in de lijst moeten opeenvolgend zijn **Omgaan met Niet-Opeenvolgende Waarden** Voor lijsten met niet-opeenvolgende waarden gebruiken we een truc waarbij het laatste cijfer van de waarde de index aangeeft: de integers in de lijst moeten beginnen bij de waarde 0 **Omgaan met Offsets** Als de lijst niet bij 0 begint, kunnen we offsets als volgt behandelen:  Een hashtable heeft een vaste lengte Een hashtable maakt gebruik van de lengte van de array om elk element een juiste plek te geven.\ Wanneer de array groter of kleiner gemaakt wordt, moet elk element een nieuwe plek gegeven\ worden. Dit is geen groot nadeel. Door voorzichtig om te gaan met de hashtable, en op voorhand\ een grootte te bepalen die groot genoeg is, zal deze operatie weinig moeten gebeuren. waardes die verschillend zijn kunnen toch dezelfde hash-waarde hebben **Omgaan met Collisions door LinkedLists te Gebruiken** Om botsingen te beheren, gebruiken we een lijst van linked lists in de hashtable:  } Datastructures ============== Stack ----- = lineaire datastructuur volgens LIFO Bevat 2 functies: - - Queue ----- = lineaire datastructuur volgens FIFO Bevat 2 functies: - - Heeft 2 pointers: - - Linked List ----------- #### Wat is een Linked List? Een Linked List is een lineaire datastructuur In een lineaire datastructuur staan de elementen op één rij achter elkaar, je zou deze datastructuur dus kunnen vergelijken met een array. Een Array heeft echter heel wat nadelen: - De Linked List lost al deze nadelen op, maar heeft in de plaats daarvan enkele nieuwe nadelen.\ Zo is een Linked List bijvoorbeeld trager om te doorzoeken, sorteren of uit te lezen. Een element in een linked list wordt een Node genoemd. Een Node bestaat uit: - - Een linked list houdt ook altijd een referentie naar: - - ### Singly Linked List Een Singly Linked List houdt enkel een referentie bij naar de volgende Node. #### Methodes Node Class Singly Linked List Class ####  Find De Nodes van een Linked List zitten verspreid in het geheugen. De enige manier om een bepaalde Node te vinden is door één voor één elke Node af te lopen, waarbij je begint vanaf de eerste node. - - AddLast Een element achteraan toevoegen doe je zo: -  AddFirst Uiteraard is het ook mogelijk om vooraan een element aan de lijst toe te voegen.\ De code hiervoor is gelijkaardig. AddAfter Eén van de grote voordelen van een Linked List is dat je elementen gemakkelijk kunt invoegen\ in het midden van de lijst. Je kan dit doen op 2 manieren, de eerste manier is na een bepaalde node. -  AddBefore De 2e manier is voor een bepaalde node. AddBefore werkt echter iets ingewikkelder dan de AddAfter,\ omdat een Node in een Singly Linked List enkel een referentie heeft naar de volgende Node\ (en niet naar de vorige). De complexiteit is daarom heel anders dan bij AddAfter omdat we (in het slechtste geval) de volledige\ lijst moeten doorlopen ! - RemoveFirst Naast het toevoegen moeten er uiteraard ook elementen kunnen worden verwijderd.\ Typisch gaan we dan eerst met de **Find** methode de node gaan opzoeken in de lijst en kunnen we\ via een **Remove** methode dan aangeven dat we deze node willen verwijderen.\ Omdat er echter een verschil is in time complexity tussen het verwijderen van het eerste element en\ de andere elementen, voorzien we hier voor de duidelijkheid een aparte methode om de code hiervan\ apart te kunnen bekijken en beoordelen ten opzichte van de andere Remove methodes. Na het uitvoeren van deze methode zal er geen enkele verwijzing meer zijn naar de node die verwijderd werd. Daarom zal de node automatisch worden opgekuist door de.NET garbage collector.  Remove Een willekeurige Node verwijderen betekent dat we de lijst weer (worst case) volledig moeten doorlopen: - ### Doubly Linked List Geeft een referentie naar beide de volgende Node, maar ook naar de vorige Node. Waardoor je de Linked List in beide richtingen kan doorlopen Voordeel is dat AddBefore en Remove nu vereenvoudigd kunnen worden #### Methodes Node Class  Doubly Linked List Class #### AddBefore  Remove Binary Search Tree ------------------ Een Binary Search Tree (BST) is een niet-lineaire datastructuur die elementen op een gesorteerde, binaire, hiërarchische manier organiseert. Elke node in een BST heeft maximaal twee kinderen: een left child en een right child. #### Belangrijke Concepten - - - - #### Regels 1. 2. #### Toevoegen van Elementen Elementen worden toegevoegd door te beginnen bij de root node en naar beneden te gaan: - - - #### BST Methodes Insert Voegt een nieuwe waarde toe aan de BST. 1. 2. 3. 4. Remove Verwijdert een specifieke node uit de BST. Er zijn drie situaties: 1. 2. 3. #### Gebalanceerd vs. Ongebalanceerd - - #### C\# Implementatie Node Class  Binary Search Tree Class Insert Method  Remove Method  #### Samenvatting Een BST is een efficiënte manier om gegevens op te slaan en op te halen in een gesorteerde volgorde, mits de boom gebalanceerd blijft. Door gebruik te maken van recursieve methoden voor het toevoegen en verwijderen van nodes, kan de structuur eenvoudig worden beheerd en bijgewerkt. In C\# worden de belangrijkste methoden geïmplementeerd met behulp van recursie voor leesbaarheid en eenvoud..NET Datastructures =================== Generics -------- #### DRY (Don\'t Repeat Yourself) Principe en Generics in C\# Het DRY-principe is een belangrijk concept in de softwareontwikkeling dat stelt dat code niet onnodig herhaald moet worden. In deze samenvatting laten we zien hoe we generieke datastructuren en methoden kunnen gebruiken in C\# om herhaling te vermijden. #### Generieke Klassen: Stack We beginnen met een generieke stack-implementatie. In plaats van afzonderlijke Stack\_string en Stack\_int klassen te hebben, gebruiken we één generieke Stack\ klasse.  #### Generieke Methodes Generieke methodes stellen ons in staat om methodes te schrijven die met elk type kunnen werken. Hier is een voorbeeld van een generieke methode die een array maakt met twee waarden: #### Beperkingen voor Generics Om bepaalde functionaliteiten zoals vergelijkingen te garanderen, kunnen we beperkingen toepassen op generics. Bijvoorbeeld, we kunnen vereisen dat het type T Samenvatting Door gebruik te maken van generics in C\#, kunnen we datastructuren en methodes schrijven die met verschillende datatypes kunnen werken zonder dat we dezelfde code moeten herhalen. Dit maakt onze code flexibeler, herbruikbaarder en onderhoudsvriendelijker.  Compares -------- Voor het sorteren van objecten in C\# moeten we objecten met elkaar kunnen vergelijken. Dit wordt meestal gedaan met behulp van de IComparable\ interface of de IComparer\ interface. #### IComparable\ Interface - - #### IComparer\ Interface - -  #### Waarom IComparable en IComparer? - -