程序代写 Abstract Data Types

Abstract Data Types

Abstract Data Types (ADTs)
• Due to in 1974

􏰀 She received the 2008 Turing Award for this work
• One of the most important advances in programming
􏰀 On par with structured programming and automatic memory
management
• Will be one of our guiding notions in this class

What is an ADT?
An ADT defines:
• A set of (abstract) values
• A set of (abstract) operations on those values An ADT omits:
• How the values are concretely represented • How the operations work
Omissions = Axes of Freedom!
• Can choose between many different representations! • And/or implementations for operations!
• Each with their own tradeoffs

ADT: Stack
Think: A stack of plates, or a program’s call stack Abstract values look like:

ADT: Stack
Think: A stack of plates, or a program’s call stack Abstract values look like:
Abstract operations signature: • push(Stack, Element): None • pop(Stack): Element
• empty?(Stack): Bool

ADT: Stack
Think: A stack of plates, or a program’s call stack Abstract values look like:
Abstract operations signature, as a DSSL2 interface:
interface STACK:
def push(self, element)
def pop(self)
def empty?(self)
• DSSL2 interface ≈ C++ abstract class
• Abstractly specifies operations, but not concrete
implementations
• Classes can implement interfaces to fill those in

ADT: Stack
Think: A stack of plates, or a program’s call stack Abstract values look like:
Abstract operations signature, with contracts:
interface STACK[T]: # E.g., stack of ints, of strings, …
def push(self, element: T) -> NoneC
def pop(self) -> T
def empty?(self) -> bool?
• Contracts are a way to checking type-like constraints during program execution
• We may use some in examples or in starter code, but you don’t need to write new ones (unless you want to)
• More details in the docs

ADT: Queue (FIFO)
Think: A queue to check out (or get in!) at the grocery store, a playlist in a music player
Abstract values look like:
Abstract operations signature, with contracts:
interface QUEUE[T]:
def enqueue(self, element: T) -> NoneC
def dequeue(self) -> T
def empty?(self) -> bool?

Stack versus Queue
interface STACK[T]:
def push(self, element: T) -> NoneC
def pop(self) -> T
def empty?(self) -> bool?
interface QUEUE[T]:
def enqueue(self, element: T) -> NoneC
def dequeue(self) -> T
def empty?(self) -> bool?
Same thing modulo names!
So what’s the difference?
Clearly we’re missing something…

Adding laws
{p} f(x) ⇒ y {q}
means that if precondition p is true when we apply f to x then we
will get y as a result, and postcondition q will be true afterward.

Adding laws
{p} f(x) ⇒ y {q}
means that if precondition p is true when we apply f to x then we
will get y as a result, and postcondition q will be true afterward. Examples:
{a = [2,4,6,8]} a[2] ⇒ 6 {a = [2,4,6,8]}
{a = [2,4,6,8]} a[2] = 19 ⇒None {a = [2,4,19,8]}
This notation is called Hoare triples, after C. A. R. (Tony) Hoare • 1980 Turing award, quicksort, concurrency, etc.

ADT: Stack
Abstract values look like: Abstract operations signature:
interface STACK[T]:
def push(self, element: T) -> NoneC
def pop(self) -> T
def empty?(self) -> bool?
􏰂 s.pop() ⇒ e
{} .empty?() ⇒ True {} .empty?() ⇒ False {}
􏰂 s.push(e) ⇒None 􏰁s = 􏰂
|e1,…,ek⟩
|e1,…,ek,ek+1⟩
|e1,…,ek,e⟩
|e1,…,ek,ek+1⟩
|e1,…,ek⟩

ADT: Queue (FIFO)
Abstract values look like: Abstract operations signature:
interface QUEUE[T]:
def enqueue(self, element: T) -> NoneC
def dequeue(self) -> T
def empty?(self) -> bool?
{} .empty?() ⇒ True {} .empty?() ⇒ False {}
􏰂 q.enqueue(e) ⇒ None 􏰁q =
􏰂 q.dequeue()⇒e 􏰁q= 1
⟨e1,…,ek⟨
⟨e1,…,ek,ek+1⟨
⟨e1,…,ek,e⟨
⟨e1,e2,…,ek⟨
⟨e2,…,ek⟨

Stop! Question time!
Before we move on to implementations…
Anything unclear so far? Anything I missed?

Stack implementation: linked list
let s = ListStack()

Stack implementation: linked list
let s = ListStack() s.push(2)

Stack implementation: linked list
let s = ListStack() s.push(2) s.push(3)
push = add to start of list
data data next next

Stack implementation: linked list
let s = ListStack() s.push(2) s.push(3) s.push(4)
push = add to start of list
data data data next next next

Stack implementation: linked list
data data data data next next next next
let s = ListStack() s.push(2) s.push(3) s.push(4) s.push(5)
push = add to start of list

Stack implementation: linked list
let s = ListStack() s.push(2) s.push(3) s.push(4) s.push(5)
push = add to start of list
pop = remove from front of list
data data next next

