Java'nın Toplama Yığını veri yapısının verimliliği

Question

Bugün Java'da ArrayList kullanarak Yığın veri yapısını uygulamak için kod yazıyordum. Koleksiyonumdaki Stack kütüphanesine karşı uygulanan Stack I'in verimliliğini karşılaştırmak için kodumu genişlettim ve sonuç bana biraz şaşırdı. Demek istediğim, kodumun çok daha az verimli olacağından emindim ama basit kodumun daha iyi performans gösterdiği birçok durum vardı (eğer doğru anladıysam). Yazdığım kod aşağıdadır: - Aşağıdaki

import java.util.ArrayList; 
import java.util.List; 
import java.util.Random; 
import java.util.Stack; 

import customexceptions.StackUnderflowException; 

public class StackArray<T> { 
    private int top=-1; 
    private List<T> array = new ArrayList<T>(); 

    public void push(T object) { 
     array.add(object); 
     top++; 
    } 

    public T pop() throws StackUnderflowException { 
     if (top == -1) { 
      throw new StackUnderflowException(); 
     } 
     return array.remove(top--); 
    } 

    public T peek() throws StackUnderflowException { 
     if (top == -1) { 
      throw new StackUnderflowException(); 
     } 
     return array.get(top); 
    } 

    public boolean isEmpty() { 
     return top == -1; 
    } 

    public static void main(String[] args) throws StackUnderflowException { 
     Random random = new Random(); 
     for (int pow=1; pow<25; pow++) { 
      StackArray<Integer> intStack = new StackArray<>(); 
      int size = 1<<pow; 
      int i; 
      int randomInt = random.nextInt(10); 
      long startTime = System.currentTimeMillis(); 
      for(i=1; i<=size; i++) { 
       intStack.push(i * randomInt); 
      } 
      i--; 

      while(!intStack.isEmpty()) { 
       int popedValue = intStack.pop(); 
       assert popedValue == (i * randomInt); 
       i--; 
      } 
      assert i == 0; 
      intStack = null; 
      long endTime = System.currentTimeMillis(); 
      System.out.println("Time taken StackArray for 2^" + pow 
        + " ints = " + (endTime - startTime) + " ms") ; 

      randomInt = random.nextInt(10); 
      startTime = System.currentTimeMillis(); 
      Stack<Integer> collectionStack = new Stack<>(); 
      for(i=1; i<=size; i++) { 
       collectionStack.push(i * randomInt); 
      } 
      i--; 

      while(!collectionStack.isEmpty()) { 
       int popedValue = collectionStack.pop(); 
       assert popedValue == (i * randomInt); 
       i--; 
      } 
      assert i == 0; 
      endTime = System.currentTimeMillis(); 
      System.out.println("Time taken by Collection Stack for 2^" + 
        pow + " int = " + (endTime - startTime) + " ms"); 
     } 
    } 
} 

Ve I aynı için aldığım çıkışı: - Yukarıdaki örnekte

Time taken StackArray for 2^1 ints = 0 ms 
Time taken by Collection Stack for 2^1 int = 0 ms 
Time taken StackArray for 2^2 ints = 0 ms 
Time taken by Collection Stack for 2^2 int = 0 ms 
Time taken StackArray for 2^3 ints = 0 ms 
Time taken by Collection Stack for 2^3 int = 0 ms 
Time taken StackArray for 2^4 ints = 0 ms 
Time taken by Collection Stack for 2^4 int = 0 ms 
Time taken StackArray for 2^5 ints = 1 ms 
Time taken by Collection Stack for 2^5 int = 0 ms 
Time taken StackArray for 2^6 ints = 0 ms 
Time taken by Collection Stack for 2^6 int = 0 ms 
Time taken StackArray for 2^7 ints = 0 ms 
Time taken by Collection Stack for 2^7 int = 0 ms 
Time taken StackArray for 2^8 ints = 0 ms 
Time taken by Collection Stack for 2^8 int = 1 ms 
Time taken StackArray for 2^9 ints = 0 ms 
Time taken by Collection Stack for 2^9 int = 1 ms 
Time taken StackArray for 2^10 ints = 0 ms 
Time taken by Collection Stack for 2^10 int = 1 ms 
Time taken StackArray for 2^11 ints = 0 ms 
Time taken by Collection Stack for 2^11 int = 1 ms 
Time taken StackArray for 2^12 ints = 2 ms 
Time taken by Collection Stack for 2^12 int = 1 ms 
Time taken StackArray for 2^13 ints = 3 ms 
Time taken by Collection Stack for 2^13 int = 3 ms 
Time taken StackArray for 2^14 ints = 5 ms 
Time taken by Collection Stack for 2^14 int = 5 ms 
Time taken StackArray for 2^15 ints = 3 ms 
Time taken by Collection Stack for 2^15 int = 7 ms 
Time taken StackArray for 2^16 ints = 9 ms 
Time taken by Collection Stack for 2^16 int = 15 ms 
Time taken StackArray for 2^17 ints = 12 ms 
Time taken by Collection Stack for 2^17 int = 22 ms 
Time taken StackArray for 2^18 ints = 7 ms 
Time taken by Collection Stack for 2^18 int = 21 ms 
Time taken StackArray for 2^19 ints = 16 ms 
Time taken by Collection Stack for 2^19 int = 51 ms 
Time taken StackArray for 2^20 ints = 28 ms 
Time taken by Collection Stack for 2^20 int = 94 ms 
Time taken StackArray for 2^21 ints = 58 ms 
Time taken by Collection Stack for 2^21 int = 201 ms 
Time taken StackArray for 2^22 ints = 111 ms 
Time taken by Collection Stack for 2^22 int = 318 ms 
Time taken StackArray for 2^23 ints = 2338 ms 
Time taken by Collection Stack for 2^23 int = 2189 ms 
Time taken StackArray for 2^24 ints = 5940 ms 
Time taken by Collection Stack for 2^24 int = 3748 ms 

Yığın benim algoritması nereye götürdüğünü pek çok durumlarda bulabilirsiniz itme ve haşhaş işleminde daha az zaman. Bunun için belirli bir nedeni var mı? Yoksa bu kararsız bir sonuç mu? Ya da Koleksiyon kütüphanesinde iyileştirme alanı olabilir mi? Stack parçacığı güvenlidir ve uygulamada değil, bu yüzden size sınıfta yok sınıfta Stack sahip senkronizasyon kilitleri tarafından eklenen ek yük var çünkü

Answer 1

Kişisel uygulanması daha hızlı basitçe. Stack'daki