提高 Java 中按字符对大型字符串列表进行排序的速度

Question

我编写了一个代码来遍历字符串列表，returns 是整个字符串列表中出现频率最低的字符的列表。

什么是 return 按包含最少出现字符的单词排序的单词列表的最快方法？（我正在处理一个巨大的字符串列表，所以我写的代码不够快运行。下面的例子只是为了举例）

例如，如果给定的列表是：["hello", "my", "name", "is", "inigo", "montoya", "you", "killed", "my", "father", "prepare", "to", "die"]。我的代码 returns : [s, g, u, k, f, h, d, p, n, t, r, l, m, y, a, i, o, e]，其中 s 是字符串列表中出现频率最低的字母，而 e 是列表中出现频率最高的字母。然后，结果列表将 return 包含频率最低的字母的单词放在首位，依此类推。例如：["is", "inigo", "you", "killed", "father", "hello", "die", "prepare", "name", "montoya", "to", "my"]

这是我找到出现次数最少的字母的代码：

    public static void method(List<String> words)
    {
        Map<Character, Integer> elemCount = new LinkedHashMap<>();
        for (String word : words)
        {
            for (int i = 0; i  < word.length(); i++)
            {
                if (elemCount.containsKey(word.charAt(i)))
                {
                    elemCount.put(word.charAt(i), elemCount.get(word.charAt(i)) + 1);
                }
                else
                {
                    elemCount.put(word.charAt(i), 1);
                }
            }
        }
        ArrayList<Character> sortedElems = new ArrayList<>();
        LinkedList<String> sorted = new LinkedList<>();
        elemCount.entrySet().stream().sorted(
        Map.Entry.comparingByValue()).forEach(entry -> 
        { 
            for (int i = 1; i <= entry.getValue(); i++)
            {
                if (sortedElems.contains(entry.getKey()) == false)
                {
                    sortedElems.add(entry.getKey());
                }
            }
        }
        );

这是我尝试按字符串中出现频率最低的字符进行排序的代码：

        for (int i = 0; i < sortedElems.size(); i++)
        {
            for (String word : words)
            {
                char x = sortedElems.get(i);
                CharSequence c = x + "";
                if (word.contains(c) == true && sorted.contains(word) == false)
                {
                    sorted.add(word);

                }
            }
        }
        System.out.println(sorted);

Answer 1

这似乎工作得很好。我放弃了流方法，因为它太慢了。

        List<String> words = new ArrayList<>(List.of("hello", "my",
                "name", "is", "inigo", "montoya", "you", "killed",
                "my", "father", "prepare", "to", "die"));

        // frequency count.
        int[] chars = new int[256];
        for (String w : words) {
            for (char c : w.toCharArray()) {
                chars[c]++;
            }
        }
        // find minimum used character
        Map<String, Integer> mins = new HashMap<>();
        for (String w : words) {
            if (!mins.containsKey(w)) {
                int v = Integer.MAX_VALUE;
                for (char c : w.toCharArray()) {
                    if (chars[c] < v) {
                        v = chars[c];
                    }
                }
                mins.put(w, v);
            }
        }

        Comparator<String> comp1 =
                (String a, String b) -> a.compareTo(b);
        Comparator<String> comp =
                (a, b) -> mins.get(a).compareTo(mins.get(b));
        comp = comp.thenComparing(comp1);

        // sort first on character then lexically
        words.sort(comp);
        words.forEach(System.out::println);

这是频率计数

1=[f, g, k, s, u]
2=[d, h, p]
3=[n, r, t]
4=[a, l, m, y]
5=[i]
6=[o]
7=[e]

并且单词排序

father
inigo
is
killed
you
die
hello
prepare
montoya
name
to
my
my

Answer 2

这些是我的考虑，无法发表评论。

根据您的描述，算法的一般流程是扫描数组以生成直方图和使用直方图信息以某种方式对数组进行排序的两步过程。

第一步是不可避免的，并且不能进一步减少，除非数据直接从这些词的来源作为流到达。在这种情况下，您可以在新单词到达时几乎没有任何开销地简单地更新直方图。无论如何，这是简单的部分。

对于困难的部分，我们可以扫描数组并将每个单词（或指向每个单词的指针）插入到 b 树中，其拆分机制使用一个简单的函数即时计算分数作为参数的当前单词和直方图。
最后扫描b-tree，提取出所有单词排列整齐的最终数组。

在非流式场景中，计算复杂度将接近 O(n+nlog(n)+n)，但如果对原始数组使用流式且您满意，则可以达到不超过 O(nlog(n))将 B 树作为最终产品，而无需构建显式最终数组。

提高 Java 中按字符对大型字符串列表进行排序的速度

Increase Speed of Sorting Large List of Strings by Character in Java

java

performance

list

character

frequency