Timing Reporters

On this page, you will use an algorithm timer to help you compare the efficiency of algorithms.

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.
  3. Open the "U5L3-ReporterTimer" project that you saved on the previous page.
  4. Download this library: U5L3functiontimer.xml, and drag the file into your Snap! application to import it.
Brian says time function should really be time expression. --MF, 2/20/18

At the bottom of the Variables palette, there will now be a block called time function. It takes any reporter (with its inputs filled in), computes the result, and reports how long it took to do the computation (in milliseconds).

You can replace the list from block with any reporter. You can edit time function to see how it works.
time function (list from (1) through (1000)) reporting 27

In this example, it took 27 milliseconds to compute the list of integers from 1 to 1000. (The number you see reported will depend on how fast your computer is and what other programs are running on it.)

Here's how time function works:
time function (function): (script variables (start time), set (start time) to (current(time in milliseconds)), ignore (call(function)), report(current(time in milliseconds) - start time))

  1. It creates a variable start time and sets it to the current time.
  2. It calls the reporter that you're trying to time, but it ignores the result.
  3. When the reporter finishes, it gets the current time and subtracts the start time from it.

  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:

    A linear search means searching a list from one item to the next.

    A binary search means dividing a sorted list into two pieces at each step.

    • The reporter position of () in unsorted list works for any list by checking element-by-element until it finds a match. This is called a linear search because the program searches from the beginning of the list to the match in a straight line.
    • The reporter position of () in sorted list works on sorted lists by repeatedly dividing the list into two equal-sized parts and using the middle value to decide which half can contain the match. This is called a binary search because binary means "two" and the algorithm divides the list into two parts.
    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. Which algorithm is faster?
    Is the other algorithm ever faster?
  3. Throughout this course, you've programmed many algorithms. Try timing them. Here are some examples:

    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