알고리즘 4th edition에서 자동 권투의 실험

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

첫 번째 예에서는 스택 개체 자체로 인해 많은 오버 헤드가 발생합니다. 박스형 프리미티브는 클래스를 느리게 만들지 만 고려해야 할 다른 병목 현상이 있습니다.

두 번째 예제에서는 오버 헤드가 거의 없으므로 boxed 프리미티브와 unboxed 프리미티브 간의 성능 차이가 훨씬 더 두드러집니다.