Analyzing Procedures

At this point in your career, you know the basic tools to build algorithms, including conditionals, recursion, variables, and subroutines (procedures). You've also found that you can often write several different procedures that all solve the same problem and even produce the same results. How do you then decide which one to use? There are many criteria we use. One important one is readability - can we easily understand the way the algorithm works? A more readable algorithm is also easier to correct if we ever notice an error or to modify if we want to expand its capabilities.

However, most programmers care as much about efficiency - how many computing resources does the algorithm use? (Pointy-haired bosses care even more about such things.) Resources include memory and processing time. Most analyses of efficiency focus on running time, the amount of time the program takes to run, which, in turn depends on both how many steps the procedure executes and how long each step takes. Since almost every step in Scheme involves a procedure call, to get a sense of the approximate running time of Scheme algorithms, we can usually count procedure calls.

In this reading and the corresponding lab, we will consider some techniques for figuring out how many procedure calls are done.

As we explore analysis, we'll start with a few basic examples. First, consider two versions of the irgb-brightest procedure, which you should recall from earlier in the semester.

;;; Procedure:
;;;   irgb-brightest
;;; Parameters:
;;;   colors, a list of integer-encoded RGB colors
;;; Purpose:
;;;   Find the brightest color in the list.
;;; Produces:
;;;   brightest, an integer-encoded RGB color.
;;; Preconditions:
;;;   colors contains at least one element.
;;;   irgb-brightness is defined
;;; Postconditions:
;;;   For any color in colors,
;;;    (irgb-brightness color) <= (irgb-brightness brightest)
;;;   brightest is an element of colors.
(define irgb-brightest-1
  (lambda (colors)
    (cond
      [(null? (cdr colors))
       (car colors)]
      [(irgb-brighter? (car colors) (irgb-brightest-1 (cdr colors)))
       (car colors)]
      [else
       (irgb-brightest-1 (cdr colors))])))
(define irgb-brightest-2
  (lambda (colors)
    (if (null? (cdr colors))
        (car colors)
        (irgb-brighter (car colors)
                       (irgb-brightest-2 (cdr colors))))))

You can find the helpers for this procedure in an appendix.

The two versions are fairly similar. Does it really matter which we use? We'll see in a bit.

As a second example, consider how we might write the famous reverse procedure ourselves, rather than using the built-in version. In this example, we'll use two very different versions.

;;; Procedure:
;;;   list-reverse
;;; Parameters:
;;;   lst, a list of size n
;;; Purpose:
;;;   Reverse lst.
;;; Produces:
;;;   reversed, a list
;;; Preconditions:
;;;   lst is a list. [Unverified]
;;; Postconditions:
;;;   (length reversed) = (length lst)
;;;   For all valid indices i,
;;;     (list-ref lst i) equals (list-ref reversed (- n i 1))
(define list-reverse-1
  (lambda  (lst)
    (if (null? lst)
        null
        (list-append (list-reverse-1 (cdr lst)) (list (car lst))))))
(define list-reverse-2
  (lambda (lst)
    (let kernel ([reversed null]
                 [remaining lst])
      (if (null? remaining)
          reversed
          (kernel (cons (car remaining) reversed)
                  (cdr remaining))))))

You'll note that we've used list-append rather than append. Why? Because we know that the append procedure is recursive, so we want to make sure that we can count the calls that happen there, too. We've used the standard implementation strategy for append in defining list-append.

;;; Procedure:
;;;   list-append
;;; Parameters:
;;;   front, a list of size n
;;;   back, a list of size m
;;; Purpose:
;;;   Put front and back together into a single list.
;;; Produces:
;;;   appended, a list of size n+m.
;;; Preconditions:
;;;   front is a list [Unverified]
;;;   back is a list [Unverified]
;;; Postconditions:
;;;   For all i, 0 <= i < n,
;;;    (list-ref appended i) is (list-ref front i)
;;;   For all i, <= i < n+m
;;;;   (list-ref appended i) is (list-ref back (- i n))
(define list-append
  (lambda (front back)
    (if (null? front)
        back
        (cons (car front) (list-append (cdr front) back)))))

