Learning objectives

The same real-world information can be stored in many different ways. How we organize our data affects whether specific functions are easy or hard to write, how fast computations run, and how easy it is to keep our data up to date. In this lab, you'll design two different data organizations for a problem, think about what is hard or easy to do on each design, and start to think about how fast programs can run.

This lab will:

Setup

Part 1Travel

An airline wants to record its flights and the tickets sold on them. A flight has a flight number, an airline code, and a departure hour. A ticket has a ticket number, a passenger name, and a passport id, and belongs to exactly one flight.

Step 1Define two organizations

Task 1

With your partner, try to come up with two different ways to organize the flight and ticket info. Should you use tables or datatypes? One table or two? Are lists useful anywhere? Document your ideas in your worksheet.

Check out our two versions. If what you had was significantly different and the differences raise questions, discuss them with a TA.

our versions
  • Travel A: one table of flights. Each flight carries the list of its tickets, with each ticket a datatype with its own fields.
  • Travel B: two tables, one of flights and one of tickets. Each ticket records the flight it belongs to.

You'll work with our two organizations for the rest of the lab (because they are designed to illustrate the rest of the learning objectives in this lab).

Task 2

Create datatypes as needed for each of our two versions.

Design an example dataset, and create it in Pyret in each of our two versions/organizations. Your example dataset should have at least three flights and at least seven tickets, with at least one flight that has no tickets, and at least one passenger who appears on two flights.

Checkpoint

Show a TA your definitions and examples for both organizations.

Step 2Considering the tradeoffs

Task 3

In your worksheet, indicate which organization you think you prefer and why.

Task 4

In practice, we choose data organizations based on the specific tasks that we plan to do with the data. Here are four concrete scenarios. For each one, indicate whether you prefer A, B, or either (A and B name our two solutions). Write a couple of sentences about why. Don't write code.

  1. A flight is under-booked if it has fewer than 50 tickets. Find the flight numbers of all under-booked flights.
  2. Given a ticket number, find the airline of its flight.
  3. Determine whether two tickets have the same passenger name but different passport ids.
  4. Add a seat number to every ticket.

Part 2Trying These Functions on Large Datasets

Your example data has three flights and seven tickets. A real airline has thousands of flights and millions of tickets. An organization that works well on a small example may not hold up at that size. In this part, you'll find out how well your functions do as the datasets get larger. In lecture, we will give you the vocabulary and tools for explaining what you see.

Step 1Develop the functions

Task 5

Write these two functions for both organizations, using your examples from Task 2 to test them:

  1. Who is on a given flight? The function takes the data and a flight number, and returns the list of passenger names.
  2. Which flights are under-booked? The function takes the data and a number n, and returns the flight numbers of all flights with fewer than n tickets.

Task 6

We are going to run these functions on datasets with the number of flights held fixed at 100 while the number of tickets grows. In your worksheet, write down your prediction of whether these functions will be faster on organization A, organization B, or neither as the number of tickets grows.

Step 2Have Claude generate larger datasets

We're going to leverage Claude to help us generate the large datasets. The datasets will be generated as pairs of CSV files, one of flights and one of tickets. The dropdown below contains functions that read each kind of csv into a table. Put your datatype definitions and your example data in one file, and copy this into it, after your use context line:

The CSV readers
include csv
include data-source

fun read-flights(file):
  load-table: flight-num, airline, hour
    source: csv-table-file(file, default-options)
    sanitize flight-num using num-sanitizer
    sanitize airline using string-sanitizer
    sanitize hour using num-sanitizer
  end
end

fun read-tickets(file):
  load-table: ticket-num, flight-num, passenger, passport-id
    source: csv-table-file(file, default-options)
    sanitize ticket-num using num-sanitizer
    sanitize flight-num using num-sanitizer
    sanitize passenger using string-sanitizer
    sanitize passport-id using num-sanitizer
  end
end

Task 7

Start a fresh Claude session in your lab folder and give it this prompt, replacing travel.arr (at the top of the prompt) with the name of your file:

travel.arr has my Travel A and Travel B datatypes, and the functions
read-flights and read-tickets, which read a flights CSV and a tickets
CSV into tables.  Travel A consists of one table of flights. Each
flight carries the list of its tickets, with each ticket a datatype
with its own fields.  Travel B consists of two tables, one of flights
and one of tickets. Each ticket records the flight it belongs to.

Please:

