Introduction to Dictionaries
Dictionaries outperform lists and variables for character counting because they only allocate space for characters that actually appear, not for every possible character.
The Counting Challenge
Suppose you want to discover which letters appear most frequently in the word brontosaurus. The result should record that r, o, s, and u each appear twice, while b, n, t, and a each appear once. This task is called frequency counting. The collection of counters that records these frequencies is called a histogram.
The difficult part is not adding one to a counter. The important design decision is how to store the counters. You can use separate variables, a list, or a dictionary. All three approaches can solve the same counting problem, but they differ in how much you must know before processing the input and how much unused space they reserve.
Why Dictionaries Adapt
The first two approaches require you to decide in advance which characters might appear. For example, a design using 26 variables or a 26-element list reserves room for every letter of the alphabet, including letters that never occur in the input. A dictionary takes a different approach: it creates an entry only when a character actually appears.
This matters when the possible input is not limited to English letters. A string might include digits, punctuation, or Unicode symbols. A list-based design requires you to know the possible character range and how to map each character to a numeric position. A dictionary can use the arriving character as a key, so the counting pattern does not need a new variable or a preallocated position for every possible character.
The Two-Branch Counting Rule
The dictionary algorithm has one decision point. For each character c, check whether c is already a key in the dictionary d. If it is not present, create the key and give it the value 1. If it is already present, increment its existing value. The pattern is commonly written as if c not in d.
d = {} for c in "brontosaurus": if c not in d: d[c] = 1 else: d[c] = d[c] + 1 print(d)
What do you think happens?
What dictionary will the loop contain after it processes the entire word brontosaurus?
Reveal answer
Answer: A dictionary with one entry for each distinct character and its frequency
The dictionary creates a key the first time a character appears and increments that key on later encounters. The completed histogram is {'b': 1, 'r': 2, 'o': 2, 'n': 1, 't': 1, 's': 2, 'a': 1, 'u': 2}.
Reading the State Changes
The word brontosaurus contains 12 characters but only 8 unique letters. On a first encounter, the dictionary gains a new key with value 1. On a later encounter, no new key is needed; the value belonging to the existing key increases.
| Character read | Decision | Dictionary state |
|---|---|---|
| b | New key, so initialize b to 1 | {'b': 1} |
| r | New key, so initialize r to 1 | {'b': 1, 'r': 1} |
| o | New key, so initialize o to 1 | {'b': 1, 'r': 1, 'o': 1} |
| r | Existing key, so increase r to 2 | {'b': 1, 'r': 2, 'o': 1} |
| o | Existing key, so increase o to 2 | {'b': 1, 'r': 2, 'o': 2} |
| n | New key, so initialize n to 1 | {'b': 1, 'r': 2, 'o': 2, 'n': 1} |
The first six processed characters show both branches of the counting rule.
Choosing the Flexible Structure
| Approach | What must be known first | How it stores counts | Main trade-off |
|---|---|---|---|
| Separate variables | The characters to count | A different counter for each planned character | Works for a fixed known set, but does not adapt naturally to unexpected characters |
| List | The character range and a mapping to positions | A counter at a position for each planned character | Can work for English letters, but reserves positions for letters that may not appear |
| Dictionary | No complete character set | A key for each character that appears and a value for its frequency | Adapts to letters, digits, punctuation, and Unicode symbols while storing only observed entries |
A list can be a reasonable choice when you know that the input contains only English letters and you are willing to convert characters to list positions with ord(). However, that approach depends on the known character range. The dictionary pattern keeps the same counting logic when the input later changes to words, multiple languages, digits, punctuation, or other symbols.
Mistakes in Frequency Counting
Treating every character as new
Repeated characters should increase the value of the existing key rather than create another count for the same character.
Fix:
Check if c not in d. Initialize a new key only when the character is absent; otherwise increment d[c].Preallocating a fixed set when the input is broader
The design requires you to know the full range of possible characters and their positions in advance.
Fix:
Use the character itself as a dictionary key so the dictionary can create entries as new characters appear.Confusing a histogram with a graph only
In computing, a histogram can simply be a collection of counters.
Fix:
Recognize the dictionary of keys and frequency values as the histogram, even when it is printed as key-value pairs.
Practice the State Trace
Trace the dictionary while processing the string "level". Write the dictionary after each character is read. Then identify which characters were initialized and which characters were incremented.
Hints
- Start with an empty dictionary.
- The first l, e, and v are new characters.
- The second e and the second l use the existing-key branch.
Tracing level
Determine the dictionary state after each character in the string level.
Read l: l is new, so create the entry l: 1.
Read e: e is new, so create the entry e: 1.
Read v: v is new, so create the entry v: 1.
Read e again: e already exists with value 1, so increase it to 2.
Read l again: l already exists with value 1, so increase it to 2.
{'l': 2, 'e': 2, 'v': 1}
Key Takeaways
- Character frequency counting can use separate variables, a list, or a dictionary.
- Variables and lists require more advance knowledge about the characters that may appear; a dictionary adapts as characters arrive.
- The central dictionary pattern is: if a character is new, initialize its count to 1; otherwise increment its existing count.
- A dictionary histogram stores each observed character as a key and its frequency as the corresponding value.
- Dictionaries are especially useful when the input may include unexpected characters or when storing entries only for observed characters is preferable.
Key Takeaways
- A dictionary represents a frequency table with character keys and count values.
- The if c not in d pattern distinguishes first encounters from repeated encounters.
- Dictionaries store entries only for characters that actually appear, unlike a fixed collection of variables or positions.
- The same approach can adapt to letters, digits, punctuation, Unicode symbols, words, and other frequency-counting tasks.