java - 提高计数算法性能

Question

我需要编写需要 2 个集合的算法，List<String>和MyClass[]

public class MyClass {
   String key;
   String value;
}

然后它将迭代 MyClass[]并检查是否是 key也在 List<String> 。事情不简单contains在这里，key有 2 部分，文本和数字(例如“Lorem ipsum 1990”，我们只需要检查文本部分，所以这里有 trimNumber 方法。

 public String trimNumber(String key) {           
       String[] splitKey = key.split(" ");
       return splitKey [splitKey .length-1].matches(("\\d+(\\.\\d+)?")) ?
       key.replace(splitKey [splitKey .length-1], "").trim() : key;
    }

现在，我需要计算这场比赛的每次出现。最后一步是从整个集合中找到出现次数最高的。

最后，我的实现

public long calculate(final List<String> list, final MyClass[] data) {
        return Arrays.stream(data)
                .map(MyClass::getKey)
                .map(Main::trimNumber)
                .filter(list::contains)
                .collect(Collectors.groupingBy(v -> v, Collectors.counting()))
                .values()
                .stream()
                .mapToLong(i -> i)
                .max()
                .orElse(1);
    }

现在的问题是，我可以简化一下吗？或者改变一些东西以使性能更好？该部分只是更大算法的一部分，它将对大量数据进行操作。假设 15 000 x MyClass[150]每一个 HTTP 请求。所以这里每一秒都很重要。

Answer 1

而不是使用 List<String>持有key我们可以使用Set<String>特别是 HashSet<String>键查找的实现。内部 HashSet将使用背衬 HashMap将数据存储为 HashMap 的键.

现在通常key的查找时间是O(1)在最好的情况下，假设没有哈希冲突，但如果存在，查找时间最多为 O(log(n))从 JDK-8 开始，这是因为哈希冲突中的条目链接链在内部被转换为 LinkedList 到 红黑 树，其中查找时间为通过树化过程对数。

这是上述更改的 JEP:

http://openjdk.java.net/jeps/180

本文做了一个基准测试来展示 contains 之间的比较ArrayList的方法和一个 HashSet :

https://www.baeldung.com/java-hashset-arraylist-contains-performance

如果可能的话，我们可以将修剪后的 key 文本存储在 MyClass 的另一个字段中。类如此Main::trimNumber不会对所有请求进行调用，但这也会转化为额外的内存开销:

public class MyClass {
   String key;
   String value;
   String trimmedKey; //caching the trimmed key value
}