Stack implementation: linked list
let s = ListStack() s.push(2) s.push(3) s.push(4) s.push(5)
s.pop() s.pop()
push = add to start of list
pop = remove from front of list
data data next next

Stack implementation: array
Allocate array with spare capacity. Keep track of # of elements.
let s = VecStack()

Stack implementation: array
Allocate array with spare capacity. Keep track of # of elements.
let s = VecStack() s.push(2)

Stack implementation: array
Allocate array with spare capacity. Keep track of # of elements.
let s = VecStack() s.push(2) s.push(3)

Stack implementation: array
Allocate array with spare capacity. Keep track of # of elements.
let s = VecStack() s.push(2) s.push(3) s.push(4)

Stack implementation: array
Allocate array with spare capacity. Keep track of # of elements.
let s = VecStack() s.push(2) s.push(3) s.push(4) s.push(5)

Stack implementation: array
Allocate array with spare capacity. Keep track of # of elements.
let s = VecStack() s.push(2) s.push(3) s.push(4) s.push(5) s.push(6)
With an array, capacity is an issue. → Dyn. arrays (last time) can fix.

Tradeoffs: linked list stack versus array stack
Time costs
• All operations are always cheap for both versions
􏰀 Cheap = number of elements doesn’t affect cost
􏰀 Expensive = cost increases with number of elements
• Linked list version: add and remove at start • Array version: read and write array elements
􏰀 Well, except if array fills up
􏰀 Then either expensive or impossible
• We’ll make costs accounting precise in the next lecture

Tradeoffs: linked list stack versus array stack
Space costs
• Linked list stack only fills up when memory fills up
• Array has a fixed size (or must reallocate)
• Array stack has better cache locality (see 213)
• Linked list nodes must be allocated each time, and may be
scattered all over memory
• Array stack’s space usage is tighter: all the space is used for elements, not for arrows between nodes
• Linked list stack’s space usage is smoother: no big jumps in usage as size grows, gradual increase

Queue implementation: linked list?
let q = ListQueue()

Queue implementation: linked list?
let q = ListQueue() q.enqueue(2)

Queue implementation: linked list?
let q = ListQueue() q.enqueue(2) q.enqueue(3)
Add at the front. QUIZ: cheap?

Queue implementation: linked list?
let q = ListQueue() q.enqueue(2) q.enqueue(3)
Add at the front. Cheap.

Queue implementation: linked list?
let q = ListQueue() q.enqueue(2) q.enqueue(3) q.enqueue(4)
Add at the front. Cheap.
data data next next

Queue implementation: linked list?
data data data next next next
let q = ListQueue() q.enqueue(2) q.enqueue(3) q.enqueue(4) q.enqueue(5)
Add at the front. Cheap.

Queue implementation: linked list?
data data data next next next
let q = ListQueue() q.enqueue(2) q.enqueue(3) q.enqueue(4) q.enqueue(5) q.dequeue()
Add at the front. Cheap.
Remove at the back. QUIZ: cheap?

Queue implementation: array?
let q = VecQueue()

Queue implementation: array?
let q = VecQueue() q.enqueue(2)

Queue implementation: array?
let q = VecQueue() q.enqueue(2) q.enqueue(3)

Queue implementation: array?
let q = VecQueue() q.enqueue(2) q.enqueue(3) q.enqueue(4)

Queue implementation: array?
let q = VecQueue() q.enqueue(2) q.enqueue(3) q.enqueue(4) q.enqueue(5)

Queue implementation: array?
let q = VecQueue() q.enqueue(2) q.enqueue(3) q.enqueue(4) q.enqueue(5) q.dequeue()
Remove at the start.
Then shift everything? Expensive! (And capacity is still an issue…)
Anything else we could try?

Queue impl.: linked list with tail pointer
let q = ListQueue()

Queue impl.: linked list with tail pointer
let q = ListQueue() q.enqueue(2)

Queue impl.: linked list with tail pointer
let q = ListQueue() q.enqueue(2) q.enqueue(3)
data data next next
Add at the end. QUIZ: cheap?

Queue impl.: linked list with tail pointer
let q = ListQueue() q.enqueue(2) q.enqueue(3)
data data next next
Add at the end. Cheap!

Queue impl.: linked list with tail pointer
let q = ListQueue() q.enqueue(2) q.enqueue(3) q.enqueue(4)
data data data next next next
Add at the end. Cheap!

Queue impl.: linked list with tail pointer
let q = ListQueue() q.enqueue(2) q.enqueue(3) q.enqueue(4) q.enqueue(5)
data data next next
data data next next
Add at the end. Cheap!

Queue impl.: linked list with tail pointer
let q = ListQueue() q.enqueue(2) q.enqueue(3) q.enqueue(4) q.enqueue(5) q.dequeue()
data data data next next next
Add at the end. Cheap!
Remove at the front! QUIZ: cheap?

Queue impl.: linked list with tail pointer
let q = ListQueue() q.enqueue(2) q.enqueue(3) q.enqueue(4) q.enqueue(5) q.dequeue() q.dequeue()
data data next next
Add at the end. Cheap!
Remove at the front! Also cheap!

