算法自动装箱实验第4版

Question

这是一个关于自动装箱的实验。主要思想是分别与 Stack 和 Stack<Integer> 一起执行 pop() 和 push() 的挂载。下面的核心class：

public class FixedCapcityStack<Item> {
    private final int cap;
    private Item[] arr;
    private int N;
    public FixedCapcityStack(int cap){
        this.cap = cap;
        arr = (Item[]) new Object[cap];
    }

    public void push(Item i){
        arr[N++] = i;
    }

    public Item  pop(){// 不考虑其他其他情况,方便测试
        return arr[--N];
    }

    public boolean isEmpty() {
        return N==0;
    }

    public boolean isFull() {
        return N == cap;
    }
}

public class FixedCapcityStackOfInts {
    private final int cap;
    private int[] arr;
    private int N;
    public FixedCapcityStackOfInts(int cap){
        this.cap = cap;
        arr = new int[cap];
    }

    public void push(int i){
        arr[N++] = i;
    }

    public int  pop(){// 不考虑其他其他情况,方便测试
        return arr[--N];
    }

    public boolean isEmpty() {
        return N==0;
    }

    public boolean isFull() {
        return N == cap;
    }
}

然后我用下面的代码来测试：

public static void main(String args[]) {
    Random random = new Random();
    int SIZE = 10;
    FixedCapcityStackOfInts intStack = new FixedCapcityStackOfInts(SIZE);
   //FixedCapcityStack<Integer> intStack = new FixedCapcityStack(SIZE);

    int N = 200;
    while (true) {
        Stopwatch stopwatch = new Stopwatch();
        for (int j = 0; j < N; j++) {
            for (int i = 0; i < SIZE; i++) {
                intStack.push(random.nextInt());
            }

            for (int i = 0; i < SIZE; i++) {
                int k = intStack.pop();
            }
        }
        System.out.printf("N: %d, elapseTime: %f \n", N, stopwatch.elapsedTime());
        N*=2;
    }
}

没有泛型的栈的结果是

N: 100, elapseTime: 0.033000s
N: 200, elapseTime: 0.026000s
N: 400, elapseTime: 0.025000s
N: 800, elapseTime: 0.047000s
N: 1600, elapseTime: 0.124000s
N: 3200, elapseTime: 0.238000s
N: 6400, elapseTime: 0.490000s
N: 12800, elapseTime: 0.731000s
N: 25600, elapseTime: 1.437000s
N: 51200, elapseTime: 2.951000s
N: 102400, elapseTime: 5.891000s
N: 204800, elapseTime: 11.810000s
N: 409600, elapseTime: 23.699000s
N: 819200, elapseTime: 46.441000s

Stack<Integer>的结果是：

N: 100, elapseTime: 0.034000s
N: 200, elapseTime: 0.018000s
N: 400, elapseTime: 0.049000s
N: 800, elapseTime: 0.053000s
N: 1600, elapseTime: 0.150000s
N: 3200, elapseTime: 0.251000s
N: 6400, elapseTime: 0.536000s
N: 12800, elapseTime: 0.885000s
N: 25600, elapseTime: 1.570000s
N: 51200, elapseTime: 3.181000s
N: 102400, elapseTime: 6.321000s
N: 204800, elapseTime: 12.923000s
N: 409600, elapseTime: 25.643000s
N: 819200, elapseTime: 51.373000s

表现还不错。但是当你使用下面的代码进行测试时：

long start = System.currentTimeMillis();
Long sum = 0L;
for (long i = 0; i < Integer.MAX_VALUE; i++) {
    sum += i;
}
long end = System.currentTimeMillis();
System.out.println("Long sum took: " + (end - start) + " milliseconds");

start  = System.currentTimeMillis();
long sum2 = 0L;
for (long i = 0; i <Integer.MAX_VALUE; i++) {
    sum2 += i;
}
end = System.currentTimeMillis();
System.out.println("long sum took: " + (end - start) + " milliseconds");

结果是：

 Long sum took: 8043 milliseconds
 long sum took: 793 milliseconds

天哪！为什么这两个结果彼此不同。当然，从这两个结果得出的关于自动装箱的结论也是不一样的。这让我很困惑。

Answer 1

在第一个示例中，堆栈对象本身造成了很多开销。盒装原语使 class 变慢，但还有其他瓶颈需要考虑。

在第二个示例中，开销非常小，使得装箱与未装箱原语之间的性能差异更加明显。

算法自动装箱实验第4版

the experiment of auto boxing in algorithms 4th edition

java

algorithm

autoboxing