9
\$\begingroup\$

I'm new to Java and is trying to solve the beginners problem of finding out the number of vowels in a string. I was just wondering if there is any alternatives to any of the steps that can improve efficiency as well as simplicity.

import java.util.Arrays;
import java.util.Scanner;


public class CountVowels{

    public static void main(String[] args) {
        Scanner sc1 = new Scanner(System.in);
        String userInput = sc1.next();
        sc1.close();
        CountVowels cv1 = new CountVowels();
        int numberOfVowels = cv1.countingVowels(userInput);
        System.out.println(numberOfVowels);
    }


    public int countingVowels(String s1){
        String lowerCaseString = s1.toLowerCase();
        int vowelCount = 0;
        for (int i = 0; i < lowerCaseString.length(); ++i){
            Character charCharacter = lowerCaseString.charAt(i);
            char[] vowels = {'a', 'e', 'i', 'o', 'u'};
            if(Arrays.binarySearch(vowels, charCharacter) >= 0){
                vowelCount += 1;
            }
        }
        return vowelCount;
    }
}
\$\endgroup\$
0

5 Answers 5

5
\$\begingroup\$

Always measure! :)

I took the liberty of taking the original code and the proposed algorithms and did a benchmark. I also threw in my own algorithm in the mix.

First off, the results. I generate a random string with 10k vowels and 90k non-vowels and run each algorithm through it for 1000 passes and take the average:

OriginalVowelCounter n=10000: (Unit: NANOSECONDS)
Average  :  2 006 894,0000

LinearSearchVowelCounter n=10000: (Unit: NANOSECONDS)
Average  :  1 199 626,0000

BooleanArrayVowelCounter n=10000: (Unit: NANOSECONDS)
Average  :  792 455,0000

IntArrayVowelCounter n=10000: (Unit: NANOSECONDS)
Average  :   73 250,0000

First there is the OP's original algorithm. Then the linear search proposed by 200_success. We see that the linear search is much faster than a binary search for such a small array. The overhead of the binary search is just too much here.

Then izomorphius suggested using a boolean array to avoid the searching altogether and this is again much faster than even the linear search. But at this stage, branch prediction on the boolean array is starting to become an issue. Because the data is random the branch is poorly predicted.

I propose using an array of int instead of boolean and simply add the contents of the array to a counter to avoid the branch (if statement) and avoid the branch-prediction fails. The result is by far the fastest algorithm this far. Beating the boolean array with a factor 11x, and the original algorithm by a factor 27.5x.

Finally, I'll attach the source code for the comparison (requires the excellent µbench):

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;

import net.tuis.ubench.UBench;

public class Main {

    public static String genString(int aVowels, int aLength) {
        List<Character> chars = new ArrayList<>(aLength);
        String vowels = "aiueoAIUEO";
        String nonVowels = "bcdfghjklmnpqrstvwxyzBCDFGHJKLMNPQRSTVWXYZ";
        Random rnd = new Random();
        for (int i = 0; i < aVowels; ++i) {
            chars.add(vowels.charAt(rnd.nextInt(vowels.length())));
        }
        while (chars.size() < aLength) {
            chars.add(nonVowels.charAt(rnd.nextInt(nonVowels.length())));
        }
        Collections.shuffle(chars, rnd);
        StringBuilder sb = new StringBuilder();
        for (Character c : chars) {
            sb.append(c.charValue());
        }

        return sb.toString();
    }

    public static interface VowelCounter {
        int count(String aString);
    }

    public static class OriginalVowelCounter implements VowelCounter {
        public int count(String s1) {
            String lowerCaseString = s1.toLowerCase();
            int vowelCount = 0;
            for (int i = 0; i < lowerCaseString.length(); ++i) {
                Character charCharacter = lowerCaseString.charAt(i);
                char[] vowels = { 'a', 'e', 'i', 'o', 'u' };
                if (Arrays.binarySearch(vowels, charCharacter) >= 0) {
                    vowelCount += 1;
                }
            }
            return vowelCount;
        }
    }

    public static class LinearSearchVowelCounter implements VowelCounter {
        String vowels = "aeiou";

        public int count(String s1) {
            String lowerCaseString = s1.toLowerCase();
            int vowelCount = 0;
            for (int i = 0; i < lowerCaseString.length(); ++i) {
                if (vowels.indexOf(lowerCaseString.charAt(i)) != -1) {
                    vowelCount += 1;
                }
            }
            return vowelCount;
        }
    }

    public static class BooleanArrayVowelCounter implements VowelCounter {
        boolean vowel[] = new boolean[26];

        public BooleanArrayVowelCounter() {
            vowel['a' - 'a'] = vowel['e' - 'a'] = vowel['i' - 'a'] = vowel['u' - 'a'] = vowel['o' - 'a'] = true;
        }

        public int count(String s1) {
            int count = 0;
            for (char c : s1.toLowerCase().toCharArray()) {
                if (vowel[c - 'a']) {
                    count++;
                }
            }
            return count;
        }
    }

