Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
1  
Algorithms + Data Structures = Programs. You would be well served by going through the java collections and thinking of a use case for each one. See also Torvalds' quote about good programmer. –  MichaelT May 17 '13 at 3:53

4 Answers 4

up vote 7 down vote accepted

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.
share|improve this answer
  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.

share|improve this answer

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/

share|improve this answer
    
Why a tree and not hash? –  MichaelT May 17 '13 at 16:10

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">
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.