4
\$\begingroup\$

Continuing my TDD from exercism.

Write a program that given a phrase can count the occurrences of each word in that phrase.

For example for the input "olly olly in come free"

olly: 2
in: 1
come: 1
free: 1
import java.util.Map;
import java.util.HashMap;

/**
 * Counts the word in a given string. Ignores any punctuation.
 * Example:
 *    "one two, two# ??three" === {"one": 1, "two": 2, "three": 1}
 */
public class WordCount {
  private final Map<String, Integer> wordFrequencyMap;

  WordCount() {
    wordFrequencyMap = new HashMap<>();
  }

  public Map<String, Integer> phrase(String phrase) {
    for (String word : phrase.trim().split("\\s+")) {
      word = withoutPunctuation(word.toLowerCase());
      if (word == null || word.isEmpty()) {
        continue;
      }
      if (!wordFrequencyMap.containsKey(word)) {
        wordFrequencyMap.put(word, 1);
      } else {
        wordFrequencyMap.put(word, wordFrequencyMap.get(word) + 1);
      }
    }
    return wordFrequencyMap;
  }

  private String withoutPunctuation(String word) {
    String wordWithoutPunctuation = "";
    for (char ch : word.toCharArray()) {
      if (isLetter(ch) || isDigit(ch)) {
        wordWithoutPunctuation += ch;
      }
    }
    return wordWithoutPunctuation;
  }

  private boolean isLetter(char ch) {
    return ch >= 'a' && ch <= 'z';
  }

  private boolean isDigit(char ch) {
    return ch >= '0' && ch <= '9';
  }
}

Test suite:

import org.junit.Test;

import java.lang.Integer;
import java.lang.String;
import java.util.HashMap;
import java.util.Map;

import static org.junit.Assert.*;

public class WordCountTest {

    private final WordCount wordCount = new WordCount();

    @Test
    public void countOneWord() {
        Map<String, Integer> actualWordCount = new HashMap<String, Integer>();
        final Map<String, Integer> expectedWordCount = new HashMap<String, Integer>();
        expectedWordCount.put("word", 1);

        actualWordCount = wordCount.phrase("word");
        assertEquals(
            expectedWordCount, actualWordCount
        );
    }

    @Test
    public void countOneOfEach() {
        Map<String, Integer> actualWordCount = new HashMap<String, Integer>();
        final Map<String, Integer> expectedWordCount = new HashMap<String, Integer>();
        expectedWordCount.put("one", 1);
        expectedWordCount.put("of", 1);
        expectedWordCount.put("each", 1);

        actualWordCount = wordCount.phrase("one of each");
        assertEquals(
            expectedWordCount, actualWordCount
        );
    }

    @Test
    public void countMultipleOccurences() {
        Map<String, Integer> actualWordCount = new HashMap<String, Integer>();
        final Map<String, Integer> expectedWordCount = new HashMap<String, Integer>();
        expectedWordCount.put("one", 1);
        expectedWordCount.put("fish", 4);
        expectedWordCount.put("two", 1);
        expectedWordCount.put("red", 1);
        expectedWordCount.put("blue", 1);

        actualWordCount = wordCount.phrase("one fish two fish red fish blue fish");
        assertEquals(
            expectedWordCount, actualWordCount
        );
    }

    @Test
    public void ignorePunctuation() {
        Map<String, Integer> actualWordCount = new HashMap<String, Integer>();
        final Map<String, Integer> expectedWordCount = new HashMap<String, Integer>();
        expectedWordCount.put("car", 1);
        expectedWordCount.put("carpet", 1);
        expectedWordCount.put("as", 1);
        expectedWordCount.put("java", 1);
        expectedWordCount.put("javascript", 1);

        actualWordCount = wordCount.phrase("car : carpet as java : javascript!!&@$%^&");
        assertEquals(
            expectedWordCount, actualWordCount
        );

    }

    @Test
    public void includeNumbers() {
        Map<String, Integer> actualWordCount = new HashMap<String, Integer>();
        final Map<String, Integer> expectedWordCount = new HashMap<String, Integer>();
        expectedWordCount.put("testing", 2);
        expectedWordCount.put("1", 1);
        expectedWordCount.put("2", 1);

        actualWordCount = wordCount.phrase("testing, 1, 2 testing");
        assertEquals(
            expectedWordCount, actualWordCount
        );
    }

    @Test
    public void normalizeCase() {
        Map<String, Integer> actualWordCount = new HashMap<String, Integer>();
        final Map<String, Integer> expectedWordCount = new HashMap<String, Integer>();
        expectedWordCount.put("go", 3);

        actualWordCount = wordCount.phrase("go Go GO");
        assertEquals(
            expectedWordCount, actualWordCount
        );
    }

}

