如何优化Java中的函数以使其更快？

Question

public static ArrayList<Integer> duplicates(int[] arr) {
    ArrayList<Integer> doubles = new ArrayList<Integer>();
    boolean isEmpty = true;
    for(int i = 0; i<arr.length; i++) {
        for (int j = i+1; j< arr.length; j++) {
            if( arr[i] == arr[j] && !doubles.contains(arr[i]) ){
                doubles.add(arr[i]);
                isEmpty = false;
                break;
            }
        }
    }
    if(isEmpty) doubles.add(-1);
    Collections.sort(doubles);
    return doubles;
}

public static void main(String[] args) {
    System.out.println( ( duplicates( new int[]{1,2,3,4,4,4}  ) ) ); // Return: [4]
}

我用 Java 创建了这个函数，它返回输入 int 数组的倍数，如果输入数组为空或没有倍数，则返回 -1。

它有效，但可能有一种方法可以让它更快。是否有任何好的做法可以使函数总体上更高效、更快？

Answer 1

概括地说，您可以进行 2 项完全不相关的性能改进：

• 降低算法复杂度。这是一个高度数学化的概念。
• 降低实际性能特征 - 从字面上看，只是让它运行得更快和/或使用更少的内存（通常，“使用更少的内存”和“更快”是齐头并进的）。

第一个很简单，但可能会产生误导：您可以编写一个算法，以算法上不太复杂的方式完成相同的工作，但实际上运行速度较慢。

第二个也很棘手：你的眼球和大脑无法完成这项工作。编写 JVM 本身的工程师曾公开表示，他们通常不知道任何给定代码的实际运行速度有多快。这是因为 JVM太复杂了：它有很多复杂的途径来优化东西的运行速度（不仅是支持这些东西的代码复杂，而且它们的工作方式也很复杂。例如，热点最终启动，并使用以前运行的特征来确定如何最好地将给定方法重写为经过微调的机器代码，并且运行它的硬件也很重要）。

这得出以下简单的结论：

• 除非存在实际性能问题，否则不要执行任何操作。
• 您确实需要一份能够实际指示哪些代码“相关”的探查器报告。一般来说，对于任何给定的 java 应用程序，所有代码行中的 1% 负责 99% 的负载。除了那 1% 之外，优化任何东西都是没有意义的。分析器报告对于查找需要关注的 1% 很有用。Java 附带了一个分析器，并且还有商业产品。
• 如果您想要进行微基准测试（针对特定输入对特定代码片段进行计时），这也非常困难，并且存在许多陷阱。实际上只有一种方法可以做到这一点：使用Java Microbenchmark Harness。
• 虽然您可以决定关注算法复杂性，但您可能仍然需要分析器报告或 JMH 运行，因为算法复杂性就是“最终，即在输入足够大的情况下，算法复杂性克服了任何其他性能方面”。诀窍是：您的输入是否足够大以达到“最终”空间？

对于这个特定的算法，鉴于我不知道合理的输入可能是什么，您将必须完成设置 JMH 和/或探查器运行的工作。然而，就算法复杂性而言：

该doubles.contains调用的算法复杂度为 O(N)：调用所需的时间与输入的大小成线性关系。

如果您使用 HashSet，则可以获得 O(1) 的算法复杂度。

从单纯的性能角度来看，通常 ArrayList 的性能和内存负载与 ArrayList 相比int[]是相当大的。

这给出了 2 个替代的明显策略来优化此代码：

• 将 替换ArrayList<Integer>为int[].
• 将 替换为ArrayList<integer>a HashSet<Integer>。

如果不花费大量时间来处理原始 int 数组支持的 hashbucket 实现，您就无法真正将这两者结合起来。幸运的是，有人为您完成了这项工作：Eclipse Collections 有一个原始的 int hashset 实现。

理论上很难想象用 IntHashSet 替换它会慢多少。然而，我不能公开向你保证它会更快：我可以想象如果你的输入是一个包含几百万个整数的 int 数组，IntHashSet 可能会快很多个数量级。但您确实需要测试数据和探查器报告和/或 JMH 运行，否则我们都只是猜测，考虑到 JVM 是如此复杂，这是一个坏主意。

所以，如果你真的想优化这个：

• 编写一堆测试用例。
• 围绕此代码编写一个包装器，以便您可以在 JMH 设置中运行这些测试。
• 将代码替换为 IntHashSet 并将其与 JMH 工具中的上述代码进行比较。
• 如果这确实改善了事情并且现在的性能满足您的需求，那就太好了。你完成了。
• 如果没有，您可能需要重新评估在何处以及如何使用此代码，或者是否可以采取其他措施来优化。