Sorting Dictionary Results
Dictionaries outperform lists and variables for character counting because they only allocate space for characters that actually appear, not for every possible character.
Why Counts Need a Data Structure
Suppose you need to analyze a word and determine which letters appear most often. For the word brontosaurus, the letters r, o, s, and u each appear twice, while b, n, t, and a appear once. This is a frequency count. The collection of counters is called a histogram.
The difficult part is not only counting. You also need to choose how to store the counts. Three main approaches are possible: use separate variables, use a list, or use a dictionary. The first two require you to decide in advance which characters might appear. A dictionary adapts as the input is processed.
A dictionary-based frequency table contains one key for each character that actually appears and stores that character's count as the associated value.
Tracing brontosaurus
What do you think happens?
What will the dictionary contain after every character in brontosaurus has been processed?
Reveal answer
Answer: {'b': 1, 'r': 2, 'o': 2, 'n': 1, 't': 1, 's': 2, 'a': 1, 'u': 2}
Each first occurrence creates a dictionary entry with count 1. Each later occurrence increments the existing count. The word has 12 characters but only 8 unique letters.
The important transition occurs when the second o is read. The dictionary already has o with value 1, so the program does not create another o entry. It changes the existing value to 2. The same update happens when later occurrences of r, u, and s are encountered.
The New-or-Existing Decision
Every character follows one of two paths. If the character is not already a key in the dictionary, the program adds it with a count of 1. If the character is already a key, the program increments its current count. The conditional check if c not in d expresses this decision.
{'b': 1, 'r': 2, 'o': 2, 'n': 1, 't': 1, 's': 2, 'a': 1, 'u': 2}Choosing Among Three Approaches
| Approach | What it requires | Main limitation | Adaptability |
|---|---|---|---|
| Separate variables | Advance decisions about which characters may appear | The code must account for the chosen characters individually | Low when the possible input changes |
| List | Advance knowledge of the character range and numeric codes | Space is reserved for the range, including characters that may not appear | Useful when the counted range is known |
| Dictionary | A key for each character that appears | The approach stores frequency information in key-value entries | High because it grows as new characters arrive |
A list can work when you know that you are counting only English letters and are willing to convert characters to indices with ord(). However, that approach requires knowledge of the possible character range and its numeric codes. A dictionary does not require that advance decision. It can count digits, punctuation, or Unicode symbols by creating entries for the characters that arrive.
Mistakes in Frequency Counting
Incrementing a dictionary value before creating the key
A character may be appearing for the first time, so there is no existing count to increment.
Fix:
Check whether the character is a key. Create it with count 1 when it is new; otherwise increment its existing count.Creating a new entry every time a character appears
Repeated occurrences must update the existing counter so that one key records the total frequency.
Fix:
When the key already exists, increment its value rather than creating another entry.Assuming the input character set in advance
The fixed approach requires knowledge of the complete possible range and does not adapt automatically to other characters.
Fix:
Use a dictionary when the possible characters are unknown or broader than the chosen fixed range.
Practice the State Changes
Trace the dictionary for the input "banana". Write the dictionary after each character is processed. Identify the first character that causes an existing value to be incremented rather than a new key being created.
Hints
- Begin with an empty dictionary.
- The first occurrence of a character creates a key with count 1.
- The second occurrence of a character increments the value already stored for that key.
A Short Trace
Determine the final frequency table for the input "cocoa".
Read c: c is new, so create the key c with count 1.
Read o: o is new, so create the key o with count 1.
Read c again: c already exists with count 1, so increment it to 2.
Read o again: o already exists with count 1, so increment it to 2.
Read a: a is new, so create the key a with count 1.
{'c': 2, 'o': 2, 'a': 1}
The reusable pattern is: check whether the key exists, then either create the counter or update the existing value. This pattern is useful for frequency tables, tallies, and histograms.
Key Takeaways
- Character 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 creates entries only for characters that actually occur.
- The if c not in d pattern creates a count for a new key and increments the count for an existing key.
- The completed dictionary is a histogram: a collection of counters containing the frequency information.
Key Takeaways
- A dictionary is well suited to frequency counting because it stores only characters that actually appear.
- The counting algorithm has two paths: create a new key with count 1 or increment an existing value.
- A list can work for a known character range, but a dictionary adapts more easily to unknown characters, digits, punctuation, and Unicode symbols.
- The resulting dictionary is a histogram because it contains the counters for every observed character.