Sorting Dictionary Results

A dictionary-based frequency table contains one key for each character that actually appears and stores that character's count as the associated value.

Programming

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.

Key point

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.

How does the dictionary change after each character is read, including when a character is first added and when its count is incremented?

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.

What control-flow path does the program follow when the current character is already a key versus when it is not?

python

text = "brontosaurus"
counts = {}

for c in text:
    if c not in counts:
        counts[c] = 1
    else:
        counts[c] += 1

print(counts)

text = "brontosaurus"
counts = {}

for c in text:
    if c not in counts:
        counts[c] = 1
    else:
        counts[c] += 1

print(counts)

Output

{'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

The three approaches solve the same counting problem but differ in how they handle unknown input.

How do variables, lists, and dictionaries differ when storing character frequencies?

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

Common mistake
Incrementing a dictionary value before creating the key
What it looks like
Treating every character as though it already exists in the dictionary
Why it fails
A character may be appearing for the first time, so there is no existing count to increment.
Do this instead
Check whether the character is a key. Create it with count 1 when it is new; otherwise increment its existing count.
Common mistake
Creating a new entry every time a character appears
What it looks like
Adding another separate entry when the second o in brontosaurus is processed
Why it fails
Repeated occurrences must update the existing counter so that one key records the total frequency.
Do this instead
When the key already exists, increment its value rather than creating another entry.
Common mistake
Assuming the input character set in advance
What it looks like
Designing a fixed collection only for English letters when the input may contain digits, punctuation, or Unicode symbols
Why it fails
The fixed approach requires knowledge of the complete possible range and does not adapt automatically to other characters.
Do this instead
Use a dictionary when the possible characters are unknown or broader than the chosen fixed range.

Practice the State Changes

EASY

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.

Your attempt (not saved)

Worked example

A Short Trace

Determine the final frequency table for the input "cocoa".

1
Read c
c is new, so create the key c with count 1.
2
Read o
o is new, so create the key o with count 1.
3
Read c again
c already exists with count 1, so increment it to 2.
4
Read o again
o already exists with count 1, so increment it to 2.
5
Read a
a is new, so create the key a with count 1.

Result

{'c': 2, 'o': 2, 'a': 1}

Key point

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

1
Character counting can use separate variables, a list, or a dictionary.
2
Variables and lists require more advance knowledge about the characters that may appear.
3
A dictionary creates entries only for characters that actually occur.
4
The if c not in d pattern creates a count for a new key and increments the count for an existing key.
5
The completed dictionary is a histogram: a collection of counters containing the frequency information.

At a glance

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.

Related concepts

More concepts starting with S