1. Create CSV files, with these exact names and header rows:
   - fixed-flights.csv: 100 flights, columns flight-num,airline,hour
   - fixed-tickets-N.csv for N = 100, 200, 400, 800, 1600: columns
     ticket-num,flight-num,passenger,passport-id. Spread the tickets
     evenly over the 100 flights.
   - grow-flights-F.csv and grow-tickets-F.csv for F = 25, 50, 100, 200,
     400, where grow-flights-F.csv has F flights and grow-tickets-F.csv
     has 20 tickets per flight.
   Flights are numbered 1 to F with no gaps. Every ticket names a flight
   that exists. Don't choose anything randomly; follow a simple pattern, so
   that you can predict how many tickets each flight has.

2. Add the functions read-a(flights-file, tickets-file) and
   read-b(flights-file, tickets-file) to the arr file. Each reads a pair of CSV files into
   that organization, using read-flights and read-tickets.

Claude will add two functions to your file, read-a and read-b. Each takes a flights file and a tickets file and returns your dataset in that organization. You will call them by these names in later tasks, so check that they exist with those names and arguments.

Task 8

How would you check that Claude's readers actually put the same data into both organizations, and lose nothing from the CSV files? Write a comment in your worksheet explaining how you would go about this.

Checkpoint

Show a TA your CSVs, your readers, and your ideas on validation.

Step 3Time it and plot

We've written some support code for you to find out how fast your functions run and plot the results. Copy the code in the dropdown into your file, after your use context line and before your own definitions. We'll explain the functions as you need them for the next couple of tasks.

The timing and plotting code
import charts as C
include from C:
  from-list,
  render-charts
end

# Total milliseconds for reps calls of thunk.
fun time-reps(thunk, reps):
  start = time-now()
  out = each(lam(_): thunk() end, range(0, reps))
  time-now() - start
end

# Average milliseconds per call of thunk. The clock only reports whole
# milliseconds, so a call that takes microseconds is repeated, doubling the
# number of repetitions until the total passes 50 ms.
fun time-it(thunk):
  fun go(reps):
    elapsed = time-reps(thunk, reps)
    if elapsed >= 50: elapsed / reps else: go(reps * 2) end
  end
  go(1)
end

# Plot two lines against the same sizes.
fun plot-times(title, sizes, a-times, b-times):
  render-charts([list:
      from-list.line-plot(sizes, a-times).legend("A"),
      from-list.line-plot(sizes, b-times).legend("B")])
    .title(title)
    .x-axis("number of tickets")
    .y-axis("milliseconds per call")
    .display()
end

Task 9

First, we want you to understand how to measure the time taken to run one computation. Let's say you wanted to time the computation of who-is-on-a(my-dataset, 100). You would write the following:

time-it(lam(): who-is-on-a(my-dataset, 100) end)

time-it takes a function with no arguments that runs the computation you want to time. Internally, it starts a timer, runs the code inside the lam many times, then stops the timer, reporting the average time per run.

You try it. Read fixed-flights.csv and fixed-tickets-100.csv into organization A and organization B using read-a and read-b. Use time-it to find how long “who is on flight 100?” takes in each organization on that dataset. Then do the same with fixed-tickets-1600.csv.

Task 10

Now we want to get the times on every one of the fixed-tickets-N.csv datasets, for both organizations, and plot the results as the number of tickets grows. Imagine that you had a list of all the fixed-ticket CSV filenames. How could you run time-it on each one of them and gather up a list of the results? Write an expression that will do this.

If you had a list of times from two different functions on the same datasets, we can ask Pyret to draw a plot of the two lists of times. The function

plot-times(title, sizes, a-times, b-times)

plots two lists of times against a list of dataset sizes. The "title" is the label that goes on the plot. Use this to create a plot of the times for each organization against all of the fixed-ticket files.

Task 11

Compare each plot with your prediction from Task 6. Do the plots support your prediction, or not? If not, what do you think is going on?

Checkpoint

Show a TA your plots.

Task 12

Take a step back: what have you learned from this lab so far? What ideas are new to you? What techniques are you learning? What questions do you have?

Step 4If you still have time, change what grows

Task 13

The grow- files hold datasets where every flight has 20 tickets and the number of flights grows. Predict what happens to the lines for both functions as the number of flights grows. Then repeat Task 10 on those datasets and check your predictions. (The last flight is no longer number 100.)