7

I created a method for finding the most common character in a string:

public static char getMax(String s) {

char maxappearchar = ' ';
int counter = 0;
int[] charcnt = new int[Character.MAX_VALUE + 1];


for (int i = 0 ; i < s.length() ; i++)
{
    char ch = s.charAt(i);
    // increment this character's cnt and compare it to our max.
    charcnt[ch]++ ;
    if (charcnt[ch] >= counter)
    {
        counter = charcnt[ch];
        maxappearchar = ch;
    } 
}
System.out.println("the max char is   " +maxappearchar + "  and displayed  " +counter+ "  times");
return maxappearchar;
}

I am asking about different solutions for it:

  • solution 1 - Fastest code (is that my attached code?)
  • solution 2 - Most effective in terms of memory, reduced use of arrays and variables

I created my method using HashMap - is that more Suitable for solution 2? If so why? And what are the pros/cons?

Is the attached code is suitable for o Technique (o^ , o logn ... )? If so why?

3

4 Answers 4

3

The fastest way to do this will be to count occurrences of every character, then take the max value in the count array. If your string is long, you'll gain a decent speedup from not tracking the current max while looping over characters in the String.

See How to count frequency of characters in a string? for many other ideas about how to count frequencies.

If your Strings are mostly ASCII, a branch in the count loop to choose between an array for the low 128 char values, or a HashMap for the rest, should be worth it. The branch will predict well if your strings don't have non-ASCII characters. If there's a lot of alternating between ascii and non-ascii, the branch might hurt a bit, compared to using HashMap for everything.

public static char getMax(String s) {

    char maxappearchar = ' ';
    int counter = 0;
    int[] ascii_count = new int[128];  // fast path for ASCII
    HashMap<Character,Integer> nonascii_count = new HashMap<Character,Integer>();

    for (int i = 0 ; i < s.length() ; i++)
    {
        char ch = s.charAt(i);  // This does appear to be the recommended way to iterate over a String
        // alternatively, iterate over 32bit Unicode codepoints, not UTF-16 chars, if that matters.
        if (ch < 128) {
            ascii_count[ch]++;
        } else {
            // some code to set or increment the nonascii_count[ch];
        }
    }

    // loop over ascii_count and find the highest element
    // loop over the keys in nonascii_count, and see if any of them are even higher.
    return maxappearchar;
}

I didn't flesh out the code, since I don't do a lot of Java, so IDK if there's a container than can do the insert-1-or-increment operation more efficiently than a HashMap get and put pair. https://stackoverflow.com/a/6712620/224132 suggests Guava MultiSet<Character>, which looks good.


This may do better than your array of 2^16 ints. However, if you only ever touch the low 128 elements of this array, then most of the memory may never be touched. Allocated but untouched memory doesn't really hurt, or use up RAM / swap.

However, looping over all 65536 entries at the end means at least reading it, so the OS would have to soft pagefault it in and wire it up. And it will pollute caches. So actually, updating the max on every character might be a better choice. Microbenchmarks might show that iterating over the String, then looping over charcnt[Character.MAX_VALUE] wins, but that wouldn't account for the cache / TLB pollution of touching that much not-really-needed memory.

3

It is a fast algorithm using much space.

It does not cover full Unicode, there are code points (Unicode characters, ints) that need two chars.

Small optimizations still possible:

  • Making extra versions with byte[] and short[], depending on s.length().
  • Keeping the length() in a variable

    for (int i = 0, n = s.length(); i < n; i++)
    

And yes a HashMap probably is the most "sensible" solution.

Now with java 8, you might turn to parallelism: using multiple cores. Not worth the effort.

int mostFrequentCodePoint = s.codePoints()
    ...

For frequency analysis in natural language, it may suffice to limit the string's length to 1000 or so.

6
  • 1
    As long as ASCII-only, not utf8 is sufficient, 256 ints is not a lot of space. Good point that if the input strings are extremely long, you could do the first half in one thread, 2nd half in another thread, and sum the elements of the two count arrays. (or even more threads if you want) Aug 13, 2015 at 23:44
  • 1
    Oops, Character.MAX_VALUE is 0xFFFF. If you only ever touch the low 256 elements of this array, and the JVM gets them with mmap(MAP_ANONYMOUS) and knows it doesn't need to zero them itself, then it's not a problem. Allocated but untouched memory doesn't really count, or use up RAM. Aug 14, 2015 at 0:04
  • 1
    @PeterCordes thanks, especially mentioning the 0xFFFF to all readers. The rest is of technical interest, and makes me pondering also about far-fetched solutions like, a memory mapped file, and so on. Your answer is nice, might be generalized by checking the Unicode script of the first 100 characters, and then holding an array for that script.
    – Joop Eggen
    Aug 14, 2015 at 7:48
  • 1
    re: mapping a file. mmap(MAP_ANONYMOUS) is what malloc uses for big allocations. Anonymous means there is no file backing up the memory. It's just overloading the mmap system call as a memory allocator. (Instead of having to actually open /dev/zero and map pages of that with MAP_PRIVATE, I guess.) Anyway, it's relevant because allocating a giant array bigger than you need can be ok if you never touch the parts you don't need. Real memory doesn't need to be reserved, if (like is normal) the OS doesn't mind overcommitting memory. Aug 14, 2015 at 8:06
  • 1
    @PeterCordes I understood but am grateful for a CS & Unix & C perspective.
    – Joop Eggen
    Aug 14, 2015 at 8:30
1
public class HelloWorld {

    public static void main(String[] args) {

        String word = "Ferrari";

        String mostUsedChar = "";
        int count = 0;

        String[] array = word.split("");

        for (int i = 0; i < array.length; i++) {
            int tempCount = 0;

            for (int j = 0; j < array.length; j++)
            {
                if (array[i].equals(array[j])) {
                    tempCount++;
                }
                if (tempCount > count) {
                    count = tempCount;
                    mostUsedChar = array[i];
                }
            }
        }
        System.out.println(count + " Most Used Char: " + mostUsedChar);
    }
}
0

Using the solution above returning a SimpleEntry<Character,Integer> (full implementation) for ASCII:

public static Map.Entry getMostCommonChar(String phrase) {
    if (phrase == null || phrase.isEmpty()) {
        throw new IllegalArgumentException("input phrase must have non-empty value.");
    }

    char maxchar = ' ';
    int counter = 0;
    int[] ascii_count = new int[Character.MAX_VALUE];  // fast path for ASCII

    for (int i = 0; i < phrase.length(); i++) {
        char ch = phrase.charAt(i);  // This does appear to be the recommended way to iterate over a String
        if (ascii_count[ch]++ >= counter) {
            counter = ascii_count[ch];
            maxchar = ch;
        }
    }

    Map.Entry<Character,Integer> e = new AbstractMap.SimpleEntry<>(maxchar,counter);

    System.out.println(e.getKey());
    System.out.println(e.getValue());

    return e;
}

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.