How do we figure out how many steps these procedures take? One obvious way is to add a bit of code to output something for each procedure call. While you may not know the details of output yet, all you need to know right now is that write prints its parameter, and newline prints a carriage return. To annotate the procedures for output, we simply add appropriate calls. For example, here are the first few lines of the annotated versions of rgb-brightest-1 and rgb-brightest-2.

(define irgb-brightest-1
  (lambda (colors)
    (write (list 'irgb-brightest-1 (map irgb->string colors))) (newline)
    (cond
      [(null? (cdr colors))
       (car colors)]
      [(rgb-brighter? (car colors) (irgb-brightest-1 (cdr colors)))
       (car colors)]
      [else
       (irgb-brightest-1 (cdr colors))])))

(define irgb-brightest-2
  (lambda (colors)
    (write (list 'irgb-brightest-2 (map irgb->string colors))) (newline)
    (if (null? (cdr colors))
        (car colors)
        (irgb-brighter (car colors)
                      (irgb-brightest-2 (cdr colors))))))

So, what happens when we call the two procedures on a simple list of colors?

> (define grey (lambda (n) (rgb-new n n n)))
> (define light-to-dark (map grey (list 255 192 128 64 0)))
> (irgb-brightest-1 light-to-dark)
(irgb-brightest-1 (255/255/255 192/192/192 128/128/128 64/64/64 0/0/0))
(irgb-brightest-1 (192/192/192 128/128/128 64/64/64 0/0/0))
(irgb-brightest-1 (128/128/128 64/64/64 0/0/0))
(irgb-brightest-1 (64/64/64 0/0/0))
(irgb-brightest-1 (0/0/0))
16777215
> (irgb-brightest-2 light-to-dark)
(irgb-brightest-2 (255/255/255 192/192/192 128/128/128 64/64/64 0/0/0))
(irgb-brightest-2 (192/192/192 128/128/128 64/64/64 0/0/0))
(irgb-brightest-2 (128/128/128 64/64/64 0/0/0))
(irgb-brightest-2 (64/64/64 0/0/0))
(irgb-brightest-2 (0/0/0))
16777215

So far, so good. Each has about five calls for a list of length five. Let's try a slightly different list.

> (define dark-to-light (reverse light-to-dark))
> (irgb-brightest-1 dark-to-light)
(irgb-brightest-1 (0/0/0 64/64/64 128/128/128 192/192/192 255/255/255))
(irgb-brightest-1 (64/64/64 128/128/128 192/192/192 255/255/255))
(irgb-brightest-1 (128/128/128 192/192/192 255/255/255))
(irgb-brightest-1 (192/192/192 255/255/255))
(irgb-brightest-1 (255/255/255))
(irgb-brightest-1 (255/255/255))
(irgb-brightest-1 (192/192/192 255/255/255))
(irgb-brightest-1 (255/255/255))
(irgb-brightest-1 (255/255/255))
(irgb-brightest-1 (128/128/128 192/192/192 255/255/255))
(irgb-brightest-1 (192/192/192 255/255/255))
(irgb-brightest-1 (255/255/255))
(irgb-brightest-1 (255/255/255))
(irgb-brightest-1 (192/192/192 255/255/255))
(irgb-brightest-1 (255/255/255))
(irgb-brightest-1 (255/255/255))
(irgb-brightest-1 (64/64/64 128/128/128 192/192/192 255/255/255))
(irgb-brightest-1 (128/128/128 192/192/192 255/255/255))
(irgb-brightest-1 (192/192/192 255/255/255))
(irgb-brightest-1 (255/255/255))
(irgb-brightest-1 (255/255/255))
(irgb-brightest-1 (192/192/192 255/255/255))
(irgb-brightest-1 (255/255/255))
(irgb-brightest-1 (255/255/255))
(irgb-brightest-1 (128/128/128 192/192/192 255/255/255))
(irgb-brightest-1 (192/192/192 255/255/255))
(irgb-brightest-1 (255/255/255))
(irgb-brightest-1 (255/255/255))
(irgb-brightest-1 (192/192/192 255/255/255))
(irgb-brightest-1 (255/255/255))
(irgb-brightest-1 (255/255/255))
16777215

Wow! That's a lot of lines to count, 31 if we've counted correctly. That seems like a few more than one might expect. That may be a problem. So, how many does the other version take?

> (irgb-brightest-2 dark-to-light)
(irgb-brightest-2 (0/0/0 64/64/64 128/128/128 192/192/192 255/255/255))
(irgb-brightest-2 (64/64/64 128/128/128 192/192/192 255/255/255))
(irgb-brightest-2 (128/128/128 192/192/192 255/255/255))
(irgb-brightest-2 (192/192/192 255/255/255))
(irgb-brightest-2 (255/255/255))
16777215

Still five calls for a list of length five. Clearly, the second one is better on this input. Why and how much? That's an issue for a bit later.

In case you haven't noticed, we've now tried two special cases, one in which the list is organized brightest to darkest and one in which the list is organized darkest to brightest. In the first case, the two versions are equivalent in terms of the number of recursive calls. In the second case, the second implementation is significantly faster. Clearly, the cases you test for efficiency matter a lot. We should certainly try some others.

Now, let's try the other example, reversing lists. We'll start by reversing a list of length five.

> (reverse-1 (list 1 2 3 4 5))
(reverse-1 (1 2 3 4 5))
(reverse-1 (2 3 4 5))
(reverse-1 (3 4 5))
(reverse-1 (4 5))
(reverse-1 (5))
(reverse-1 ())
(5 4 3 2 1)
> (reverse-2 (list 1 2 3 4 5))
(reverse-2 (1 2 3 4 5))
(reverse-2-kernel (1 2 3 4 5) ())
(reverse-2-kernel (2 3 4 5) (1))
(reverse-2-kernel (3 4 5) (2 1))
(reverse-2-kernel (4 5) (3 2 1))
(reverse-2-kernel (5) (4 3 2 1))
(reverse-2-kernel () (5 4 3 2 1))
(5 4 3 2 1)

So far, so good. The two seem about equivalent. But what about the other procedures that each calls? The kernel of reverse-2 calls cdr, cons, and car once for each recursive call. Hence, there are probably five times as many procedure calls as we just counted. On the other hand, reverse-1 calls list-append and list. The list procedure is not recursive, so we don't need to worry about it. But what about list-append? It is recursive, so let's add an output annotation to that procedure, too. Now, what happens?

> (reverse-1 (list 1 2 3 4 5))
(reverse-1 (1 2 3 4 5))
(reverse-1 (2 3 4 5))
(reverse-1 (3 4 5))
(reverse-1 (4 5))
(reverse-1 (5))
(reverse-1 ())
(list-append () (5))
(list-append (5) (4))
(list-append () (4))
(list-append (5 4) (3))
(list-append (4) (3))
(list-append () (3))
(list-append (5 4 3) (2))
(list-append (4 3) (2))
(list-append (3) (2))
(list-append () (2))
(list-append (5 4 3 2) (1))
(list-append (4 3 2) (1))
(list-append (3 2) (1))
(list-append (2) (1))
(list-append () (1))
(5 4 3 2 1)

Hmmm, that's a few calls to list-append. Not the 31 we saw for the brightest element in a list, but still a lot. Let's see ... fifteen, if we count correctly. Now, let's see what happens when we add one element to the list.

> (reverse-1 (list 1 2 3 4 5 6))
(reverse-1 (1 2 3 4 5 6))
(reverse-1 (2 3 4 5 6))
(reverse-1 (3 4 5 6))
(reverse-1 (4 5 6))
(reverse-1 (5 6))
(reverse-1 (6))
(reverse-1 ())
(list-append () (6))
(list-append (6) (5))
(list-append () (5))
(list-append (6 5) (4))
(list-append (5) (4))
(list-append () (4))
(list-append (6 5 4) (3))
(list-append (5 4) (3))
(list-append (4) (3))
(list-append () (3))
(list-append (6 5 4 3) (2))
(list-append (5 4 3) (2))
(list-append (4 3) (2))
(list-append (3) (2))
(list-append () (2))
(list-append (6 5 4 3 2) (1))
(list-append (5 4 3 2) (1))
(list-append (4 3 2) (1))
(list-append (3 2) (1))
(list-append (2) (1))
(list-append () (1))
(6 5 4 3 2 1)
> (reverse-2 (list 1 2 3 4 5 6))
(reverse-2 (1 2 3 4 5 6))(kernel (1 2 3 4 5 6) ())
(kernel (2 3 4 5 6) (1))
(kernel (3 4 5 6) (2 1))
(kernel (4 5 6) (3 2 1))
(kernel (5 6) (4 3 2 1))
(kernel (6) (5 4 3 2 1))
(kernel () (6 5 4 3 2 1))
(6 5 4 3 2 1)

Hmmm ... we added one element to the list, and we added six calls to list-append (we're now up to 21). In the case of reverse-2, we seem to have added only one call.

What if there are ten elements? You probably don't want to count that high. However, we're pretty sure the we'll end up with 55 total calls to list-append, and only ten recursive calls to the kernel.

We've seen a few problems in the previous strategy for analyzing the running time of procedures. First, it's a bit of a pain to add the output annotations to our code. Second, it's even more of a pain to count the number of lines those annotations produce. Finally, there are some procedure calls that we didn't count. So, what should we do? We want to transition from manual to automatic counting.

Once upon a time, some Grinnell faculty built a simple library that helps make the transition to automatic counting. Unfortunately, as Scheme and Racket have changed, the library no longer works. And so we will update our code just a bit to do the counting, but at least the counting will be automatic.

What do we do? For each procedure we want to count, we create a vector. Why a vector? Because we know how to change the elements in vectors, and we are going to want to have a count that we can change. For convenience, we will also include the name of the thing we are counting.

;;; Procedure:
;;;   counter-new
;;; Parameters:
;;;   name, a string
;;; Purpose:
;;;   Create a counter associated with the given name.
;;; Produces:
;;;   counter, a counter
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   counter can be used as a parameter to the various counter
;;;   procedures.
;;; Process:
;;;   Counters are two element vectors.  Element 0 is the name, and
;;;   should not change.  Element 1 is the count, and should change.
(define counter-new
  (lambda (name)
    (vector name 0)))

Now, let's create some procedures that we can use with that counter. First, we want to be able to increment the counter (that is, to count one more procedure call).

;;; Procedure:
;;;   counter-count!
;;; Parameters:
;;;   counter, a counter 
;;; Purpose:
;;;   count the counter
;;; Produces:
;;;   counter, the same counter, now mutated
;;; Preconditions:
;;;   counter was created by counter-new (or something similar) and
;;;   has only been modified by the counter procedures.
;;; Postconditions:
;;;   (counter-get counter) gives a number one higher than it 
;;;   did before.
(define counter-count!
  (lambda (counter)
    (vector-set! counter 1 (+ 1 (vector-ref counter 1)))
    counter))

And, of course, we want to be able to get the value of the counter.

;;; Procedure:
;;;   counter-get
;;; Parameters:
;;;   counter, a counter
;;; Purpose:
;;;   Get the number of times that counter-count! has been called
;;;   on this counter.
;;; Produces:
;;;   count, a non-negative integer
;;; Preconditions:
;;;   counter was created by counter-new and has only been modified
;;;   by the counter procedures.
;;; Postconditions:
;;;   count is the number of calls to counter-new on this counter since
;;;   the last call to counter-reset! on this counter, or since the
;;;   counter was created, if there have been no calls to counter-reset!
(define counter-get
  (lambda (counter)
    (vector-ref counter 1)))

As that documentation suggests, we may, on occasion, want to reset the counter.

;;; Procedure:
;;;   counter-reset!
;;; Parameters:
;;;   counter, a counter 
;;; Purpose:
;;;   reset the counter
;;; Produces:
;;;   counter, the same counter, now set to 0
;;; Preconditions:
;;;   counter was created by counter-new (or something similar) and
;;;   has only been modified by the other counter procedures.
;;; Postconditions:
;;;   (counter-get counter) gives 0.
(define counter-reset!
  (lambda (counter)
    (vector-set! counter 1 0)
    counter))

Finally, it may be useful to print out the value of the counter.

;;; Procedure:
;;;   counter-print!
;;; Parameters:
;;;   counter, a counter
;;; Purpose:
;;;   Print out the information associated with the counter.
;;; Produces:
;;;   counter, the same counter
;;; Preconditions:
;;;   counter was created by counter-new and has only been modified
;;;   by the various counter procedures.
;;; Postconditions:
;;;   counter is unchanged.
;;;   The output port now contains information on counter.
;;; Ponderings:
;;;   Why does counter-print! have a bang, given that it doesn't mutate
;;;   it's parameter?  Because it mutates the broader environment - we
;;;   call counter-print! not to compute a value, but to print something.
(define counter-print!
  (lambda (counter)
    (display (vector-ref counter 0))
    (display ": ")
    (display (vector-ref counter 1))
    (newline)))

Now, we can try the second analysis of the rgb-brightest procedures and even do a bit less manual counting.

First, we create counters.

(define rbg-brightest-1-counter (counter-new "rgb-brightest-1"))
(define rbg-brightest-2-counter (counter-new "rgb-brightest-2"))
(define counters (list rgb-brightest-1-counter rgb-brightest-2-counter))

Next, we update the code to rgb-brightest-1 and rgb-brightest-2.

(define rgb-brightest-1
  (lambda (colors)
    (counter-count! rgb-brightest-1-counter)
    (cond
      [(null? (cdr colors))
       (car colors)]
      [(rgb-brighter? (car colors) (rgb-brightest-1 (cdr colors)))
       (car colors)]
      [else
       (rgb-brightest-1 (cdr colors))])))

(define rgb-brightest-2
  (lambda (colors)
    (counter-count! rgb-brightest-2-counter)
    (if (null? (cdr colors))
        (car colors)
        (rgb-brighter (car colors)
                      (rgb-brightest-2 (cdr colors))))))

Finally, we can do some analysis.

> (for-each counter-reset! rgb-brightest-counters)
> (irgb-brightest-1 light-to-dark)
16777215
> (for-each counter-print! rgb-brightest-counters)
rgb-brightest-1: 5
rgb-brightest-2: 0
> (irgb-brightest-2 light-to-dark)
16777215
> (for-each counter-print! rgb-brightest-counters)
rgb-brightest-1: 5
rgb-brightest-2: 5
> (for-each counter-reset! rgb-brightest-counters)
> (for-each counter-print! rgb-brightest-counters)
rgb-brightest-1: 0
rgb-brightest-2: 0
> (irgb-brightest-1 dark-to-light)
16777215
> (irgb-brightest-2 dark-to-light)
16777215
> (for-each counter-print! rgb-brightest-counters)
rgb-brightest-1: 31
rgb-brightest-2: 5

What if we try a slightly bigger list? We didn't really want to do so when we were counting by hand, but now the computer can count for us.

> (define lots-of-greys (map grey (list 0 16 32 48 64 96 112 128 144 160 176 192 208 224 240 255)))
> (length lots-of-greys)
16
> (for-each counter-reset! rgb-brightest-counters)
> (irgb-brightest-1 lots-of-greys)
16777215
> (irgb-brightest-2 lots-of-greys)
16777215
> (for-each counter-print! rgb-brightest-counters)
rgb-brightest-1: 65535
rgb-brightest-2: 16

We really didn't want to count more than 64,000 calls by hand.

Now that we've done some preliminary exploration of these procedures, which one would you prefer to use?

You may be waiting for us to analyze the two forms of reverse, but we'll leave that as a task for the lab.

You now have a variety of ways to count steps. But what should you do with those results in comparing algorithms? The strategy most computer scientists use is to look for patterns that describe the relationship between the size of the input and the number of procedure calls. We find it useful to look at what happens when you add one to the input size (e.g., go from a list of length 4 to a list of length 5) or when you double the input size (e.g., go from a list of length 4 to a list of length 8, or go from the number 8 to the number 16).

The most efficient algorithms generally use a number of procedure calls that does not depend on the size of the input. For example, car always takes one step, whether the list of length 1, 2, 4, or even 1024. Computer scientists refer to those as constant time algorithms.

At times, we'll find algorithms that add a constant number of steps when you double the input size (we haven't seen any of those so far). Those are also very good. (Computer scientists and mathematicians say that these algorithms are logarithmic in the size of the input.)

However, for most problems, the best we'll be able to do is write algorithms that take twice as many steps when we double the size of the input. For example, in processing a list of length n, we probably have to visit every element of the list. In fact, we'll probably do a few steps for each element. If we double the length of the list, we double the number of steps. Most of the list problems you face in this class should have solutions that have this form. For these algorithms, we say that the running time is linear in the size of the input.

However, there are times that the running time grows much more quickly. For example, you may notice that when you double the input, the number of steps seems to go up by about a factor of four. Such algorithms are sometimes necessary, but get very slow as input size increases. When the running time grows by the square of the growth in input size, we say that algorithms are quadratic.

But there are even worse cases. At times, you'll find that when you double the input size, the number of steps goes up much more than a factor of four. (For example, that happens in the first version of rgb-brightest-1.) If you find your code exhibiting that behavior, it's probably time to write a new algorithm.

Note: While we generally don't like to use algorithms that exhibit worse behavior than quadrupling steps for doubled input, there are cases in which these slow algorithms are the best that any computer scientist has developed. There are even some problems for which we have slow algorithms but theorize that there cannot be a fast algorithm. To make life even more confusing, there are some problems for which it has been proven that no algorithm can exist. If you continue your study of computer science, you willl have the opportunity to explore these puzzling but powerful ideas.

We started the reading by considering pairs of algorithms for the same problem, and found that one of each pair was much slower than the other. Why are the slower versions of the two algorithms above so slow? In the case of rgb-brightest-1, there is a case in which one call spans two identical recursive calls. That doubling gets painful fairly quickly. From 1 to 3 to 7 to 15 to 31 to 63 to ....

If you notice that you are doing multiple identical recursive calls, see if you can apply a helper to the recursive call, as we did in rgb-brightest-2. Rewriting your procedure using the primary tail recursion strategy (that is, accumulating a result as you go) may also help.

In the case of reverse-1, the difficulty is only obvious when we include list-append. And what's the problem? The problem is that list-append is not a constant-time algorithm, but one that needs to visit every element in the first list. Since reverse keeps calling list-append with larger and larger lists, we spend a lot of time appending.

At the beginning of this reading, we considered two techniques for computing the brightest element of a list. Each of those techniques relied on some additional procedures, such as rgb-brighter? and rgb-brighter. Those procedures, and other related procedures, may be found here.

;;; Procedure:
;;;   rgb-brightness
;;; Parameters:
;;;   color, an RGB color
;;; Purpose:
;;;   Computes the brightness of color on a 0 (dark) to 100 (light) scale.
;;; Produces:
;;;   b, an integer
;;; Preconditions:
;;;   color is a valid RGB color.  That is, each component is between
;;;     0 and 255, inclusive.
;;; Postconditions:
;;;   If color1 is likely to be perceived as lighter than color2,
;;;     then (brightness color1) > (brightness color2).
;;;   0 <= b <= 100
(define rgb-brightness
  (lambda (color)
    (round (* 100 (/ (+ (* 0.30 (rgb-red color))
                        (* 0.59 (rgb-green color))
                        (* 0.11 (rgb-blue color)))
                      255)))))

;;; Procedure:
;;;   rgb-brighter?
;;; Parameters:
;;;   color1, a color
;;;   color2, a color
;;; Purpose:
;;;   Determine if color1 is strictly brighter than color 2.
;;; Produces:
;;;   brighter?, a Boolean
;;; Preconditions:
;;;   [No additional preconditions.]
;;; Postconditions:
;;;   If (rgb-brightness color1) > (rgb-brightness color2)
;;;     then brighter is true (#t)
;;;   Otherwise
;;;     brighter is false (#f)
(define rgb-brighter?
  (lambda (color1 color2)
    (> (rgb-brightness color1) (rgb-brightness color2))))

;;; Procedure:
;;;   rgb-brighter
;;; Parameters:
;;;   color1, an RGB color.
;;;   color2, an RGB color.
;;; Purpose:
;;;   Find the brighter of color1 and color2.
;;; Produces:
;;;   brighter, an RGB color.
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   brighter is either color1 or color2
;;;   (rgb-brightness brighter) >= (rgb-brightness color1)
;;;   (rgb-brightness brighter) >= (rgb-brightness color2)
(define rgb-brighter
  (lambda (color1 color2)
    (if (>= (rgb-brightness color1) (rgb-brightness color2))
        color1
        color2)))