Queue implementation: ring buffer
data start len
let q = RingBuffer()

Queue implementation: ring buffer
data start len
let q = RingBuffer() q.enqueue(2)

Queue implementation: ring buffer
data start len
let q = RingBuffer() q.enqueue(2) q.enqueue(3)

Queue implementation: ring buffer
data start len
let q = RingBuffer() q.enqueue(2) q.enqueue(3) q.enqueue(4)

Queue implementation: ring buffer
data start len
let q = RingBuffer() q.enqueue(2) q.enqueue(3) q.enqueue(4) q.enqueue(5)

Queue implementation: ring buffer
data start len
let q = RingBuffer() q.enqueue(2) q.enqueue(3) q.enqueue(4) q.enqueue(5) q.dequeue()
Remove at start! Cheap!

Queue implementation: ring buffer
data start len
let q = RingBuffer() q.enqueue(2) q.enqueue(3) q.enqueue(4) q.enqueue(5) q.dequeue() q.dequeue()
Remove at start! Cheap!

Queue implementation: ring buffer
data start len
let q = RingBuffer() q.enqueue(2) q.enqueue(3) q.enqueue(4) q.enqueue(5) q.dequeue() q.dequeue()
2 3 4 5 6 7 8 9
Remove at start! Cheap!

Queue implementation: ring buffer
data start len
let q = RingBuffer() q.enqueue(2) q.enqueue(3) q.enqueue(4) q.enqueue(5) q.dequeue() q.dequeue()
20 3 4 5 6 7 8 9
. q.enqueue(0)
Remove at start! Cheap!
Add at (start+len) % size! Cheap too!

Queue implementation: ring buffer
data start len
let q = RingBuffer() q.enqueue(2) q.enqueue(3) q.enqueue(4) q.enqueue(5) q.dequeue() q.dequeue()
q.enqueue(0) q.dequeue()
020 3 4 5 6 7 8 9
Remove at start! Cheap!
Add at (start+len) % size! Cheap too!

Tradeoffs: linked list queue versus ring buffer
Basically the same as for the stack implementations: • Operations are cheap for both.
• Ring buffer has better locality, and doesn’t waste space with arrows between nodes.
• Linked list doesn’t get full.

See it in action!
(USF) designed some really nice data structure visualizations.
We’ll be referring to them throughout the quarter. You can see his stack and queue visualizations here:
• https://www.cs.usfca.edu/~galles/ visualization/StackArray.html
• https://www.cs.usfca.edu/~galles/ visualization/StackLL.html
• https://www.cs.usfca.edu/~galles/ visualization/QueueArray.html
• https://www.cs.usfca.edu/~galles/ visualization/QueueLL.html

Stop! Question time!
Before we move on to revisiting other ADTs we’ve seen before today…
Anything unclear so far? Anything I missed?

ADTs we’ve already seen

• Abstract values: mathematical sets: ,
• Abstract operations: membership (∈), insertion (+), etc.
{e0,…,ek,…,en}
{“red”, “green”, “blue”}
• Laws (examples): {}
.member?(ek) ⇒True {}
∧ek ∈/s􏰂 s.member?(ek)⇒False{}
s.insert(ek) ⇒None
{e0, …, en}
{e0, …, en}
• Concrete implementations:
􏰀 We saw array, sorted array, linked list 􏰀 Others are possible
{{1, 2}, {3, 4}}
{e0, …, en}

• Abstract values: ordered collections of items: , etc.
• Abstract operations: read/write nthelement, add/remove at the start/end, etc.
• Laws (examples):
{} .read(k) ⇒ ek {}
{n < k} .read(k) ⇒ error {} s.push_front(ek) ⇒None [1, 5, 2, 28, −3] [e0, ..., en] [e0,...,ek,...,en] [e0, ..., en] 􏰁s = 􏰂 􏰀 Linked lists (any kind), arrays, dynamic arrays, etc. • Concrete implementations: [ek,e0,...,en] If we have time: Ring buffer in DSSL2 Representation and initialization class RingBuffer (QUEUE): let data: VecC let start: nat? let size: nat? def __init__(self, capacity): self.data = [None; capacity] self.start = 0 self.size = 0 Size querying class RingBuffer (QUEUE): let data: VecC let start: nat? let size: nat? # ok to have more operations in the class # than in the interface def cap(self): return self.data.len() def len(self): return self.size def empty?(self): return self.len() == 0 def full?(self): return self.len() == self.cap() Enqueueing class RingBuffer (QUEUE): let data: VecC let start: nat? let size: nat? def enqueue(self, element): if self.full?(): # check pre-condition error('RingBuffer.enqueue: full') let index = (self.start + self.size) % self.cap() self.data[index] = element self.size = self.size + 1 Dequeueing class RingBuffer (QUEUE): let data: VecC let start: nat? let size: nat? def dequeue(self): if self.empty?(): error('RingBuffer.dequeue: empty') let result = self.data[self.start] self.data[self.start] = None # no leaks! self.size = self.size - 1 self.start = (self.start + 1) % self.cap() return result Next time: Asymptotic complexity 程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts