5EWI/LWI/WWI Herhalingsopdracht DW3: Sorteren en Zoeken

2.1. Bronnen Vermelden!

2.2. Werkbestanden

2.3. Evaluatie

3.1. Versamel verschillende sorteer-algoritmen!

3.2. Vergelijk de looptijd van de verschillende algoritmen!

lengte_reeks = 1e5

from random import shuffle
test_reeks = [n for n in range(int(lengte_reeks))]
shuffle(test_reeks)

4.1. Test Case: Een Boek

1. Data
   

   Data: the text of Charles Darwin (1859) “On the Origin of Species by Means Of Natural Selection” (gratis beschikbaar hier: https://www.gutenberg.org)

   • download de tekstbestand hier (1MB): ../dat/darwins_words.txt

   Je kan hem inlezen met de volgende code. (Noot: het bestand moet in dezelfde map liggen als jouw programma.)

   with open('darwins_words.txt', 'r') as fi:
       tekst = fi.read().split('\n')
   
   print(len(tekst), "woorden")
   

   We gaan nu proberen om een woord in het boek te vinden.

2. Zoeken
   

   Maak er een functie “Woordvinder” aan!

   - De functie krijgt een zoekwoord binnen.
   - Maak een index aan die begint met "1".
   - Itereer in een lus over alle woorden van de "tekst" (dus, over het boek).
       - Indien het momentele woord op het zoekwoord lijkt, geef de index terug.
   - Indien het woord niet in het boek staat, geef het getal "0" terug.
   

   Testen:

   • Vind de positie van de volgende woorden:

   zoekwoorden = ["utilitarian", "selection", "vicissitudes", "uselessness", "Škoda"]
   

3. Looptijd
   

   Je kan met de volgende code een aantal toevallige zoekwoorden uit je tekst kiezen.

   import random
   aantal_zoekwoorden = 50
   zoekwoorden = random.sample(tekst, aantal_zoekwoorden)
   

   • Hoe hangt de looptijd van jouw Woordvinder af van het aantal zoekwoorden?
   • Maak er een grafiek aan waarin je de samenhang toont.

4.2. Use Case: Search Wikipedia

1. Naïve Search
   

   Nu gaan we zien hoe snel we een pagina in Wikipedia kunnen terugvinden. We gebruiken een lijst met wikipedia-paginatitels [bron].

   • download de tekstbestand hier (55MB): ../dat/wikipedia_entries.txt

   Je kan hem inlezen met de volgende code. (Noot: het bestand moet in dezelfde map liggen als jouw programma.)

   with open('wikipedia_entries.txt', 'r') as fi:
       wiki_index = fi.read().split('\n')
   
   print(len(wiki_index))
   

   We gebruiken opnieuw een aantal zoekwoorden.

   zoekwoorden = ['Complexiteitsgraad', 'Phascolarctos cinereus', 'Škoda Fabia', 'Zwolle']
   

   • Zoals boven: hoe snel kan jouw Woordvinder deze Wikipedia-pagina’s terug vinden?
2. Binary Search
   

   Je gaat een nieuwe algoritme aanmaken: een “Binary Search”, nl. “Bisectie”. Die algoritme heeft wel een alfabetisch gesorteerde reeks nodig (wat hier gegeven is).

   Maak er een functie “Bisectie” aan:

   - Jouw functie krijgt er een zoekwoord binnen.
   - maak er een kopie aan van de zoeklijst, namens "werklijst"
   + maak er een resultaatindex aan en initialiseer hem met de waarde "0".
   - Ga in een oneindige lus ("while True: ...")
       - Vind er de index van het middelste element van jouw wiki_index lijst (= "werklijst").
       - Vind het middelelement.
       - Vergelijk het zoekwoord met het middelelement:
       - Indien het zoekwoord precies het middelste element is:
           - geef de som van resultaatindex en middelindex terug.
       - Indien het zoekwoord "kleiner" is (bv. "beta < gamma"):
           - werk verder met de linke helft van jouw lijst (tot aan de index van het middelelement) door de werklijst aan te passen.
       - Indien het zoekwoord "groter" is (bv. "kappa > gamma"):
           - werk verder met de rechte helft van jouw lijst (vanaf de index van het middelelement) door de werklijst aan te passen.
           + verhoog de resultaatindex om de middelindex.
   
   

   Tipp: je kan deze algoritme eerst met het “Boek”-voorbeeld boven oefenen.

3. Complexiteit
   
   • Vergelijk de gemiddelde looptijd van de “Binary Search” met de “Naïve Search” en de python-functie “<list>.index(zoekwoord)”!