Timing Reporters

EK: 4.2.4D, 4.2.4F
Blue button feedback:
The title of this page has two meanings: You will build a "timing reporter" … that times reporters.

Snap! allows us to report how long a program takes to finish.

  1. In the "Sensing" palette, look for the current (date) reporter. Drag it into the scripting area. From its input menu, select time in milliseconds.
    2. current (time in milliseconds) reporting 1454091401280
  2. Click the block several times. Note the results.

This block can be used to time how long a reporter takes to output. Here’s an algorithm:

  1. Download this library and save it on your desktop. It provides a block called time function that takes any reporter (with its inputs filled in), computes the result, but reports how long it took to do the computation. The answer will be in milliseconds.
  2. Open the project U5L3-ReporterTimer that you saved on page 1 of this lab. Drag in the U5L3functiontimer library that you just downloaded.
You can replace the list from block with any reporter. You can edit time function to see how it works.
time function (list between (1) (1000)) reporting 27

In this example, it took 27 milliseconds to compute the list of integers from 1 to 1000. (The actual number will depend on how fast your computer is.)

  1. Use time function to compare Alphie and Betsy's ways of adding the integers from 1 to n. Try it with several different large numbers to see just how different the algorithms are in terms of the time it takes to compute their outputs.
    Alphie and Betsy’s algorithms solve the same problem but are quite different in efficiency. Imagine the difference when adding the integers from 1 to 1,000,000…
    time function (betsy way (2000)) reporting 1
    time function (alphie way (2000)) reporting 187
    2. The efficiency of an algorithm can make a huge difference. Sometimes, an efficient algorithm is necessary to solve larger instances of a problem.
  2. In Lab 1 you built two reporters that output the position of an element in a list. The reporter position of __ in unsorted list works for any list as a linear search, checking element-by-element until it finds a match (or gets to the end and reports "Not In List"). The reporter position of __ in sorted list works on sorted lists as a binary search algorithm. So, both will work on sorted lists. Compare them for some long sorted lists and make a table of your findings. You may have to use very large lists, say 1000 or 2000 items, to get meaningful results.
    Is the other algorithm ever faster?
    Which algorithm is faster?
  3. Write Out Your Thoughts Throughout this course, you've programmed many algorithms. Try timing them! Test your favorite algorithms, such as:
    • Creating a list of numbers
    • Testing a list to see if the elements are distinct
    • Adding 1 to a number
    • Computing the factorial of a number
    • Number guessing games

    Time your algorithms for varying size inputs and describe the different behaviors you see. Again, use large inputs for meaningful results.

  4. "U5L3-timer"save your work as U5L3-timer