CSC 151.01, Class 33: Project work day 1

Overview

• Preliminaries
  • Notes and news
  • Upcoming work
  • Extra credit
  • Questions
• Making code more efficient
• Quiz
• Work time

Preliminaries

News / Etc.

• Sit with your project group.
• We will miss the crane.
  • However, last Friday’s S&B suggests that worries about crane permissions made the College less willing to explore certain important but controversial changes, so perhaps not.

Upcoming work

• No writeup for today’s class.
• Reading for Monday: Searching
• Flash Cards due next Wednesday at 9pm.
  • Optional.
  • Grade is percent of eight flashcard assignments you complete (capped at 100%).
• Project Proposal due Monday at 10:30 p.m.
  • Due early to give me time to react.

Extra credit (Academic/Artistic)

• Disability panel, Friday, 7pm, JRC 101.
• HackGC (or any of the HackGC talks). https://hackgc.github.io
• Rap concert tonight. (Opening act is a Grinnell alum.)
• The Cypher Paradigm: Closing Cypher, Tuesday, 8:30 p.m., ARH 120.
• Squire Lecture in Physics, Tuesday at 11:45: STEM Eqwuality and Inclusion, a Female Astronomer’s View. Noyce 1023.
• CS Table Tuesday: Subject TBD.
• Diversity in Filmmaking, Monday, 4:15 p.m., Bucksbaum 152

Extra credit (Peer)

• Play presentation Friday at 4pm in the Wall Theatre (154).
• ISO Cultural Evening Saturday night at 7pm in Harris
• Escape Room, 7-9pm Monday, Gates
• Thursday, April 26th, Noyce 2022: Mellon Mays Project introductions, 4:15 to 6:30 p.m.
• Field Day.
• Making a Killing, Friday 7pm, Harris.

Extra credit (Recurring peer)

• Listen to KDIC Wednesdays at 6pm - Witty banter with other personalities and/or co-host. Also Indian, Arabic, and Farsi music.
  (Up to two units of extra credit.)
• Listen to KIDC Thursday at 7pm - Classic Rock. (60’s and 70’s)
• Peer editing with SS. Talk to SS about the details. Make your English Lit more literate.

Extra credit (Misc)

• Any Sexual Assault Awareness Month event.
• Host one or more prospective students. (I think this is the last visit weekend.)

Other good things

• Free HIV testing at SHACS.
• Dick Young Meet tomorrow.
• Water Polo Saturday and Sunday.
• Ideation, a play, 7:30 p.m. in Loft Theatre tonight and tomorrow night. and Sunday at 2.

Questions

Making code more efficient

We’ll consider two examples.

Example one: Finding the smallest value in a list

What are potential expenses in the following code. How would you reduce those expenses without completely rewriting the code?

(define list-smallest
  (lambda (lst)
    (counter-increment! lsc)
    (if (= (length lst) 1)
        (car lst)
        (if (< (car lst)
               (list-smallest (cdr lst)))
            (car lst)
            (list-smallest (cdr lst))))))

Warning bells!

• length is expensive. I shouldn’t call it on every recursive call.
• I also worry about identical expressions: three calls to (car lst) and two to (list-smallest (cdr lst)).
  • I worry less about (car lst) because car is fast.
  • I worry more about (list-smallest (cdr lst)) because I know that those are expensive.

My worries were appropriate.

• (list-smallest (reverse (iota 4))) => 15 calls
• (list-smallest (reverse (iota 8))) => 255 calls
• (list-smallest (reverse (iota 16))) => 65535 calls
• Pattern: Approximately (- (expt 2 (length lst)) 1) calls
• We gave up after about five minutes on (list-smallest (reverse (iota 1000))). At that point, there had been 4123710043 (4,123,710,043 for those who like commas) calls.

Solving the problems.

• Use (null? (cdr lst)) to check for a one-element list.
• Use let to avoid repeated computations.

(define list-smallest
  (lambda (lst)
    (counter-increment! lsc)
    (if (null? (cdr lst))
        (car lst)
        (let ([smallest-of-rest (list-smallest (cdr lst))])
        (if (< (car lst)
               smallest-of-rest)
            (car lst)
            smallest-of-rest)))))

What happens?

• For (list-smallest (reverse (iota 1000))), it was nearly instantaneous and was 1000 calls. Yay!

Computing a sublist.

Once again, what’s wrong with this code?

;;; Purpose:
;;;   take the sublist starting at position start and ending right
;;;   before position finish.
(define sublist
  (lambda (lst start finish)
    (let kernel ([start start]
                 [finish finish])
      (cond
        [(>= start finish)
         null]
        [(>= start (length lst))
         null]
        [else
         (cons (list-ref lst start)
               (kernel (+ 1 start) finish))]))))

Agh! There’s another call to length. That makes me nervous. I’ll move it outside the kernel.

(define sublist
  (lambda (lst start finish)
    (let [(len (length lst))]
      (let kernel ([start start]
                   [finish finish])
        (cond
          [(>= start finish)
           null]
          [(>= start len)
           null]
          [else
           (cons (list-ref lst start)
                 (kernel (+ 1 start) finish))]))))

Oh. There’s still a call to list-ref. That makes me nervous. list-ref is expensive. Calling it each time will likely add up. (start + start+1

• start+2 + … is a large sum.)

How do we do without the call to list-ref? We should probably follow our normal pattern for list recursion, which involves adding the list as a parameter. Here’s not-yet-better code.

(define sublist
  (lambda (lst start finish)
    (let [(len (length lst))]
      (let kernel ([remaining lst]
                   [start start]
                   [finish finish])
        (cond
          [(>= start finish)
           null]
          [(>= start len)
           null]
          [else
           (cons (list-ref lst start)
                 (kernel (+ 1 start) finish))]))))

Quiz

Work time