Timing-rapporteurs

Op deze pagina, ga je een algoritme-timer maken om de efficiëntie van algoritmes te vergelijken.

De titel van deze pagina heeft twee betekenissen: Je bouwt een "timing-rapporteur" die rapporteurs timet.

Snap! stelt ons in staat om te melden hoe lang het duurt voordat een programma is voltooid.

  1. Zoek in het Waarnemenpalet voor de current (date)-rapporteur. Sleep het in het scriptgebied. Selecteer van het invoermenu time in milliseconds (tijd in milliseconden).
  2. Geen Afbeelding
  3. Klik meerdere keren op het blok. Let op de resultaten.
  4. Open het "H5L3-RapporteurTimer"-project dat je hebt opgeslagen op de vorige pagina.
  5. Download deze library: U5L3functiontimer.xml, en sleep het bestand in je Snap!-applicatie om het te importeren.

Aan de onderkant van het Variabelenpalet staat een block dat time function heet. Het pakt een rapporteur (met invoeren al ingevuld), berekent het resultaat en rapporteert hoe lang het duurde om de berekeningen te doen (in milliseconden).

Je kan het lijst vanblok vervangen met iedere rapporteur. Je kan time function aanpassen om te leren hoe het werkt.
Geen Afbeelding

In dit voorbeeld duurde het 27 milliseconden om de lijst met gehele getallen van 1 tot 1000 te berekenen. (Het aantal dat u ziet, hangt af van hoe snel uw computer is en welke andere programma's erop worden uitgevoerd.)

Dit is hoe time function werkt:
Geen Afbeelding

  1. Het maakt een variabele dat start time heet en en zet het gelijk aan de huidige tijd.
  2. Het roept de rapporteur aan die je wil timen en negeert het resultaat.
  3. Wanneer de rapporteur klaar is pakt het weer de huidige tijd en trekt het af van de start time.

  1. Gebruik time function om Alex' en Bo's manieren van getallen van 1 tot n optellen te vergelijken. Probeer het met een aantal verschillende grote getallen om te zien hoe verschillend de algoritmes zijn qua tijd om de uitkomst te berekenen.
    Alex' en Bo's algoritmes lossen hetzelfde probleem om maar zijn vrij verschillend qua efficiëntie. Stel je het verschil voor wanneer je de getallen van 1 tot 1,000,000...
    Geen Afbeelding
    Geen Afbeelding
  2. De efficiëntie van een algoritme maken een groot verschil. Soms is een efficiënt algoritme nodig om grote versies van een probleem op te lossen.
  3. In Les 1 , heb je twee rapporteurs gebouwd die de positie van een element in een lijst geven:

    Een lineaire zoekopdracht betekent dat je de lijst doorzoekt voor ieder item.

    Een binaire zoekopdracht betekent dat je een gesorteerde lijst in twee helften verdeelt bij iedere stap.

    • De rapporteur position of () in unsorted list werkt voor elke lijst door element-voor-element de lijst te doorzoeken tot je een match vindt. Dit heet een lineaire zoekopdracht omdat het programma van het begin van de lijst in een rechte lijn zoekt tot hij een match vindt.
    • De rapporteur position of () in sorted list werkt op gesorteerde lijsten door herhaaldelijk de lijst te verdelen in twee delen van gelijke grootte en gebruikt de middelste waar om te beslissen welke helft nu doorzochtgaat worden om de match te vinden. Dit heet een binaire zoekopdracht omdat binair "twee" betekent en het algoritme de lijst in twee delen verdeelt.
    Beide werken op gesorteerde lijsten. Vergelijk ze voor een aantal lange gesorteerde lijsten en maak een tabel van je bevindingen. Mogelijk moet je zeer grote lijsten gebruiken, bijvoorbeeld 1000 of 2000 items, om betekenisvolle resultaten te krijgen. Welk algoritme is sneller?
    Is het andere algoritme ooit sneller?
  4. In de hele cursus heb je veel algoritmes gemaakt. Probeer ze de timen, hier zijn een paar voorbeelden:

    Time je algoritmes met invoer van verschillende grootte en beschrijf het gedrag dat je ziet. Gebruik weer grote invoeren voor betekenisvolle resultaten.

  5. "H5L3-Timer" Geen Afbeelding
Terug Volgende