Java中的堆棧問題

Question

我在java中使用堆棧時遇到了一些問題...我使用ArrayList實現快速排序 - 我將在最後附上我的完整代碼，但以下是相關的部分（請牢記我已經調試了幾個小時，完全不知道出了什麼問題，所以如果你看到事情以奇怪的方式完成，那很可能是因爲我試圖檢查那裏的錯誤）：

那顯然是正在執行的調用次數過多：

  QuickSort(numArray, m+1, right); 

在這裏失敗：

//Swap pivot and left 
     numArray.set(pivot, leftVal); 

我得到的輸出：

Starting sort number: [1] : RandomPivot [ON] : Sorting [RANDOM] 
Sorted: 2496 elements. 
Took: 53 milliseconds. 

Starting sort number: [2] : RandomPivot [ON] : Sorting [RANDOM] 
Sorted: 4988 elements. 
Took: 25 milliseconds. 

Starting sort number: [3] : RandomPivot [ON] : Sorting [RANDOM] 
Sorted: 7478 elements. 
Took: 49 milliseconds. 

Starting sort number: [4] : RandomPivot [ON] : Sorting [RANDOM] 
Sorted: 9953 elements. 
Took: 85 milliseconds. 

Starting sort number: [5] : RandomPivot [ON] : Sorting [RANDOM] 
Sorted: 12416 elements. 
Took: 131 milliseconds. 

Starting sort number: [1] : RandomPivot [ON] : Sorting [SORTED] 
Sorted: 2497 elements. 
Took: 1 milliseconds. 

Starting sort number: [2] : RandomPivot [ON] : Sorting [SORTED] 
Sorted: 4984 elements. 
Took: 1 milliseconds. 

Starting sort number: [3] : RandomPivot [ON] : Sorting [SORTED] 
Sorted: 7482 elements. 
Took: 2 milliseconds. 

Starting sort number: [4] : RandomPivot [ON] : Sorting [SORTED] 
Sorted: 9950 elements. 
Took: 2 milliseconds. 

Starting sort number: [5] : RandomPivot [ON] : Sorting [SORTED] 
Sorted: 12424 elements. 
Took: 2 milliseconds. 

Starting sort number: [1] : RandomPivot [ON] : Sorting [REVERSE SORTED] 
Sorted: 2494 elements. 
Took: 2 milliseconds. 

Starting sort number: [2] : RandomPivot [ON] : Sorting [REVERSE SORTED] 
Sorted: 4988 elements. 
Took: 10 milliseconds. 

Starting sort number: [3] : RandomPivot [ON] : Sorting [REVERSE SORTED] 
Sorted: 7470 elements. 
Took: 35 milliseconds. 

Starting sort number: [4] : RandomPivot [ON] : Sorting [REVERSE SORTED] 
Sorted: 9962 elements. 
Took: 50 milliseconds. 

Starting sort number: [5] : RandomPivot [ON] : Sorting [REVERSE SORTED] 
Sorted: 12419 elements. 
Took: 65 milliseconds. 

Starting sort number: [1] : RandomPivot [OFF] : Sorting [RANDOM] 
Sorted: 2497 elements. 
Took: 5 milliseconds. 

Starting sort number: [2] : RandomPivot [OFF] : Sorting [RANDOM] 
Sorted: 4984 elements. 
Took: 54 milliseconds. 

Starting sort number: [3] : RandomPivot [OFF] : Sorting [RANDOM] 
Sorted: 7473 elements. 
Took: 47 milliseconds. 

Starting sort number: [4] : RandomPivot [OFF] : Sorting [RANDOM] 
Sorted: 9958 elements. 
Took: 80 milliseconds. 

Starting sort number: [5] : RandomPivot [OFF] : Sorting [RANDOM] 
Sorted: 12419 elements. 
Took: 130 milliseconds. 

