Counting Words with a Map

Sorting WordData objects by frequency in descending order means placing the record with the highest count first.

Programming

Predicting the First Word in the Ranking

A word-counting program can tell you how many times each word appears in a text. The useful question is usually which words appear most often. This article follows one step of that program: the sort that arranges the word records so the highest count comes first. You will commit to a prediction before seeing the mechanism that produces the result.

Suppose the sample data holds three records. The word the has a count of 3, the word is has a count of 7, and the word code has a count of 5. Using the rule that the highest count should come first, decide which word should print first and which should print last. Write down your answer before you read on.

What do you think happens?

With descending order by count, which word prints first, and which prints last?

the first, code last
is first, the last
code first, is last

Reveal answer

Answer:

is first, the last. The order is is (7), code (5), the (3).

The descending rule places the record with the highest count at the front. Since is has the highest count of 7, it comes first. Code has 5, so it sits in the middle. The has 3, the lowest, so it comes last.

Why Records Need an Order

A word-counting program produces one record per distinct word, and each record holds that word's frequency. Those records are only useful when they can be ordered. Each record has two pieces of information that play different roles. The word text identifies the record, while the count attribute is what the sort uses to arrange the records.

In this program, the count field acts as the sort key. The sort does not look at the word text when it decides order. It looks at each record's count and places records with higher counts ahead of records with lower counts, so the record with the highest count ends up first.

The Three Parts of the Sort Line

The central line of the source is a single statement. It copies the values of the words collection into an ArrayList and then sorts that list, using a lambda expression as the comparator. Read the statement as a whole before reading its pieces. The statement has three parts that work together: the copy into a list, the call to Collections.sort, and the comparator passed as the second argument.

java

ArrayList<WordData> wordsByFrequency = new ArrayList<>(words.values());
Collections.sort(wordsByFrequency, (a, b) -> b.count - a.count);

ArrayList<WordData> wordsByFrequency = new ArrayList<>(words.values());
Collections.sort(wordsByFrequency, (a, b) -> b.count - a.count);

Notes on the code

Line 1 copies the values of the words Map into an ArrayList
Line 2 sorts that list using the lambda as the comparator

The sort cannot reorder a Map directly in the way a list can be reordered, so the values are first copied into an ArrayList. The sort then receives the list and the comparator. Each part has a clear job, and a failure can come from any one of them.

Which record moves to the front when the list is sorted from highest to lowest count?

In the before list, the record for is sits in the middle position. After the descending sort, it moves to the front because its count of 7 is the highest. The record for the, with the lowest count, moves to the end.

How the Comparator Decides Order

The sort needs a way to compare two WordData objects. The lambda expression (a,b) -> b.count - a.count supplies that rule. The two parameters a and b stand for two WordData objects that the sort wants to compare. The body reads the count attribute of each one and subtracts a's count from b's count.

Rule

Which part of the expression is the parameter list, which is the body, and which field supplies the sort key?

Tracing the Comparator on a Pair

Worked example

Comparing the is record with the the record

The list holds the record for the (count 3) and the record for is (count 7). Decide which record the comparator places first.

1
Assign the parameters
Pass the record for the as a and the record for is as b, so a.count is 3 and b.count is 7.
2
Evaluate the body
Compute b.count minus a.count, which is 7 minus 3, giving 4.
3
Read the sign
The result is positive, so a belongs after b. The record for is comes before the record for the.

Result

The is record is placed ahead of the the record in the descending list.

For two WordData objects, which one comes first when the comparator returns a positive value, and how does that step change the list?

The comparator handles one pair at a time. Once you can trace one pair and see which record it places first, you can apply the same method to any two records in the list. This is the step to check when a sorted output does not match what you expected.

Mistakes That Flip or Break the Order

Common mistake
Swapping the operands of the subtraction
What it looks like
```
Writing (a,b) -> a.count - b.count in place of (a,b) -> b.count - a.count
```
Why it fails
The source states that swapping the operands reverses the result, so the sort produces ascending order instead of descending order.
Do this instead
Keep b first in the subtraction when you want the highest count to come first.
Common mistake
Sorting the Map itself and expecting the records to reorder
What it looks like
Calling Collections.sort directly on the words Map
Why it fails
The source explains that a Map cannot be reordered in the way a list can, which is why the values are first copied into an ArrayList.
Do this instead
Copy words.values() into an ArrayList, then sort that list with the comparator.
Common mistake
Assuming a wrong output is caused by the sort call alone
Why it fails
The source notes that the three parts of the statement, the copy, the sort call, and the comparator, each have a job, and a failure can come from any one of them.
Do this instead
Check the list before the sort, then the comparator on individual pairs, then the list after the sort call.

Practice Predicting Descending Order

MEDIUM

Four WordData records hold these counts: data with count 2, sort with count 9, list with count 4, and map with count 6. Predict the order in which the words print after Collections.sort with the comparator (a,b) -> b.count - a.count. Then trace the comparator on the pair list and map to confirm which one comes first.

Hints

The descending rule puts the highest count first.
Compare the pair list (4) and map (6) by computing b.count minus a.count with a as list and b as map.
The final order should run from the largest count down to the smallest.

Your attempt (not saved)

Key Takeaways

A word-counting program sorts WordData objects by the count field, so the record with the highest frequency appears first.
The line copies words.values() into an ArrayList and sorts it with Collections.sort using the lambda (a,b) -> b.count - a.count.
Writing b.count first in the subtraction produces descending order, and swapping the operands reverses the result to ascending.
When output does not match expectations, trace the comparator on individual pairs and check the list before and after the sort call.