在字符串中寻找最常见的字符的更有效方法

Question

我创建了一种查找字符串中最常见字符的方法：

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

我想询问有关IT技术的不同解决方案：

• 解决方案1 - 最快的代码（我的附加代码是否符合要求？）
• 解决方案2 - 在内存使用、减少数组和变量方面最有效

我使用了HashMap创建了我的方法 - 这对解决方案2更合适吗？如果是，为什么？它有哪些优缺点？

附加的代码是否适用于o技术（o^，o logn ...）？如果是，为什么？

- Roey Cohen

---

先排序再计数怎么样？ - user63762453

@Nivedita：这不太可能比计算频率更快。这就像基数排序，但复制的次数更少。 - Peter Cordes

https://dev59.com/2Gw15IYBdhLWcg3wSJvQ 这个问题非常类似。 - Peter Cordes

Answer 1

这是一个使用大量空间的快速算法。

它没有涵盖完整的Unicode，还有一些代码点（Unicode字符，int）需要两个字符。

仍然可以进行一些小的优化：

• 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++)
  

是的，HashMap 可能是最“明智”的解决方案。

现在有了 Java 8，您可以转向并行处理：使用多个核心。但这并不值得努力。

int mostFrequentCodePoint = s.codePoints()
    ...

对于自然语言的频率分析，将字符串长度限制在1000左右可能就足够了。

- Joop Eggen

---

只要ASCII足够，不需要utf8，256个整数并不需要很大的空间。如果输入字符串非常长，可以在一个线程中处理前一半，在另一个线程中处理后一半，并对两个计数数组的元素求和。甚至可以使用更多的线程。 - Peter Cordes

哎呀，Character.MAX_VALUE 是 0xFFFF。如果你只会接触到这个数组的低256个元素，并且JVM使用 mmap(MAP_ANONYMOUS) 获取它们并知道自己不需要将它们清零，那么这就不是问题。分配但未使用的内存实际上并不“计算”或使用RAM。 - Peter Cordes

@PeterCordes 谢谢，特别是向所有读者提到0xFFFF。其余部分对技术感兴趣，也让我思考了一些牵强的解决方案，比如内存映射文件等等。你的回答很好，可以通过检查前100个字符的Unicode脚本，并为该脚本保留一个数组来进行泛化。 - Joop Eggen

我忘记了Java如何处理Unicode。我的意思是，码点是32位的，对吧？但是char/Character只有16位？我的解决方案是，通过迭代码点而不是字符，可以正确处理Unicode。（使用低128个码点的数组，使用映射来处理其余部分）。 - Peter Cordes

关于映射文件的问题。mmap(MAP_ANONYMOUS)是malloc用于大内存分配的方法。匿名表示没有文件支持内存，只是将mmap系统调用作为内存分配器来使用。（我猜这样就不需要打开/dev/zero并使用MAP_PRIVATE映射页面了。）总之，这很重要，因为如果您从不访问不需要的部分，则分配比所需更大的巨大数组可能是可以接受的。如果（通常情况下）操作系统不介意过度提交内存，则无需保留实际内存。 - Peter Cordes

@PeterCordes 我理解了，但感激你提供了计算机科学、Unix和C语言的视角。 - Joop Eggen

Answer 2

这个问题的最快解决方法是计算每个字符的出现次数，然后在计数数组中取最大值。如果你的字符串很长，在遍历字符串中的字符时不跟踪当前最大值可以获得相当大的速度提升。

请参见如何计算字符串中字符的频率？，了解更多关于计算频率的方法。

如果您的字符串大多是ASCII码，那么在计数循环中使用一个分支来选择低128个字符值的数组或其余字符值的HashMap应该是值得的。如果您的字符串没有非ASCII字符，则分支将有良好的预测效果。如果ASCII和非ASCII之间交替出现很多次，则与对所有内容使用HashMap相比，分支可能会稍微影响效果。

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

由于我不经常使用Java，所以我没有详细编写代码，因此我不知道是否有一个容器可以比HashMap的get和put操作更有效地执行插入-1或增量操作。https://dev59.com/2Gw15IYBdhLWcg3wSJvQ#6712620建议使用Guava的MultiSet<Character>，看起来很好。

---

这可能比你的2^16个int数组更好。但是，如果你只访问这个数组的低128个元素，那么大多数内存可能永远不会被访问。已分配但未使用的内存并不会真正伤害计算机或使用RAM/交换空间。然而，在最后遍历所有65536个条目意味着至少要读取它，因此操作系统将不得不软页错误，并将其连接起来。它会污染缓存。所以，实际上，在每个字符上更新max可能是更好的选择。微基准测试可能表明，先迭代字符串，然后循环charcnt [Character.MAX_VALUE]会获胜，但这并没有考虑触及那么多不真正需要的内存所带来的缓存/ TLB污染。

- Peter Cordes

Answer 3

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

- hsyn

Answer 4

使用上述解决方案返回 ASCII 的 SimpleEntry<Character,Integer>（完整实现）：

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

- aelkz