算法4版中的自动装箱实验

Question

这是一个关于自动拳击的实验.其主要思想是执行pop()和push()的挂载，分别使用Stack和Stack<Integer>。核心班如下：

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

在第一个例子中，堆栈对象本身造成了大量开销。装箱原语使类变慢，但还有其他瓶颈需要考虑。

在第二个例子中，开销非常小，这使得盒式原语和非盒式原语之间的性能差异更加明显。