Held: Wednesday, 12 November 2014
Back to Outline 39 - Project Kickoff.
On to Outline 41 - Randomized (Unpredictable) Drawing.
Summary
We consider vectors, an alternative to lists for storing collections
of data.
Related Pages
Overview
- Problems with lists.
- A solution: Vectors.
- Behind the scenes: How Scheme implements vectors.
- Important vector procedures.
Administrivia
- New partners (some cards may be missing, so we'll adapt)!
Upcoming Work
Extra Credit Opportunities
Academic
- Scholars' Convocation, noon, today: Dean Latham.
- Town Hall Thursday on Sustainability, noon and 7:30 p.m. (I think)
- CS Table Friday: Shellshock
Peer Support
- Football, Saturday at noon vs. Lawrence.
- Karan's radio show 11pm Thursday nights on KDIC
- Evan's radio show 5pm Friday nights on KDIC
- Donna's radio show Sunday midnight on KDIC
Data Types
- At the start of the semester, we decided that "basic values and
operations on those values" are key to writing algorithms.
- We tend to use the word "type" to express these two concepts.
- We've seen a variety of characteristics of types in 151.
- Some types are defined in terms of a list of possible values or a simple construction method: Character, Boolean, RGB color, etc.
- Some types that can potentially be defined recursively: Drawings-as-value,
Maybe integers, Lists.
- Some types are designed to collect other kinds of values: Lists. (Okay, maybe that's it for now.)
- We're about to learn a few more. Vectors today. Pair structures (particularly trees) on Monday.
List Deficiencies
- Now that we've worked with lists for a while, we've identified
some things that make lists inappropriate for some situations.
- List are expensive to use; to find the length of a list
or to access an element late in the list, you need to cdr down the
list.
- Lists are fixed; you can't easily change an element of a
list.
- At the same time, there are some advantages to lists:
- Lists are dynamic; it is easy to grow and shrink a list.
- Lists are inherently recursive; the type is defined
recursively.
- Lists are simple; you can build almost every list operation
through just a few basic operations (
car, cdr,
null, and null?).
An Alternative: Vectors
- Vectors provide an alternative to lists.
- They have two primary advantages:
- Vectors are indexed: You can quickly access elements by number.
- Vectors are mutable: You can change the elements of a vector.
- In order to obtain these benefits, vectors lack some key features of lists. In particular,
- Vectors are static: Once you've created a vector, you cannot change its length.
- Some key vector procedures:
(vector val1 ... valn): Create a vector(make-vector length val): Make a vector of specified length, with duplicates of val as the contents.(vector-ref vector position): Extract a value from a vector.(vector-set! vector position newvalue): Change an element of a vector.(vector-length vector)
Implementing Vectors
- To be done live in class: Memory layout and more.
Lab