Learning from my previous experiences I agree the code breaks encapsulation as an exception (client requirement). Other thing is that I didn't want to use Regex hence wanted to test my own knowledge.

Regarding performance I haven't thought much it should be O(n).

\$\endgroup\$
10
\$\begingroup\$

Building Strings with +=

In your withoutPunctuation method, you are building the String to return by appending each character with +=.

private String withoutPunctuation(String word) {
  String wordWithoutPunctuation = "";
  for (char ch : word.toCharArray()) {
    if (isLetter(ch) || isDigit(ch)) {
      wordWithoutPunctuation += ch;
    }
  }
  return wordWithoutPunctuation;
}

It would be better to use a StringBuilder which is a class dedicated for that. The problem is that each character will be turned into a String and concatenated to the previous String, resulting in a new String again and again. All those String creation takes time. Using a StringBuilder solves that problem:

private String withoutPunctuation(String word) {
    StringBuilder wordWithoutPunctuation = new StringBuilder();
    for (char ch : word.toCharArray()) {
        if (isLetter(ch) || isDigit(ch)) {
            wordWithoutPunctuation.append(ch);
        }
    }
    return wordWithoutPunctuation.toString();
}

Unnecessary checks

The String returned by the withoutPunctuation method can never be null (and that's a good thing). So there is no need to check for it later:

word = withoutPunctuation(word.toLowerCase());
if (word == null || word.isEmpty()) {
  continue;
}

You can just have:

word = withoutPunctuation(word.toLowerCase());
if (word.isEmpty()) {
    continue;
}

Potential bugs

You are currently lowercasing Strings with

word.toLowerCase()

This can lead to weird bugs. In fact, if someone with a Turkish locale were to run your code on the sentence "I LIKE JAVA", they would have as result the map {java=1, lke=1}. Notice the "I" that are missing. This is because changing the case of a String depends on the locale and by default, this is the locale of the JVM, which also defaults to your system locale. The capital "I" in Turkish is lowercased to "ı" (dot-less i), which then doesn't pass your filter because it isn't a character between 'a' and 'z'.

To counteract this, it is best to use the ROOT locale when changing the case, so you should have:

word.toLowerCase(Locale.ROOT)

Cache the Pattern

Compiling a regulax expression Pattern, which is done internally by split, takes time. It would be best to compile it only once and reuse the Pattern. Consider making it a constant:

private static final Pattern PATTERN = Pattern.compile("\\s+");

Then you can have

for (String word : PATTERN.split(phrase.trim())) {
    // ...
}

Other comments

Do you really need wordFrequencyMap as an instance field? It is only used inside the phrase method so it would be better to declare it inside.

If you're on Java 8, consider using the Stream API for the phrase method. You would have:

public Map<String, Long> phrase(String phrase) {
    return PATTERN.splitAsStream(phrase.trim())
                  .map(s -> withoutPunctuation(s.toLowerCase(Locale.ROOT)))
                  .filter(s -> !s.isEmpty())
                  .collect(Collectors.groupingBy(s -> s, Collectors.counting()));
}

In the same way, the withoutPunctuation method can be written

private String withoutPunctuation(String word) {
    return word.chars()
               .filter(ch -> isLetter((char) ch) || isDigit((char) ch))
               .collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append)
               .toString();
}
\$\endgroup\$
  • \$\begingroup\$ So Locale.ROOT would let me treat string as English irrespective of the locale we are in, right? \$\endgroup\$ – CodeYogi Apr 27 '16 at 2:15
  • \$\begingroup\$ I think I need to start using java8, it seems cool. \$\endgroup\$ – CodeYogi Apr 27 '16 at 2:16
  • \$\begingroup\$ @CodeYogi Not strictly, ROOT is the language/country neutral locale for the locale sensitive operations. Using ENGLISH would have the same effect here (I guess it is a matter of taste) \$\endgroup\$ – Tunaki Apr 27 '16 at 7:44
  • \$\begingroup\$ Really the Locale thing was new to me, thanks! \$\endgroup\$ – CodeYogi Apr 27 '16 at 16:25
  • \$\begingroup\$ One more thing I would like to ask. I am preparing for the competitive programming and most of the books on algorithms I have read use the imperative style of coding, while the functional approach is a declarative one, what should I do? should I stick to java7 for the sake of getting correct material or move to java8 but then I think it would be difficult to get any good reference material. \$\endgroup\$ – CodeYogi Apr 27 '16 at 17:00
6
\$\begingroup\$

Checking letters and digits

Instead of your own isLetter and isDigit methods, it would be better to use Character.isLetter and Character.isDigit. Even better, there's actually Character.isLetterOrDigit too.

Not using regular expressions

Although you say you don't want to use regular expressions, you're actually using them, in the split.

Performance

Note that when you split, an array is created from the String, roughly doubling the extra storage needed. You could reduce the storage by tokenizing manually.

