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();
}
}