Find the count of each word in a string

Question

I am in a search of a better performant algorithm to implement a program, to find the count of each word in a sentence i.e.., a String in the programming sense.

I know my algorithm is too basic and Noob. Here's my algorithm.

1. Read the String.
2. Tokenize the String with the delimiter, put each token in a list(ArrayList).
3. Iterate the generated list, in each iteration compare the current string with every other string of the list, if it matches increase the count of this string.
4. For each iteration, put the String and its count in a map.
5. Iterate the map and display, with key as string and value as its count.

What is the best approach than this?

Answer 1

Replace steps 3 and 4 with the following

• If string is not in the map, store it in the map with value Integer.valueOf(1)
• If is already in the map, get the current value, increment it, and replace the mapping.

Answer 2

1. Create a Scanner for your InputStream, Reader, File, String, etc
2. Iterate over the tokens
3. If a word doesn't already exist in your Map, add it with a value of 1.
4. If a word already exists in the map, increment its value.
5. When done, close the Scanner.
6. Iterate over the map and display.

Your solution and @parsifal's take a couple of unnecessary steps that are avoided with this solution:

• When using a Scanner to read an InputStream, Reader, or File, you don't need to read the whole thing into memory at once, making this solution work with very large inputs.
• In addition to storing the entire input in a String, you duplicate the whole thing (minus spaces) in an ArrayList. In this solution there is no intermediate storage.

Here's a quick intro to Scanner.

Answer 3

The inefficient part of your algorithm is in fact the ArrayList, because it can't be traversed in a efficient way. The appropriate data structure is in your case a binary tree.

A very detailed discussion of binary trees: http://www.shiffman.net/teaching/a2z/concordance/

Answer 4

The trick is to use the right data structure for the job, and in this case the right data structure is a multiset. In fact, the multiset is the answer, you don't even need an algorithm.

Here's an example in Ruby:

require 'multiset'

s = 'Hello World Hello Programming Hello World'

Multiset.new(s.split)
# => #<Multiset:#3 "Hello", #2 "World", #1 "Programming">