Starting sort number: [1] : RandomPivot [OFF] : Sorting [SORTED] 
Sorted: 2498 elements. 
Took: 11 milliseconds. 

Starting sort number: [2] : RandomPivot [OFF] : Sorting [SORTED] 
Sorted: 4991 elements. 
Took: 44 milliseconds. 

Starting sort number: [3] : RandomPivot [OFF] : Sorting [SORTED] 
Sorted: 7474 elements. 
Took: 97 milliseconds. 

Starting sort number: [4] : RandomPivot [OFF] : Sorting [SORTED] 
Exception in thread "main" java.lang.StackOverflowError 
at java.util.ArrayList.set(Unknown Source) 
at Sorter.QuickSort(Sorter.java:64) 
at Sorter.QuickSort(Sorter.java:107) 
at Sorter.QuickSort(Sorter.java:107) 
at Sorter.QuickSort(Sorter.java:107) 
at Sorter.QuickSort(Sorter.java:107) 
    (on and on and on and on) 

測試，一旦我得到過去〜7500作爲我的ArrayList的大小，它總是失敗。總是在「ArrayList.set（）」失敗，我對此毫無頭緒。正如你所看到的那樣 - 所有其他的排序類型都可以在這個數量上正常工作，但是對於排序列表，我必須n次調用「m + 1，right」，其中n是列表的大小。

我已經試過這樣：

if(m-1>left && m-1<right) 
     QuickSort(numArray, left, m-1); 
    if(m+1<right && m+1>left) 
     QuickSort(numArray, m+1, right); 

，但我得到了同樣的錯誤無論哪種方式，我想它更容易，如果它離開了理解。

如果我可以增加堆棧大小，不知何故，我可能會推遲錯誤，這將允許我至少分析不同的方法。

我通過eclipse運行這段代碼，如果這有什麼區別。謝謝！ （現在的完整代碼）

import java.util.ArrayList; 
import java.util.HashSet; 
import java.util.Random; 
import java.util.Set; 
import java.util.TreeSet; 