It's not a huge problem, but in this code, if the word is in the map, you perform two lookups, first with containsKey, and then again with get:

  if (!wordFrequencyMap.containsKey(word)) {
    wordFrequencyMap.put(word, 1);
  } else {
    wordFrequencyMap.put(word, wordFrequencyMap.get(word) + 1);
  }

Example alternative implementation:

public Map<String, Integer> phrase(String phrase) {
    Map<String, Integer> wordFrequencyMap = new HashMap<>();

    int start = indexOfWordStart(phrase, 0);
    while (start < phrase.length()) {
        int end = indexOfWordEnd(phrase, start);
        String word = phrase.substring(start, end).toLowerCase(Locale.ROOT);
        Integer count = wordFrequencyMap.get(word);
        if (count == null) {
            wordFrequencyMap.put(word, 1);
        } else {
            wordFrequencyMap.put(word, count + 1);
        }
        start = indexOfWordStart(phrase, end);
    }
    return wordFrequencyMap;
}

private int indexOf(String phrase, int start, Predicate<Character> predicate) {
    for (int i = start; i < phrase.length(); ++i) {
        if (predicate.test(phrase.charAt(i))) {
            return i;
        }
    }
    return phrase.length();
}

protected int indexOfWordStart(String phrase, int start) {
    return indexOf(phrase, start, Character::isLetterOrDigit);
}

protected int indexOfWordEnd(String phrase, int start) {
    return indexOf(phrase, start, c -> !Character.isLetterOrDigit(c));
}

Unit tests

The unit tests are a bit tedious. Take for example this test:

Map<String, Integer> actualWordCount = new HashMap<String, Integer>();
final Map<String, Integer> expectedWordCount = new HashMap<String, Integer>();
expectedWordCount.put("word", 1);

actualWordCount = wordCount.phrase("word");
assertEquals(
    expectedWordCount, actualWordCount
);

This can be written in a single line:

assertEquals(Collections.singletonMap("word", 1), wordCount.phrase("word"));

But let's take a more interesting example:

Map<String, Integer> actualWordCount = new HashMap<String, Integer>();
final Map<String, Integer> expectedWordCount = new HashMap<String, Integer>();
expectedWordCount.put("one", 1);
expectedWordCount.put("of", 1);
expectedWordCount.put("each", 1);

actualWordCount = wordCount.phrase("one of each");
assertEquals(
    expectedWordCount, actualWordCount
);

Can be shortened to:

final Map<String, Integer> expectedWordCount = new HashMap<>();
expectedWordCount.put("one", 1);
expectedWordCount.put("of", 1);
expectedWordCount.put("each", 1);

assertEquals(expectedWordCount, wordCount.phrase("one of each"));

The changes:

  • There's really no need for actualWordCount, can be easily inlined without hurting readability
    • If you still want to keep actualWordCount, at least declare it right before you use it, not at the top of the method
  • Use the diamond operator <>, so new HashMap<>() instead of new HashMap<String, Integer>()
\$\endgroup\$
  • \$\begingroup\$ The problem with Character.isDigit for example is that it will return true for all Unicode character in the Nd category, not just 'a-z' which might be too much here (it depends on what is wanted). \$\endgroup\$ – Tunaki Apr 26 '16 at 22:54
  • \$\begingroup\$ Usually I don't look at test cases since its already there by exercism team but I think you are right they need to put some more effort. Regarding syntax it seems a bit alien to me like Character::isLetterOrDigit, is this java 8? \$\endgroup\$ – CodeYogi Apr 27 '16 at 2:04
  • \$\begingroup\$ Yes that's Java 8 \$\endgroup\$ – Stop ongoing harm to Monica Apr 27 '16 at 5:35
  • \$\begingroup\$ I need few more insights. 1) What is the use case of such class in which we really don't need any instance variables, should it be better as utility class with private constructor? 2) why ++i? \$\endgroup\$ – CodeYogi Apr 27 '16 at 16:31
  • \$\begingroup\$ Yes, a class with pure functions and no data can be turned into a utility class. For your second question, in this context ++i and i++ are equivalent. \$\endgroup\$ – Stop ongoing harm to Monica Apr 27 '16 at 17:27
1
\$\begingroup\$

Since regular expression matching is so blazing fast I would use them to implement withoutPunctuation():

private String withoutPunctuation(String s) {
    return s.replaceAll("[^a-zA-Z0-9\\s]+", "");
}

It would be even better to use pre-compiled regular expressions:

private static final Pattern ALPHANUMERIC_AND_SPACE_ONLY =
    Pattern.compile("[^a-zA-Z0-9\\s]+");

private String withoutPunctuation(String s) {
    return ALPHANUMERIC_AND_SPACE_ONLY.matcher(s).replaceAll("");
}

Of course you should benchmark it to see whether it's actually faster.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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