Building Histograms from Data
Character counting uses a dictionary to store each unique character and its count.
Why Counts Need a Dictionary
Suppose you have the word brontosaurus and want to know how many times each letter appears. Counting by hand is possible, but a dictionary can keep one count for every unique character while a loop examines the word. Each character becomes a key, and its count becomes the value associated with that key.
The central decision is simple: if the character is new, create its dictionary entry with the count 1. If the character is already present, increase its existing count by 1.
The First Counting Method
The conditional approach explicitly checks whether the current character is already a key in dictionary d. When c is not in d, the program assigns d[c] = 1 because this is the first occurrence. When c is already in d, the program assigns d[c] = d[c] + 1 because the character has appeared again.
d = {} for c in "brontosaurus": if c not in d: d[c] = 1 else: d[c] = d[c] + 1
A Character-by-Character Trace
The dictionary begins empty. Processing the first character, b, creates the entry b: 1. The next character, r, is new, so r: 1 is added. When the loop reaches another character that is already present, the program does not create a second key; it increments the value attached to the existing key.
| Character processed | Reason | Dictionary after processing |
|---|---|---|
| b | b is new, so initialize its count | {b: 1} |
| r | r is new, so initialize its count | {b: 1, r: 1} |
| o | o is new, so initialize its count | {b: 1, r: 1, o: 1} |
| n | n is new, so initialize its count | {b: 1, r: 1, o: 1, n: 1} |
| t | t is new, so initialize its count | {b: 1, r: 1, o: 1, n: 1, t: 1} |
| o | o already exists, so increment its count | {b: 1, r: 1, o: 2, n: 1, t: 1} |
State trace for the first six characters of brontosaurus
What do you think happens?
After processing b, r, o, n, t, and o from brontosaurus, what should the count for o be?
Reveal answer
Answer: 2
The first o creates the entry with count 1. The later o finds that existing entry and increments it to 2.
The Concise get Method
The dictionary get method combines the two conditional cases. The expression d.get(c, 0) returns the current count when c is already a key. If c is not a key, it returns the supplied default value 0. Adding 1 and storing the result in d[c] therefore initializes a new character to 1 or increments an existing count.
Reading d.get(c, 0) + 1
Explain what happens when the current character is new and when it has already been counted.
New character: If c is not in d, d.get(c, 0) returns 0. Adding 1 gives 1, which is stored as d[c].
Existing character: If c is already in d, d.get(c, 0) returns its current count. Adding 1 increases that count, and the new value is stored as d[c].
Same final behavior: Both cases update the dictionary with the correct count for the current character.
The get method handles initialization and incrementing in one expression.
Choosing a Clear Approach
| Approach | How it handles a new character | How it handles an existing character | Main characteristic |
|---|---|---|---|
| Conditional | Sets d[c] to 1 | Adds 1 to d[c] | More explicit and easier for beginners to follow |
| get method | Uses default 0, then adds 1 | Retrieves the current count, then adds 1 | More concise and widely used in practice |
Initializing an existing character instead of incrementing it
The dictionary must preserve the earlier count so repeated characters accumulate.
Fix:
Check whether the key exists and increment d[o], or use d[o] = d.get(o, 0) + 1.Incrementing a character before giving it an initial count
A new character has no existing count to increase in the conditional approach.
Fix:
Initialize a new key to 1, or let get supply 0 before adding 1.Assuming the two approaches produce different results
Both handle a missing key as a count of 0 before the current occurrence is added.
Fix:
Compare the final dictionaries: the approaches produce identical results.
Practice the State Change
Trace the conditional approach for the first five characters of brontosaurus. Write the dictionary after each character is processed, and identify which character causes an increment rather than an initialization.
Hints
- Begin with an empty dictionary.
- The first occurrence of a character creates a count of 1.
- The repeated character among the first five characters determines whether an increment occurs.
Rewrite the conditional counting logic as the single get-method assignment d[c] = d.get(c, 0) + 1. Then explain why the default value must be 0 rather than 1.
Hints
- The default represents the count before the current character is added.
- Adding 1 to the default should produce the first occurrence count.
Key Takeaways
- A dictionary stores each unique character as a key and its count as the associated value.
- The conditional approach initializes a new character to 1 and increments an existing character by 1.
- The get method uses a default value of 0 so one expression can handle both new and existing characters.
- The conditional and get approaches produce identical results.
- Tracing the dictionary after every character makes initialization and incrementing visible.
Key Takeaways
- Character counting uses a dictionary to map each unique character to its count.
- A character is initialized with count 1 the first time it appears.
- A character's existing count is incremented each time it appears again.
- The conditional approach and d[c] = d.get(c, 0) + 1 are equivalent.
- Tracing dictionary state one character at a time reveals exactly how the histogram is built.