public class Sorter { 

//STATE: 
public boolean test=false; 
public boolean randomPivot=false; 
Random r = new Random(); 
public int sortMethod=1; 

public static int RANDOM=1; 
public static int SORTED=2; 
public static int REVERSE_SORTED=3; 


public Sorter(){ } 


public ArrayList<Integer> SlowSort(ArrayList<Integer> numArray){ 

    //Add "infinity" to the end 
    numArray.add(Integer.MAX_VALUE); 


    //TIME AND RUN QUICKSORT 
    long startTime = System.currentTimeMillis(); 
    numArray=QuickSort(numArray, 0, numArray.size()-2); 
    long stopTime = System.currentTimeMillis(); 
    long runTime = stopTime - startTime; 

    //Remove "infinity" from the end 
    numArray.remove(numArray.size()-1); 

    //TODO: Printing effs it up? idk 
    //  printArrayWithMessage("Sort Finished.", numArray); 

    //PRINT COMPLETION MESSAGE AND RETURN 
    System.out.println("Sorted: "+numArray.size()+" elements.\nTook: " + runTime+" milliseconds.\n"); 
    return numArray; 
} 


public ArrayList<Integer> QuickSort(ArrayList<Integer> numArray, int left, int right){ 
    if(left>=right){ 
     return numArray; 
    } 

    //Correctly Initialize Pivot 
    int pivot=0; 
    if(randomPivot){ 
     pivot = r.nextInt(right-left); 
    } 
    pivot+=left; 

    //Swap pivot and left 
    Integer temp = numArray.get(pivot); 
//  System.out.println(numArray.size()+" "+pivot); 
    int leftVal=numArray.get(left); 
    numArray.set(pivot, leftVal); 
    pivot=temp; 
    numArray.set(left, pivot); 

    Integer m=0; 

    //REPEAT: 
    while(true){ 
     int i=left+1; 
     int j=right+1; 

     while(numArray.get(i).intValue()<pivot){ 
      i++; 
     } 
     while(numArray.get(j).intValue()>pivot){ 
      j--; 
     } 

     if(i<j){ 
      //Swap i and j 
      if(test) printArrayWithMessage("[SWAP] (i="+i+") and (j="+j+")", numArray); 

      Integer a=numArray.get(i); 
      numArray.set(i, numArray.get(j)); 
      numArray.set(j, a); 
     } 

     if(i>j){ 
      //Swap pivot and j 
      if(test) printArrayWithMessage("[SWAP] (j="+j+") and (pivot="+left+")", numArray); 

      numArray.set(left, numArray.get(j)); 
      numArray.set(j, pivot); 
      m=j; 

      break; 
     } 
    } 

    if(test) printArrayWithMessage("Iteration Finished... Left: "+left+" Right: "+right, numArray); 


     QuickSort(numArray, left, m-1); 
     QuickSort(numArray, m+1, right); 

    return numArray; 
} 

public void benchmark(){ 

    for(int i=1;i<6;i++){ 
     //CREATE BLANK DATA STRUCTURES 
     ArrayList<Integer> numList = new ArrayList<Integer>(); 
     Set<Integer> doublesFilter; 

     if(sortMethod==RANDOM){ 
      doublesFilter = new HashSet<Integer>(); 
     }else{ 
      doublesFilter = new TreeSet<Integer>(); 
     } 
     //FILL ARRAYLIST WITH UNIQUE NUMBERS 
     for(int j=0;j<2500*i;j++){ 
      int num=r.nextInt(1000000); 
      if(doublesFilter.add(num)){ 
       if(sortMethod==RANDOM){ 
        numList.add(num); 
       } 
      } 
     } 
     if(sortMethod==SORTED){ 
      numList.add(0); 
      numList.ensureCapacity(doublesFilter.size()); 
      numList.addAll(doublesFilter); 
      numList.remove(0); 
     } 
     else if(sortMethod==REVERSE_SORTED){ 
      numList.add(0); 
      numList.ensureCapacity(doublesFilter.size()); 
      numList.addAll(((TreeSet<Integer>) doublesFilter).descendingSet()); 
      numList.remove(0); 
     } 


     System.out.println("Starting sort number: ["+i+"] : "+getMode()); 
     numList=SlowSort(numList); 
    } 
} 


public void printArrayWithMessage(String s, ArrayList<Integer> list){ 
    System.out.println(s); 
    System.out.println(list); 
    System.out.println(); 
} 

public String getMode(){ 

    String rPivot="OFF"; 
    if(randomPivot) rPivot="ON"; 


    String sortMode="UNDEFINED"; 
    if(sortMethod==1)sortMode="RANDOM"; 
    if(sortMethod==2)sortMode="SORTED"; 
    if(sortMethod==3)sortMode="REVERSE SORTED"; 

    return "RandomPivot ["+rPivot+"] : "+"Sorting ["+sortMode+"]"; 
} 

} 

Answer 1

如你所指出的，具有快速排序時提供一個排序後的數組，並最終使O（n）的遞歸調用，因爲分區僅刪除在每個細分步驟一種元素最壞的情況下的性能。在數組未被排序的其他情況下，分區更加有效，因此您最終會收到O（lgN）遞歸調用。 O（n）遞歸調用超過O（lgN）調用不會的最大堆棧幀數。

編輯（附加說明）： 在快速排序中使用隨機數據透視的好處和意圖之一是確保分區/子問題的大小是O（n）而不是O（1）在最壞的情況下的行爲後一種情況（沒有隨機數據庫+排序輸入）就是你看到堆棧溢出錯誤的地方。

Answer 2

遞歸實現總是會在「正確」情況下（即大數據集）產生一個stackoverflow。另外，看看一些回答類似的問題：

Got stackoverflowerror when using quickSort, can I increase the stack and the heap?

Some issues in implementing QuickSort in java