    public static class IntArrayVowelCounter implements VowelCounter {
        int vowel[] = new int[256];

        public IntArrayVowelCounter() {
            vowel['a'] = vowel['e'] = vowel['i'] = vowel['u'] = vowel['o'] = 1;
            vowel['A'] = vowel['E'] = vowel['I'] = vowel['U'] = vowel['O'] = 1;
        }

        public int count(String s1) {
            int count = 0;
            for (char c : s1.toCharArray()) {
                count += vowel[c];
            }
            return count;
        }
    }

    public static void main(String[] args) {
        UBench bench = new UBench("Vowel counting");

        VowelCounter contenders[] = new VowelCounter[] { new OriginalVowelCounter(), new LinearSearchVowelCounter(),
                new BooleanArrayVowelCounter(), new IntArrayVowelCounter() };

        for (int vowels = 1; vowels < 100000; vowels *= 10) {
            final int testVowels = vowels;
            String testString = genString(testVowels, 10 * testVowels);

            for (VowelCounter counter : contenders) {
                bench.addIntTask(counter.getClass().getSimpleName() + " n=" + testVowels,
                        () -> counter.count(testString), (ans) -> ans == testVowels);
            }
        }

        bench.press(1000).report();
    }
}
\$\endgroup\$
15
\$\begingroup\$

Outline

In this case, instantiating a new CountVowels() is overkill. all you need is a function.

As a rule, classes should be named as nouns. A better name for the class would be VowelCounter.

public class VowelCounter {
    public static int vowelCount(String s) {
        …
    }

    public static void main(String[] args) {
        …
        System.out.println(vowelCount(userInput));
    }
}

Implementation

Your countingVowels() function is fine, but could be simpler.

public static int vowelCount(String s) {
    int count = 0;
    for (char c : s.toLowerCase().toCharArray()) {
        if ("aeiou".indexOf(c) >= 0) {
            count++;
        }
    }
    return count;
}

Specifically, note:

  • Using an enhanced for loop is less tedious than a counting loop.
  • Avoid boxed types such as Character, when a primitive char will do.
  • For such a short array, a binary search is overkill.

Your main() is also OK, but I would write it this way:

public static void main(String[] args) {
    try (Scanner scanner = new Scanner(System.in)) {
        String userInput = scanner.next();
        System.out.println(vowelCount(userInput));
    }
}

In particular:

  • A Scanner is AutoCloseable, so a try-with-resources block is tidier than calling close() on it manually.
  • There doesn't seem to be much point in the …1 suffix on your variable names sc1, cv1, and s1.
\$\endgroup\$
5
\$\begingroup\$

I would personally do any character-by-character analysis in Java by a char[] rather than a String, see String.toCharArray(). Furthermore, you could staticly declare vowels in the global scope, which is neater and may improve performance(I'm not sure if JVMs do optimize static variables, but I think they do).

There is no point in drawing out the += 1 in vowelCount += 1, you can just do vowelCount++.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you so much for the advice!! really appreciate your time and help!! \$\endgroup\$
    – Thor
    Jan 27, 2016 at 1:11
5
\$\begingroup\$

Names

At least to me, the names you've used seem somewhat backwards. You've defined the name of the class as a verb phrase (CountVowels) and the name of the method do the actual counting as if it were something like a state (countingVowels). You'd typically use a noun (or noun phrase) as the class name, and the method would be a verb, something like VowelCounter and count (or countVowels) respectively.

Algorithm choice

Given that you're only looking through five items, I'd at least test using a linear search instead of a binary search. With such a tiny number of items, the gain from using a binary search is minuscule at best, and I think there's a solid chance that it works out as a net loss.

If you do have to deal with a large number of vowels, it may be worth considering using something like a HashSet (or possibly TreeSet) to hold the vowels. This tends to be particularly attractive if you might (at some point) need to deal with text that contains a mixture of different natural languages, so the rules for which is or isn't a vowel might need to change over time.

Flexibility

It's at least worth considering what it would take to treat y as a vowel. More generally, it may be worth considering doing something like passing a string to the vowel counter to specify what characters should be treated as vowels. As it stands right now, the code is marginal for English, and basically unusable for most other languages (but the only real difference between English and, say, French, in this respect, is which characters are vowels, not in the code itself).

\$\endgroup\$
3
\$\begingroup\$

If performance is critical and you plan to use this for big text, it may pay off to use a boolean array where you indicate if a character is vowel or not. Here is a short example of what I propose.

public static void main (String[] args) throws java.lang.Exception
{
    boolean vowel[] = new boolean[26];
    vowel['a'-'a']=vowel['e'-'a']=vowel['i' -'a']=vowel['u'-'a']=vowel['o'-'a'] = true;

    String test = "somelongcomplextext";
    int count = 0;
    for (char c : test.toLowerCase().toCharArray()) {
        if (vowel[c - 'a']) {
            count ++;
        }
    }

    System.out.println(count);
}

The same code on ideone.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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