https://gettingreal.37signals.com/ch02_Whats_Your_Problem.php

Data Structures: An Overview¶

Motivation¶

History¶

Babbage designed the Difference Machine: https://www.youtube.com/watch?v=be1EM3gQkAY to build error-free mathmatical tables. He automated the process of creating printing plates, thereby reducing the typesetting errors of the time.

He then generalized the Difference Machine to the first (if it had been built) Turing-complete computer. It has an arithmetic logic, memory, and control flow (branching & loops).

Ada Lovelace wrote the first algorithm to compute the Bernoulli (Kowa) sequence for the Babbage Analytical Engine.

“As soon as an Analytical Engine exists, it will necessarily guide the future course of the science. Whenever any result is sought by its aid, the question will then arise—By what course of calculation can these results be arrived at by the machine in the shortest time?”

Charles Babbage Passages from the Life of a Philosopher

Babbage’s design was revolutionary in that the computer could store and then retrieve data. Then it was “pegs in a barrel” –like a music box. Today it it’s groups of bits (GOBs).

Storing and Fetching¶

The Analytical Engine only used fixed point arithmetic (column width of 50).
Data Structures improve the storing and/or fetching of GOBS.
Data Structures organize GOBs

Collections¶

GOBs are organized into data structures.

These are then grouped into data types:

Primitive
Composite
Abstract Data Types (ADT)

Primitive¶

<thead>
    <tr>
        <th>type</th>
        <th>values</th>
        <th>implementation</th>
    </tr>
</thead>
<body>
    <tr>
        <td>Boolean</td>
        <td>true or false</td>
        <td>bool</td>
    </tr>
    <tr>
        <td>Character</td>
        <td>grapheme or unicode point</td>
        <td>s[n] or ord(s[n])</td>
    </tr>
    <tr>
        <td>Floating Point</td>
        <td>single-precision real numbers</td>
        <td>--</td>
    </tr>
    <tr>
        <td>Double precision</td>
        <td>wider float</td>
        <td>float</td>
    </tr>
    <tr>
        <td>Integer</td>
        <td>integral or fixed-precision values</td>
        <td>int</td>
    </tr>
    <tr>
        <td>Enumeration</td>
        <td>small set of uniquely-name values</td>
        <td>NamedTuple</td>
    </tr>
</body>

Composite¶

<thead>
    <tr>
        <th>type</th>
        <th>definition</th>
        <th>implementation</th>
    </tr>
</thead>
<body>
    <tr>
        <td>Array</td>
        <td>true or false</td>
        <td>bool</td>
    </tr>
    <tr>
        <td>Record</td>
        <td>value containing other values --static & fixed</td>
        <td>tuple</td>
    </tr>
    <tr>
        <td>Union</td>
        <td>specifies primitive values</td>
        <td>--</td>
    </tr>
    <tr>
        <td>Union</td>
        <td>specifies primitive values</td>
        <td>--</td>
    </tr>
</body>

Abstract Data Types¶

Collection (Container)
List
Stack
Queue
Deque (Double-ended queue)
Priority queue
Associative array
Multimap
Multiset
Set
Tree
Graph

For this class:

We will consume primitive and composite data types.

These are encapsulated quite nicely by Python.
We care about what they do

We will implement ADT

We care about performance
We look at their attributes and operations.

Definition¶

Abstract Data Type:

A set of data values and associated operations that are precisely specified independent of any particular implementation.

Note: Since the data values and operations are defined with mathematical precision, rather than as an implementation in a computer language, we may reason about effects of the operations, relations to other abstract data types, whether a program implements the data type, etc.

Paul E. Black, “abstract data type”, in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 10 February 2005. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/abstractDataType.html

ADT is a mathmatical model of a data structure.

* A developer implements the data structure. * A user expects certain behaviors from the implementation.

Attributes¶

index, key
node
edge
length, size
value, cargo, information
next
previous
leaf
head
tail

Operations¶

<thead>
    <tr>
        <th>operation</th>
        <th>definition</th>
        <th>aka</th>
    </tr>
</thead>

<tr>
    <td>SEARCH(S, k)</td>
    <td>A query that, given a set S and a key value k, returns a pointer x to an element in S such that x.key = k, or NIL if no such element belongs to S.</td>
    <td>traverse, walk</td>
</tr>
<tr>
    <td>INSERT(S, x)</td>
    <td>A modifying operation that augments the set S with the element pointed to by x. We usually assume that any attributes in element x needed by the set implementation have already been initialized.</td>
    <td>push(head), add(tail)</td>
</tr>
<tr>
    <td>DELETE(S, x)</td>
    <td>A modifying operation that, given a pointer x to an element in the set S, removes x from S. (Note that this operation takes a pointer to an element x, not a key value.)</td>
    <td>remove, pop</td>
</tr>
<tr>
    <td>MINIMUM(S)</td>
    <td>A query on a totally ordered set S that returns a pointer to the element of S with the smallest key.</td>
    <td></td>
</tr>
<tr>
    <td>MAXIMUM(S)</td>
    <td>A query on a totally ordered set S that returns a pointer to the element of S with the largest key.</td>
    <td></td>
</tr>
<tr>
    <td>SUCCESSOR(S, x)</td>
    <td>A query that, given an element x whose key is from a totally ordered set S, returns a pointer to the next larger element in S, or NIL if x is the maximumelement.</td>
    <td>next</td>
</tr>
    <td>PREDECESSOR(S, x)</td>
    <td>A query that, given an element x whose key is from a totally ordered set S,returns a pointer to the next smaller element in S, or NIL if x is the minimum element.</td>
    <td>previous, prior</td>

In [1]: