Java:测试数组求和算法的效率 [英] Java : Testing Array Sum Algorithm Efficiency

问题描述

我正在大学上一门Java课程，我的笔记为我提供了三种计算ArrayList之和的方法.第一次使用迭代，第二次使用递归，第三次使用数组拆分与递归相结合.

I am taking a Java course in university and my notes give me 3 methods for calculating the sum of an ArrayList. First using iteration, second using recursion, and third using array split combine with recursion.

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

My question is how do I test the efficiency of these algorithms? As it is, I think the number of steps it takes for the algorithm to compute the value is what tells you the efficiency of the algorithm.

我的3种算法的代码:

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

现在从上面的输出中，递归数组拆分算法采取了最多的步骤，但是根据我的笔记，它与迭代算法一样有效.那么我的代码或注释中哪些不正确?

Now from the above output the recursive array split algorithm takes the most steps, however according to my notes, it is as efficient as the iterative algorithm. So which is incorrect my code or my notes?

推荐答案

您是否只想查看执行速度?如果是这样，您将需要查看微基准测试: 如何在Java中编写正确的微基准?

Do you just want to look at speed of execution? If so, you'll want to look at microbenchmarking: How do I write a correct micro-benchmark in Java?

本质上是因为JVM和现代处理器的工作方式，通过在FOR循环中运行一百万次并使用系统计时器(EDIT)来测量执行速度，您将无法获得一致的结果.

Essentially because of how the JVM and modern processors work, you won't get consistent results by running something a million times in a FOR loop and measuring the execution speed with a system timer (EDIT).

也就是说，效率"还可以表示诸如内存消耗之类的其他内容.例如，任何递归方法都存在着堆栈溢出的风险，此站点以以下名称命名:)尝试给ArrayList数以万计的元素，然后看看会发生什么.

That said, "efficiency" can also mean other things like memory consumption. For instance, any recursive method runs a risk of a stack overflow, the issue this site is named after :) Try giving that ArrayList tens of thousands of elements and see what happens.

这篇关于Java:测试数组求和算法的效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！