EK: 4.2.4D, 4.2.4F

Timing Reporters

The title of this page has two meanings: You will build a "timing reporter" … that times reporters.
'reset timer' and 'timer' blocks in palette

Snap! allows us to report how long a program takes to finish. In the "Sensing" palette, look for the reset timer command and a reporter called timer.

BK: Is this a reporter, or a variable? It feels like a variable. I guess a variable block is technically a reporter.
  1. Show the timer on the stage (click the checkbox), and you'll see a timer ticking away in the top left corner of the stage. It’s been ticking ever since you opened Snap!:
    timer watcher showing 310.2
  2. Click reset timer and see what happens.

Ways to Think About It

BH: I don't understand why TIMER is introduced and then dropped in favor of CURRENT. Students won't understand either. If there's a reason (e.g. we'll come back to TIMER later) then explain explicitly.

current (time in milliseconds) reporting 1454091401280 The timer keeps chugging along, but the current reporter is another useful feature of Snap!. If you set its input to time in milliseconds, it reports the current time. This can be used to time how long a reporter takes to output. Here’s an algorithm:

BK: The variable here should be "start time", not "time". Did not change since it might affect the XML pages.
You can replace the list between block for any reporter—this may be a new idea. Open time function to see how it works.
The answer will be in milliseconds. The block time function implements this algorithm. 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.

  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 305
The efficiency of an algorithm can make a huge difference. Sometimes, an efficient algorithm is necessary to solve larger instances of a problem.
  1. 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 NIL). 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.
    Is the other algorithm ever faster?
    Which algorithm is faster?
  2. 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.

 
  1. If you time the same function with the same input, you often get a different result.
    1. Why might that happen?
    2. Build a block average time that allows you to input a reporter and a number of trials. Its output is the average of the time it takes the reporter to compute its output for the the specified number of trials. Here’s a picture of how it works for Alphie’s summing reporter, adding the numbers from 1 to 500, performed 10 times:
      average time (alphie way (500)) (10) reporting 74.1
    3. Even average time reports different times on different calls. What could make it more consistent?