Java :测试数组和算法的效率

Question

我正在上大学的爪哇课程，我的笔记给了我3种计算ArrayList之和的方法。第一次使用迭代，第二次使用递归，第三次使用数组拆分结合递归。

我的问题是如何测试这些算法的效率？实际上，我认为算法计算值所需的步骤数告诉了算法的效率。

我的三种算法代码：

import java.util.ArrayList;
public class ArraySumTester {

    static int steps = 1;

    public static void main(String[] args) {

        ArrayList<Integer> numList = new ArrayList<Integer>();

        numList.add(1);
        numList.add(2);
        numList.add(3);
        numList.add(4);
        numList.add(5);


        System.out.println("------------------------------------------");
        System.out.println("Recursive array sum = " + ArraySum(numList));

        System.out.println("------------------------------------------");
        steps = 1;
        System.out.println("Iterative array sum = " + iterativeSum(numList));

        System.out.println("------------------------------------------");
        steps = 1;
        System.out.println("Array sum using recursive array split : " + sumArraySplit(numList));

    }

    static int ArraySum(ArrayList<Integer> list) {
        return sumHelper(list, 0);
    }

    static int sumHelper(ArrayList<Integer> list, int start) {
        // System.out.println("Start : " + start);
        System.out.println("Rescursive step : " + steps++);
        if (start >= list.size())
            return 0;
        else
            return list.get(start) + sumHelper(list, start + 1);

    }

    static int iterativeSum(ArrayList<Integer> list) {
        int sum = 0;
        for (Integer item : list) {
            System.out.println("Iterative step : " + steps++);
            sum += item;
        }
        return sum;
    }

    static int sumArraySplit(ArrayList<Integer> list) {

        int start = 0;
        int end = list.size();
        int mid = (start + end) / 2;

        System.out.println("Rescursive step : " + steps++);
        //System.out.println("Start : " + start + ", End : " + end + ", Mid : " + mid);
        //System.out.println(list);

        if (list.size() <= 1)
            return list.get(0);
        else
            return sumArraySplit(new ArrayList<Integer>(list.subList(0, mid)))
                    + sumArraySplit(new ArrayList<Integer>(list.subList(mid,
                            end)));

    }
}

输出：

------------------------------------------
Rescursive step : 1
Rescursive step : 2
Rescursive step : 3
Rescursive step : 4
Rescursive step : 5
Rescursive step : 6
Recursive array sum = 15
------------------------------------------
Iterative step : 1
Iterative step : 2
Iterative step : 3
Iterative step : 4
Iterative step : 5
Iterative array sum = 15
------------------------------------------
Rescursive step : 1
Rescursive step : 2
Rescursive step : 3
Rescursive step : 4
Rescursive step : 5
Rescursive step : 6
Rescursive step : 7
Rescursive step : 8
Rescursive step : 9
Array sum using recursive array split : 15

现在，从上面的输出来看，递归数组拆分算法的步骤最多，但是根据我的说明，它和迭代算法一样高效。我的代码和笔记哪不正确？

Answer 1

你只想看看执行的速度吗？如果是这样的话，您将需要查看微基准测试：如何用Java编写正确的微基准测试？

本质上，因为JVM和现代处理器的工作方式，所以在FOR循环中运行一百万次并使用系统定时器(编辑)测量执行速度不会得到一致的结果。

也就是说，“效率”也可以意味着其他的东西，比如内存消耗。例如，任何递归方法都有堆栈溢出的风险，这个站点以:)命名的问题尝试给ArrayList提供数万个元素，看看会发生什么。

Answer 2

使用System.currentTimeMillis()是可行的。在代码之前定义一个start变量，在它完成后定义一个end变量。它们的不同之处在于您的程序执行所需的时间。最短的时间将是最有效的。

长启动= System.currentTimeMillis()；

//测试程序

长尾= System.currentTimeMillis()；长差=结束启动；

Answer 3

我建议您在抽象中查看这些算法的运行时间和空间复杂性(这些都是计算机科学名称，以表示效率)。这就是所谓的大字号的目的.

确切地说，当然，在使实现尽可能紧凑和无副作用之后，您应该考虑编写微基准。

由于您必须能够读取列表中每个元素的值，以便对这些元素进行求和，因此在一般情况下(即没有任何其他假设)，没有任何算法比(线性) O(n)时间、O(1)空间算法(这是您的迭代算法所做的)执行得更好。这里，n是输入的大小(即列表中的元素数)。这种算法据说具有线性时间和恒定的空间复杂度，这意味着它的运行时间随着列表大小的增加而增加，但它不需要任何额外的内存；实际上，它需要一些常量内存来完成它的工作。

其他两种递归算法充其量也能与这个简单的算法一样执行，因为迭代算法没有递归算法遇到的任何复杂问题(例如，堆栈上的额外内存)。

这反映在具有相同O(f(n))运行时间的算法的常量项中。例如，如果您以某种方式找到了一种算法，它可以检查列表中大约一半的元素来解决问题，而另一种算法必须查看所有元素，那么，第一种算法具有比第二种算法更好的常量项，并且在实践中有望超过它，尽管这两种算法的时间复杂度都为O(n)。

现在，通过将庞大的列表分割成更小的列表(您可以通过索引来实现这种效果)，然后使用并行求和操作，如果列表足够长，就可以并行处理这个问题的解决方案。这是因为每个不重叠的间隔都可以并行地进行求和(同时)，最后对部分总和进行求和。但在目前情况下，这不是我们正在考虑的可能性。