Sets - Chapter 8 Flashcards
A blank is a collection of distinct elements
set
A set blank operation adds an element to the set, provided an equal element doesn’t already exist in the set.
add
A set is an blank collection
unordered
Set blank may be primitive data values, such as numbers or strings, or objects with numerous data members.
elements
When storing objects, set implementations commonly distinguish elements based on an element’s blank: A primitive data value that serves as a unique identifier for the element.
key value
Sets are commonly implemented to use keys for blank element types.
all
When storing objects, the set retrieves an object’s blank via an external function or predetermined knowledge of which object property is the key value.
key
When storing blank data values, each primitive data value’s key is itself.
primitive
Given a key, a set blank operation removes the element with the specified key from the set.
remove
Given a key, a set blank operation returns the set element with the specified key, or null if no such element exists.
search
The search operation can be used to implement a blank.
subset test
A set X is a blank of set Y only if every element of X is also an element of Y.
subset
The blank of sets X and Y, denoted as X ∪ Y, is a set that contains every element from X, every element from Y, and no additional elements.
union
The blank of sets X and Y, denoted as X ∩ Y, is a set that contains every element that is in both X and Y, and no additional elements.
intersection
The blank of sets X and Y, denoted as X \ Y, is a set that contains every element that is in X but not in Y, and no additional elements.
difference
The blank and blank operations are commutative, so X ∪ Y = Y ∪ X and X ∩ Y = Y ∩ X. The blank operation is not commutative.
union and intersection
difference
A blank operation on set X produces a subset containing only elements from X that satisfy a particular condition
filter
The condition for filtering is commonly represented by a blank: A function that takes an element as an argument and returns a Boolean value indicating whether or not that element will be in the filtered subset.
filter predicate
A blank operation on set X produces a new set by applying some function F to each element.
map
A blank is a set that can change after being constructed.
dynamic set
A blank is a set that doesn’t change after being constructed
static set
A set can be implemented in Python using a blank to store set elements. In practice, a balanced BST or hash table is often used to efficiently implement a set, but a BST will suffice for all necessary set operations.
binary search tree (BST)
The set implementation supports iterating through all items in the set. The Set class’s blank instance method constructs and returns a BSTIterator object referencing the minimum node in the tree.
__iter__()
The Set class’s blank method takes an optional argument for a get-key function.
__init__()
The blank takes an element as an argument and returns the element’s key. If no get-key function argument is passed to the Set constructor, then a default lambda function is used that takes an element as an argument and returns the same element as the key. The get-key function is used for comparing elements in the set’s BST implementation.
get-key function
A blank provides a shorthand notation for creating a function object. An expression of the form:
get_key = lambda x: x
assigns get_key as a function object with functionality equivalent to:
def get_key(x):
return x
A lambda function allows a variable to reference a function without declaring the function as global or an instance method.
lambda function
The Set class implements standard blank in the add(), remove(), and search() methods. The __len__() method returns the set’s length by counting the number of nodes in the BST. The remaining methods implement common set operations such as difference(), filter(), intersection(), map(), and union().
BST functionality
Builds a new set by adding elements returned from a function. The function is passed as an argument and is called for each element in the instance set.
map
Allows a Set object to be iterated through in a for loop.
__iter__() method
Builds and returns the set of elements that exist only in both sets.
intersection
Builds and returns the set of elements that exist in 1 or both sets.
Union
Builds and returns the set of elements that exist only in the instance set, and not in the other set.
difference
Builds and returns the set of elements from the instance set that satisfy the predicate.
filter
