Conditional Logic with Dictionaries
Dictionaries outperform lists and variables for character counting because they only allocate space for characters that actually appear, not for every possible character.
From Characters to Counts
Suppose you need to discover which letters appear most often in the word brontosaurus. The result should record that r, o, s, and u each appear twice, while b, n, t, and a appear once. This task is called frequency counting. The collection of counters is called a histogram: in this case, the dictionary itself contains the frequency information.
The main challenge is not only increasing a count. It is choosing a data structure that can hold the counts without forcing you to predict every possible character in advance. Three approaches can solve the problem: separate variables, a list with positions for characters, or a dictionary whose keys are the characters that actually appear.
| Approach | How a count is stored | Main limitation |
|---|---|---|
| Variables | A separate variable for each known character | The possible characters must be decided in advance |
| List | A count at a position associated with each character | The character range and position mapping must be decided in advance |
| Dictionary | A key-value pair for each character encountered | The program uses conditional logic to create or update entries |
Following the Dictionary
The trace shows two different kinds of update. When a character appears for the first time, the dictionary receives a new key with value 1. When a character appears again, no new key is needed; its existing value increases. The word has 12 characters but only 8 unique letters, so the final dictionary has 8 entries.
The Conditional Update
The central decision is whether the current character is already a key in the dictionary. The pattern if c not in d separates the two cases. A new character is initialized with count 1. An existing character has its count incremented. This check-then-create-or-update pattern is a foundational technique for frequency tables, tallies, and histograms.
text = "brontosaurus" counts = {} for c in text: if c not in counts: counts[c] = 1 else: counts[c] += 1 print(counts)
{'b': 1, 'r': 2, 'o': 2, 'n': 1, 't': 1, 's': 2, 'a': 1, 'u': 2}Storage That Follows the Input
A dictionary allocates entries only for characters that actually appear. For brontosaurus, the dictionary needs entries for 8 unique letters, not for every letter that could have appeared. A 26-variable or 26-element-list design reserves room for every English letter, including letters absent from the word.
When the Choice Matters
Selecting a Counting Structure
Choose a suitable approach for counting characters in text that may include letters, digits, punctuation, and Unicode symbols.
Consider variables: Separate variables require the possible characters to be decided in advance, so they do not adapt naturally to an unknown range.
Consider a list: A list requires a known character range and a mapping from each character to a numeric position. This can work when the input is restricted to English letters, but it is less flexible for broader input.
Consider a dictionary: A dictionary creates a key when a character appears and updates that key when the character appears again. It does not require the full set of possible characters to be known beforehand.
Use the dictionary approach because the input can contain characters outside a fixed, predeclared range.
The dictionary pattern also transfers to other frequency problems. The same create-or-update idea can count words instead of characters, analyze text in multiple languages, or track another kind of frequency without changing the basic pattern. By contrast, a list solution may require a new character range, mapping, or rewrite when the input changes.
Mistakes in the Decision
Incrementing a key before creating it
A character appearing for the first time has no existing count to increment.
Fix:
Check whether c is already in the dictionary. Initialize counts[c] to 1 when it is new; increment it otherwise.Assuming the dictionary must contain every possible character
The dictionary approach creates entries only for characters that actually appear.
Fix:
Interpret each key-value pair as an observed character and its frequency.Using a fixed list when the input range is unknown
A list requires the possible character range and its numeric mapping to be known in advance.
Fix:
Use dictionary keys when the input may contain characters outside a fixed range.Treating the dictionary as something separate from the histogram
In computing, the dictionary of counters is itself the histogram.
Fix:
Read each key-value pair as one item and its frequency.
Check Your Trace
Trace the dictionary for the input string "level". Write the dictionary after each character is processed, then identify the final count for l, e, and v.
Hints
- Start with an empty dictionary.
- The first occurrence of a character creates a key with value 1.
- The second occurrence of an existing character increments its value.
What do you think happens?
After processing the input "level", what dictionary should the counter contain?
Reveal answer
Answer: {'l': 2, 'e': 2, 'v': 1}
The first l, e, and v create entries with count 1. The second e increments e to 2, and the final l increments l to 2. v appears only once.
Key Takeaways
- Frequency counting records how often each character appears; the collection of counters is a histogram.
- The dictionary algorithm checks whether the current character is already a key, then either initializes its count to 1 or increments the existing count.
- Dictionaries store entries only for characters that actually appear, rather than reserving space for every possible character.
- Dictionaries adapt to digits, punctuation, Unicode symbols, words, and other inputs without requiring a fixed character range in advance.
- The key design pattern is check, create when new, and update when existing.
Key Takeaways
- A dictionary-based counter handles unknown characters by making each encountered character a key.
- New characters receive count 1, while existing characters have their counts incremented.
- The dictionary itself is the histogram: its key-value pairs contain all frequency information.
- Compared with fixed variables or a list, a dictionary stores only observed characters and adapts more easily to varied input.