The Dictionary ADT
What is a dictionary?
Dictionaries map keys to values.
Copyright By PowCoder代写 加微信 powcoder
• If you have a key, you can look up the associated value. • Can add and (usually) remove keys.
• Both keys and values can be of any type.
• Dictionary is an ADT; many possible implementations! And tons of different ones exist, for different use cases
• One of the most widespread and useful ADTs
• We’ll see one way to define the dictionary ADT
Lots of variants, with different operations, laws, …
All with pros and cons
All share the essence of mapping keys to values
When to use a dictionary?
Dictionaries map keys to values.
Common use case: you have information about some objects
that you want to look up based on the “names” of these objects.
• The titular example: (language) dictionaries. By looking up a word (key), you can find its definition (value).
• Say I want to call my friend Willie. If I have a phonebook, I can find his phone number (value) by looking up his name (key) in the phonebook.
• I want to represent the cities in each US state → dictionary with states as keys and a set of cities as values.
Can combine ADTs! For non-toy problems, you usually need to. (We’ll see more throughout the quarter.)
We can lookup what cities are in Illinois.
But we can’t lookup which state Chicago is in! (stay tuned)
The Dictionary ADT: values and operations
Looks like: Signature:
interface DICT[K, V]: # key and value types up to client
def mem?(self, key: K) -> bool?
def get(self, key: K) -> V
def put(self, key: K, value: V) -> NoneC
def del(self, key: K) -> NoneC
• Keys must all be distinct
• Order of keys isn’t significant
{a:6, b:7, c:8}
The Dictionary ADT: laws
{k0:v0,…,ki:vi,…}
{∀i, ki ̸= k}
d= ∧∀i,ki ̸=k d.put(k,v)⇒Noned=
{…,ki:vi,…}
{…,ki:vi,…}
{…,ki:vi,…}
d= d.del(ki)⇒Noned=
• That’s a lot of stuff. We’ll do one operation at a time.
.mem?(ki ) ⇒ True {} .mem?(k) ⇒ False {}
.get(ki) ⇒ vi {}
{…,ki:vi,…,k:v}
{…,ki:vi,…}
{. . . , ki−1:vi−1, ki+1:vi+1, . . .}
Bidirectional mappings
Very common in programming. Dictionaries can help! Need to look things up in two directions:
• Letters A–Z to numbers 1–26
Convert back and forth between letters and numbers
• Runners to their position in the race
May want to know which runner is in second place, OR
know which position runner Isabel is at
• US states to cities and cities in them (revisited)
Now we can both know which cities are in Illinois AND know which state Chicago is in
Represent using a pair of dictionaries! One for each direction.
{A:1, B:2, C:3, …}
{1:A, 2:B, 3:C, …}
The quest for a dictionary data structure
ADT vs Data Structure
• Ok, so now we know how dictionaries should behave I.e., their specification
• We still don’t know we we could build one, though I.e., their implementation: a concrete data structure
• Let’s hear your ideas
A data structure for dictionaries
There are many data structures we can use to represent dictionaries:
• A sorted array of key-value pairs
• A list of keys-value pairs (an association list) • A hash table (next time)
• Etc. We’ll see more later in the quarter!
They can all provide the necessary operations, but with different costs!
A sorted array dictionary
key key key key val val val val
• We look things up by key
• Therefore, vector is sorted by key • How can we do lookups?
key key val val
Sorted array lookup: Binary search
We saw it last time, but let’s recap real quick.
We’re showing an array with just the keys.
• You can assume the values are tagging along • We’ll do that a lot, for simplicity
• Suppose we’re looking up 75
• Initially, the element could be anywhere in the array
• Compare with the middle element
• Each iteration, possible range is cut in half
• This can happen at most log2 n times • Hence, O(log n). Sweet.
Sorted array insertion
• Inserting into an array requires shifting elements out of the way, to make room for the new one
Cf., full bookcase analogy
• There may be as many as n elements to move • Hence insertion is O(n)
Association list lookup
key val next
key key key val val val next next next
Binary search won’t work; linear search is our only option • Elements are not necessarily sorted
• Can’t jump to the middle of a linked list anyway → O(n) worst case
Association list insertion
key val next
key key key val val val next next next
key key val val next next
Inserting at the front (O(1)!) does not work with duplicate keys. • The same key may exist further down the list!
• But we probably want to either error or update! Oops.
Need to go through the entire list, then insert (front or back). → O(n)
Alternatively, be ok with duplicate keys (and wasted space).
• Always lookup from the start, so can’t find later k-v pair
• If you know you’ll never insert same key twice, may be ok!
Association lists
Seems like a poor choice complexity-wise. • O(n) lookup
• O(n) insert (or wasting space) But complexity is not everything!
• Maybe your dictionaries are very small! (small n)
• Simpler than the alternatives! Easier to whip up in a pinch
(see homework 3).
We’ll have more to say on how to choose data structures later in the quarter.
Comparing dictionaries
Multiple data structures following the same ADT interface → can swap implementations in and out!
Main difference: efficiency → let’s measure that! Let’s time insertions and lookups as n grows for
• An association list
• A sorted vector dictionary
• A hash table (topic of the next lecture) • An AVL tree (see later in the quarter)
See benchmarks.rkt on Canvas.
Next time: hashing and hash tables
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com