Java中的堆栈问题(Stack problems in Java)
我在java中的堆栈有一些问题...我正在使用ArrayList实现quicksort-我会在最后附上我的完整代码，但这里是相关的部分（请记住我一直在调试地狱这几个小时完全不知道出了什么问题，所以你看到以奇/ /等方式完成的事情很可能是因为我试图检查那里的错误）：
显然执行的呼叫次数过多：
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（）”失败，我没有丝毫的线索为什么。 正如你所看到的 - 所有其他排序类型的数量都超过了这个数量，但是对于排序列表，我将不得不调用“m + 1，右”n次，其中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+"]"; } }I'm having some problems with the stack in java... I'm implementing quicksort using an ArrayList- I'll attach my full code at the end but here are the relevant bits (Keep in mind I've been debugging the hell out of this for a few hours with absolutely no clue what was going wrong, so where you see things done in odd/etc ways it's more than likely because I was trying to check for bugs there):
The call that is apparently being executed too many times:
QuickSort(numArray, m+1, right);It fails here:
//Swap pivot and left numArray.set(pivot, leftVal);I'm getting output:
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)Testing and it always fails once I get past ~7500 as the size of my ArrayList. Always fails at "ArrayList.set()" and I haven't the slightest clue as to why. As you can see- all other sorted types work fine with numbers over this amount, but with the sorted list I will have to call "m+1, right" n times, where n is the size of the list.
I've tried this:
if(m-1>left && m-1<right) QuickSort(numArray, left, m-1); if(m+1<right && m+1>left) QuickSort(numArray, m+1, right);but I get the same error either way, and I figured it's easier to understand if it's left out.
If I can increase the stack size, somehow, I might be able to postpone the error, which would allow me to at least analyze the different methods.
I'm running this code via eclipse, if that makes any difference. Thanks! (Full code now)
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+"]"; } }更多推荐
发布评论