4. Core Data Structures and CollectionsIntroduction and ContextArtificial intelligence and machine learning systems are built from data, but data rarely arrives in the exact form required by an algorithm. Text must be cleaned, observations must be grouped, features must be indexed, labels must be counted, and configuration values must be stored for repeated use. Python’s built-in data structures provide the basic vocabulary for these operations. They are not merely convenient containers; they influence algorithmic complexity, memory consumption, reproducibility, and the clarity of a solution. A model-training pipeline may represent a document as a string, a sequence of tokens as a list, an immutable configuration as a tuple, unique labels as a set, and feature metadata as a dictionary. Selecting the appropriate structure is therefore a design decision. A program that uses a list for constant-time membership testing may work correctly on a small dataset but become inefficient at production scale. Similarly, careless copying of nested structures can cause data leakage or unexpected mutation. This chapter examines strings, lists, tuples, sets, dictionaries, ranges, and specialised collections in Python. It develops a unified understanding of indexing, slicing, mutability, hashing, equality, copying, and memory implications, then applies these ideas to AI and ML workflows. Learning ObjectivesAfter studying this chapter, you should be able to: 1. Explain the characteristics and appropriate uses of Python’s principal collection types. 2. Apply indexing, slicing, unpacking, iteration, and membership operations correctly. 3. Distinguish mutable, immutable, ordered, hashable, and unhashable objects. 4. Select data structures using considerations of time complexity, memory, and semantics. 5. Explain shallow copying, deep copying, aliasing, and their consequences in nested data. 6. Use dictionaries, sets, ranges, and specialised collections in practical AI and ML tasks. 7. Identify common errors involving mutation, hashing, views, ordering, and inefficient access. 8. Evaluate collection designs in a realistic data-processing scenario. A Mental Model: Objects, References, and CollectionsIn Python, a variable name refers to an object. The name does not contain the object itself in the way a fixed-size variable in some languages may contain a value. For example: ```python features = [0.2, 0.8, 0.4] backup = features backup.append(1.0) print(features) # [0.2, 0.8, 0.4, 1.0] ``` Both names refer to the same list. This relationship is called aliasing. Assignment generally binds another name to an existing object; it does not automatically copy the object. The identity operator `is` tests whether two references point to the same object, whereas `==` tests value equality. These tests answer different questions and should not be interchanged. Collections also differ in whether they can be changed after creation. A mutable object, such as a list or dictionary, can have its contents changed. An immutable object, such as a string or tuple, cannot be modified in place. Immutability does not mean that a variable can never be rebound: ```python name = "Ada" name = name + " Lovelace" ``` The original string was not changed; a new string was created and assigned to `name`. Indexing and slicingSequence types support positional access. Indexing starts at zero, and negative indices count from the end: ```python values = [10, 20, 30, 40, 50] values[0] # 10 values[-1] # 50 values[1:4] # [20, 30, 40] values[::2] # [10, 30, 50] values[::-1] # [50, 40, 30, 20, 10] ``` A slice has the general form `sequence[start:stop:step]`. The start is included, but the stop is excluded. A slice usually creates a new object for standard sequences. Thus, `values[1:3]` creates a new list, although the elements inside it may still refer to the same objects as the original list. This distinction becomes important for nested mutable structures. Strings: Text as an Immutable SequenceA string is an immutable sequence of Unicode characters. It supports indexing, slicing, iteration, membership testing, comparison, and many transformation methods. Since strings are immutable, methods such as `replace`, `lower`, and `strip` return new strings. ```python text = " Neural Networks " clean = text.strip().lower() print(clean) # neural networks print(clean.replace(" ", "_")) # neural_networks ``` String immutability makes text values safer to share, but repeated concatenation in a loop can be inefficient because each concatenation may create a new string. For assembling many pieces, use `str.join`: ```python words = ["data", "drives", "models"] sentence = " ".join(words) ``` Important operations include `split`, `join`, `find`, `startswith`, `endswith`, `count`, `partition`, and formatted string construction. `split` converts text into a list, while `join` combines an iterable of strings. A delimiter belongs to the operation that joins the pieces; it is not automatically added to the elements. Text processing also requires attention to representation. Unicode characters may occupy different numbers of bytes when encoded, so character length and encoded byte length are not always the same. For example, `len(text)` counts Python string elements, while `len(text.encode("utf-8"))` counts bytes in UTF-8 representation. In multilingual ML applications, explicit encoding and normalization policies are essential. Formatted strings improve readability and reduce accidental type-conversion errors: ```python accuracy = 0.9375 message = f"Validation accuracy: {accuracy:.2%}" ``` A frequent mistake is assuming that string methods mutate their receiver: ```python label = "Positive" label.lower() print(label) # Positive label = label.lower() ``` Lists: Mutable Ordered CollectionsLists are ordered, mutable sequences. They are suitable when order matters, duplicates are allowed, and the collection will change. Typical operations include `append`, `extend`, `insert`, `remove`, `pop`, `clear`, `sort`, and `reverse`. ```python batch = ["image_1", "image_2"] batch.append("image_3") batch.extend(["image_4", "image_5"]) ``` `append(x)` adds one object as a single element, whereas `extend(iterable)` adds each element from the iterable. Confusing these operations produces nested lists unexpectedly. List comprehensions express transformations and filtering compactly: ```python squares = [x * x for x in range(6)] even_squares = [x * x for x in range(10) if x % 2 == 0] ``` They should remain readable. A complex comprehension containing several conditions and transformations is often better replaced by a named function or a conventional loop. Indexing a list is generally constant-time, O(1), because Python can calculate the location of a positional element. Inserting or deleting near the beginning is generally O(n), because later elements must be shifted. Membership testing with `in` is also generally O(n). Consequently, lists are excellent for ordered batches and poor as large membership indexes. Lists may contain objects of different types, but consistency is usually preferable in numerical and ML pipelines. A Python list of floating-point objects has more object and reference overhead than a compact numerical array. Libraries such as NumPy are designed for dense numerical data and vectorized computation; Python lists remain valuable for orchestration, irregular records, and heterogeneous metadata. Tuples and the Meaning of ImmutabilityTuples are ordered, immutable sequences. They are useful for fixed records, multiple return values, coordinates, and composite keys. Their immutability communicates that the sequence structure should not change. ```python point = (12.5, 8.0) mean, deviation = (4.2, 0.7) ``` Tuple unpacking assigns elements to names and can make code expressive. The starred target collects remaining elements: ```python first, *middle, last = [1, 2, 3, 4, 5] ``` Immutability is shallow in the structural sense. A tuple cannot replace one of its positions, but it may contain a mutable object: ```python record = ("case-1", [0.4, 0.9]) record[1].append(1.0) # permitted ``` The tuple still contains the same list object; the list itself changed. This matters when tuples are used as apparently stable configuration records. A tuple can be used as a dictionary key only if all its elements are hashable. A tuple containing a list cannot be hashed. This illustrates that hashability depends on the complete structure, not simply on the outer type. Sets: Uniqueness and MembershipA set is an unordered collection of unique hashable elements. It supports efficient average-case membership testing and mathematical operations such as union, intersection, difference, and symmetric difference. ```python training_labels = {"cat", "dog", "bird"} new_labels = {"dog", "horse"} training_labels | new_labels # union training_labels & new_labels # intersection training_labels - new_labels # difference ``` Sets are especially useful for removing duplicates and testing whether an item belongs to a vocabulary, permission group, or accepted-label set. They do not preserve duplicates, and they should not be used when positional order is semantically meaningful. The empty set is written as `set()`, not `{}`, because `{}` creates an empty dictionary. Set elements must be hashable. Lists, dictionaries, and ordinary sets cannot be elements because they are mutable and therefore unsuitable for stable hashing. A `frozenset` is an immutable, hashable set-like object and can itself be used as a dictionary key or as a member of another set. Set operations are often more efficient than repeated list membership tests. However, sets use hash tables and may consume more memory than lists for the same number of elements. The appropriate choice depends on the operation being optimized and the scale of the data. Dictionaries: Associating Keys with ValuesA dictionary maps hashable keys to values. It is the principal structure for named data, lookup tables, counters, configuration, and sparse representations. ```python sample = { "id": "A17", "features": [0.2, 0.9, 0.1], "label": "approved" } print(sample["label"]) ``` Dictionary lookup, insertion, and deletion are average-case O(1), although pathological cases and resizing should be recognized in theoretical analysis. Keys must be hashable and obey the rule that equal keys have equal hashes. Values may be any object. Use `get` when a missing key is an expected possibility: ```python score = sample.get("confidence", 0.0) ``` The expression `sample["confidence"]` raises `KeyError` if the key is absent. That exception may be appropriate when absence indicates malformed input; silently supplying a default may conceal a data-quality problem. Modern Python dictionaries preserve insertion order as a language guarantee. This does not transform a dictionary into a sequence: access remains key-based, and code should not use incidental order when the domain requires an explicit ordering policy. The methods `keys()`, `values()`, and `items()` return dynamic view objects. They reflect later dictionary changes rather than being independent lists. Dictionary comprehensions support transformation: ```python frequencies = {word: tokens.count(word) for word in set(tokens)} ``` For large data, repeatedly calling `count` can be inefficient; `collections.Counter` is usually preferable. Ranges and Lazy Regular SequencesA `range` represents an arithmetic progression without storing every integer as a separate element. Its form is `range(start, stop, step)`, with `stop` excluded. ```python indices = range(2, 10, 2) list(indices) # [2, 4, 6, 8] ``` Ranges are iterable, support indexing and membership testing, and are memory-efficient even when they describe a large progression. They are particularly useful for loop indices, batch positions, and train-validation partitions. A range is not a list: it is a compact object describing a sequence. Converting it to a list materializes all values and may defeat its memory advantage. A zero step is invalid, and a range with a positive step may be empty when its start is not below its stop. Explicitly checking boundaries is important in batch-generation code. Specialised Collections for Practical WorkThe `collections` module provides structures that express common patterns more directly than general-purpose dictionaries and lists. `Counter` counts hashable objects: ```python from collections import Counter counts = Counter(["spam", "ham", "spam"]) counts.most_common(1) # [('spam', 2)] ``` It is useful for class distributions, token frequencies, and error categories. Class imbalance analysis should distinguish raw frequency from the sampling strategy used later. `defaultdict` creates a default value when a missing key is accessed: ```python from collections import defaultdict inverted = defaultdict(list) inverted["model"].append("document_1") ``` This is convenient for grouping and inverted indexes. It can, however, create keys as a side effect of reading them, so ordinary dictionaries with `get` may be safer when accidental insertion is undesirable. `deque` supports efficient insertion and removal at both ends: ```python from collections import deque queue = deque(["job1", "job2"]) queue.append("job3") next_job = queue.popleft() ``` A list is efficient for operations at its right end, but a deque is more suitable for queues, sliding windows, and breadth-first traversal. `namedtuple` supplies tuple-like records with named fields, although `dataclass` is often more flexible for modern application models. Hashing, Equality, and Collection SemanticsHashing converts an object into an integer used by hash-table structures such as dictionaries and sets. A hashable object has a hash value that remains stable during its lifetime and can be compared for equality. Immutable built-in types such as strings, numbers, and suitable tuples are commonly hashable. The essential relationship is: ```text if a == b, then hash(a) == hash(b) ``` The reverse is not guaranteed: different objects may share a hash value. Python resolves such collisions internally. Hash randomization also means that hash-related details should not be treated as a portable ordering mechanism across processes. Using a mutable object as a key would be dangerous if its equality-relevant contents changed after insertion. Python therefore makes lists and dictionaries unhashable. A custom class can be hashable only when its equality and hashing behavior remain logically consistent. Copying, Slicing, and Memory ImplicationsA shallow copy creates a new outer container but does not recursively copy contained objects. Common shallow-copy techniques include `list(original)`, `original[:]`, `dict(original)`, and `copy.copy(original)`. ```python rows = [[1, 2], [3, 4]] copy_rows = rows[:] copy_rows[0].append(99) print(rows) # [[1, 2, 99], [3, 4]] ``` The outer lists differ, but their inner lists are shared. A deep copy recursively copies reachable objects: ```python import copy independent_rows = copy.deepcopy(rows) ``` Deep copying is not universally appropriate. It can be expensive, may copy more state than intended, and may not work meaningfully for external resources or custom objects. In ML systems, explicit reconstruction of the required data or immutable representations is often clearer than indiscriminate deep copying. The multiplication trap is another form of aliasing: ```python matrix = [[0] 3] 2 matrix[0][0] = 1 print(matrix) # [[1, 0, 0], [1, 0, 0]] ``` Both rows refer to the same inner list. Use a comprehension to create independent rows: ```python matrix = [[0] * 3 for _ in range(2)] ``` Memory analysis must consider both container overhead and referenced objects. A list stores references, not compact values in the same sense as a typed numerical array. Dictionaries and sets require hash tables with unused capacity to support efficient operations. Generators and ranges can represent regular or streamed data without materializing an entire collection, but they are single-use or computation-oriented abstractions rather than random-access containers. Choosing Structures by Operation and MeaningA sound design begins with the question: what operations and invariants does the application require? | Requirement | Suitable structure | Reason | |---|---|---| | Ordered, changeable sequence | `list` | Indexing and flexible updates | | Fixed positional record | `tuple` | Structural immutability and unpacking | | Unique membership values | `set` | Deduplication and fast average lookup | | Key-based association | `dict` | Named or indexed retrieval | | Large arithmetic progression | `range` | Compact lazy representation | | Frequency counting | `Counter` | Direct counting operations | | Queue or double-ended window | `deque` | Efficient operations at both ends | | Grouping by key | `defaultdict` | Convenient accumulation | This table is a starting point, not a substitute for profiling. A list may be preferable to a set when preserving order and minimizing memory are more important than membership speed. A dictionary may be less appropriate than a database or columnar data structure when the dataset exceeds process memory. In numerical ML workloads, NumPy arrays, pandas objects, sparse matrices, tensors, and database tables may be more suitable than built-in collections for the core data plane, while Python collections remain central for metadata and control logic. Applications in AI and Machine LearningCollections appear throughout an ML workflow. A tokenizer may return a list of strings; a vocabulary is naturally represented as a dictionary from token to integer ID; a set can store reserved tokens; a tuple can represent a fixed shape; and a `Counter` can summarize label imbalance. For example: ```python from collections import Counter documents = ["red blue", "blue green", "red red"] tokens = [token for document in documents for token in document.split()] vocabulary = {token: index for index, token in enumerate(sorted(set(tokens)))} frequencies = Counter(tokens) ``` Sorting before enumeration makes the vocabulary assignment reproducible. Without an explicit ordering policy, relying on set traversal can make IDs difficult to reproduce across environments. Reproducibility is a technical and governance concern: changing IDs can invalidate cached features, model artifacts, or evaluation comparisons. Dictionaries also represent sparse feature vectors: ```python sparse_vector = {3: 1.0, 17: 2.5, 104: 1.0} ``` Only nonzero features are stored, saving space when the feature dimension is large and observations are sparse. For very large collections, specialized sparse matrix formats are generally more efficient. Applied Case: Designing a Text Classification Record PipelineBackgroundConsider an illustrative case involving a university support service that classifies incoming student messages into categories such as `fees`, `registration`, and `technical`. The service needs to clean text, maintain a vocabulary, preserve message metadata, and calculate category frequencies. Situation and ProblemAn initial prototype stores every message as a list and checks whether each token belongs to a list of vocabulary terms. It also copies batches using assignment before applying text-cleaning operations. As the number of messages grows, membership checks become slow, and cleaning one batch unexpectedly changes the archived records. AnalysisThe prototype has two conceptual errors. First, vocabulary membership is a set operation, not an ordered-list operation. The vocabulary-to-ID mapping additionally requires a dictionary. Second, assignment creates an alias rather than a copy. If nested message records are mutable, a shallow copy may still share token lists. Approach and SolutionA better design separates concerns: ```python from collections import Counter import copy records = [ {"id": "m1", "text": "Help with fees", "label": "fees"}, {"id": "m2", "text": "Portal login problem", "label": "technical"} ] cleaned = copy.deepcopy(records) for record in cleaned: record["tokens"] = record["text"].lower().split() vocabulary_set = { token for record in cleaned for token in record["tokens"] } vocabulary = { token: index for index, token in enumerate(sorted(vocabulary_set)) } label_counts = Counter(record["label"] for record in cleaned) ``` The set expresses uniqueness and supports membership tests. The sorted dictionary assignment establishes reproducible token IDs. The deep copy ensures that nested changes do not alter the archived records in this illustrative design. In a production system, an explicit transformed-record construction may be preferable to deep copying, especially when records contain large or non-copyable objects. OutcomeThe revised design makes the data model clearer, prevents accidental mutation of the archive, and provides efficient vocabulary lookup and label counting. It also makes later validation easier because each representation has a defined role. Learning PointsThe case demonstrates that collection choice is a semantic decision. It also shows that performance and correctness are connected: a data structure that expresses the intended invariant—uniqueness, association, or immutability—reduces both computational waste and programming errors. Common Errors, Risks, and Professional ConsiderationsA frequent error is modifying a collection while iterating over it. This can skip elements or produce confusing behavior. Iterate over a copy or construct a new collection when filtering. Another error is using a mutable default argument such as `def add_item(item, items=[]):`; the same list is reused across calls. Use `None` as the default and create a list inside the function. Dictionary keys should be validated when data comes from external sources. Unexpected keys, missing fields, and inconsistent types can corrupt feature pipelines. Sets and dictionaries should not be treated as secure storage, and collection representations may contain personally identifiable or sensitive information. Logs, serialized objects, and caches require access control, retention policies, and appropriate minimization. Data leakage can arise when a shared mutable collection is modified across training and validation stages. Defensive copying, immutable configuration, clear ownership, and pipeline boundaries help reduce this risk. Pickle-based serialization should not be used to load untrusted data because deserialization can execute arbitrary code. Safe, validated formats and explicit schemas are preferable for exchanged artifacts. Emerging Directions and Best PracticesContemporary Python data systems increasingly combine built-in collections with typed models, dataclasses, validation libraries, array libraries, data frames, tensors, and distributed data abstractions. The trend is not to replace built-ins but to use them at the appropriate layer: dictionaries for metadata, arrays for dense numerical blocks, sparse structures for sparse features, and streaming iterators for data that should not be materialized. Effective practice includes: - Choose a collection according to required operations and domain invariants.
- Use `is` only for identity tests, such as checking against `None`; use `==` for value comparison.
- Make ordering explicit when IDs, reports, or model artifacts must be reproducible.
- Avoid unnecessary copies, but copy deliberately when ownership or isolation requires it.
- Profile time and memory on representative workloads rather than relying only on intuition.
- Prefer clear transformations and validated schemas over clever, opaque collection manipulations.
- Keep sensitive data out of diagnostic representations and logs.
Chapter SummaryPython collections provide distinct semantic and computational tools. Strings are immutable Unicode sequences; lists are mutable ordered sequences; tuples provide immutable sequence structure; sets represent unique hashable values; dictionaries associate hashable keys with values; and ranges compactly represent arithmetic progressions. Specialised collections such as `Counter`, `defaultdict`, and `deque` express counting, grouping, and queue operations directly. Indexing and slicing support sequence manipulation, but slices are generally shallow with respect to nested objects. Hashability enables dictionary and set membership and depends on stable equality-related state. Assignment creates aliases, shallow copies duplicate only an outer container, and deep copies recursively duplicate reachable objects at potentially significant cost. In AI and ML, careful collection design supports tokenization, vocabulary construction, sparse features, batching, metadata management, and reproducibility. The best structure is determined by meaning, operations, scale, memory, and professional requirements such as data isolation and security. Key TermsHashability: The property of having a stable hash value and equality behavior suitable for use in sets or as dictionary keys. Immutability: The inability to change an object’s contents after creation. Mutability: The ability to alter an object in place. Aliasing: The condition in which multiple names refer to the same object. Indexing: Accessing an element by its positional or key-based location. Slicing: Creating a subsequence using start, stop, and step boundaries. Shallow copy: A copy of an outer container that retains references to contained objects. Deep copy: A recursive copy that attempts to duplicate nested objects. Dictionary: A mapping from hashable keys to values. Set: An unordered collection of unique hashable elements. Tuple: An immutable ordered sequence. List: A mutable ordered sequence. Range: A compact representation of an arithmetic progression. Counter: A specialised mapping for counting hashable objects. Deque: A double-ended queue supporting efficient operations at both ends. View object: A dynamic dictionary view reflecting keys, values, or items. Comprehension: A compact syntax for constructing a collection from an iterable. Membership testing: Determining whether an element occurs in a collection. Reproducibility: The ability to obtain consistent computational results under controlled conditions. Review QuestionsShort Answer Questions1. How do `is` and `==` differ in Python? 2. Why can a tuple containing a list not normally be used as a dictionary key? 3. What is the difference between `append` and `extend` for lists? 4. Why is `range` generally more memory-efficient than an equivalent list? 5. What problem does `Counter` solve? Long Answer Questions1. Compare lists, tuples, sets, and dictionaries in terms of ordering, mutability, admissible elements, and typical applications. 2. Explain Python hashing and its relationship to equality, using examples involving dictionary keys and set members. 3. Discuss shallow and deep copying, including the nested-list multiplication trap and implications for ML pipelines. 4. Explain how strings, sets, dictionaries, and specialised collections can be combined to construct a reproducible text vocabulary. 5. Analyse the time and memory trade-offs involved in choosing a list, set, dictionary, or specialised collection. Analytical / Application Questions1. A developer stores a vocabulary as a list and repeatedly checks whether incoming tokens are present. Recommend a revised design and justify it using operations, complexity, and reproducibility. 2. A training batch is copied with assignment, then preprocessing changes the archived dataset. Diagnose the cause and propose two technically sound remedies. 3. Design suitable Python collection types for a system that requires a FIFO job queue, class-frequency statistics, a fixed image shape, and a mapping from feature names to IDs. Explain each choice. 22. Multiple Choice Questions with AnswersQuestion 1Which statement correctly describes the result of assigning one list variable to another? A. A deep copy of the list is always created B. Both names refer to the same list object C. Only immutable elements are copied D. The second variable becomes a tuple Correct Answer: B. Both names refer to the same list object Question 2Which structure is most appropriate for testing membership among a large collection of unique labels? A. A set B. A tuple C. A range D. A string Correct Answer: A. A set Question 3What does `values[1:4]` select from a sequence? A. Elements at positions 1, 2, 3, and 4 B. Only the element at position 4 C. Elements at positions 1, 2, and 3 D. Elements at positions 0, 1, 2, and 3 Correct Answer: C. Elements at positions 1, 2, and 3 Question 4Why does `matrix = [[0] 3] 2` create a potential problem? A. It creates tuples instead of lists B. Both rows refer to the same inner list C. It cannot contain integer values D. It reverses the row order Correct Answer: B. Both rows refer to the same inner list Question 5Which object can be used as a dictionary key, assuming its contents are as shown? A. [1, 2] B. {1, 2} C. {'a': 1} D. (1, 2) Correct Answer: D. (1, 2) Question 6What is the principal advantage of `range(0, 1000000)` over `list(range(0, 1000000))`? A. It stores the entire sequence as text B. It represents the progression compactly without materializing every value C. It permits arbitrary string keys D. It automatically sorts values Correct Answer: B. It represents the progression compactly without materializing every value Question 7Which specialised collection is most directly suited to counting class labels? A. Counter B. deque C. defaultdict(list) D. range Correct Answer: A. Counter Question 8What does `dict.get('confidence', 0.0)` do when the key is absent? A. Raises a TypeError B. Deletes the dictionary C. Returns 0.0 without requiring the key to exist D. Adds a random confidence value Correct Answer: C. Returns 0.0 without requiring the key to exist Question 9A tuple contains a list, and the list is appended to. Which statement is correct? A. The tuple’s position is replaced automatically B. The operation is impossible because tuples are immutable C. The contained list may change even though the tuple structure does not D. All references to the list are converted to tuples Correct Answer: C. The contained list may change even though the tuple structure does not Question 10Why should vocabulary IDs often be assigned after sorting a set of tokens? A. Sorting makes tokens mutable B. Sorting establishes an explicit and reproducible order C. Sorting changes all tokens into integers automatically D. Sorting removes the need for a dictionary Correct Answer: B. Sorting establishes an explicit and reproducible order
|
