選擇排名算法

下面是選擇排名算法的實現，該算法用於查找數組中第K個最小元素之前的元素。有時，這種計劃行之有效，但有時由於失敗堆棧溢出錯誤（錯誤下面的代碼片段）選擇排名算法

public static int rand(int left, int right){ 
    return left+(int)(Math.random()*(double)(right-left)); 
} 

public static int rank(int[] array, int left, int right, int rank){ 
    int pivot = rand(left, right); 
    int leftend = partition(array, left, right, array[pivot]); 

    int size = leftend - left +1; 
    if(size == rank+1){ 
     for(int i=0; i<=leftend; i++) 
     System.out.print(array[i]+" ,"); 
     return 0; 
    }else if(size > rank) 
     return rank(array, left, leftend, rank); 
    else return rank(array, leftend+1, right, rank - size); 

} 

public static int partition(int[] array, int left, int right, int pivot){ 
    while(true){ 
     while(left <= right && array[left] <= pivot) 
      left++; 

     while(right >= left && array[right] > pivot) 
     right--; 

     if(left > right) 
     return left-1; 

     int temp = array[left]; 
     array[left] = array[right]; 
     array[right] = temp; 
    } 

}

錯誤：

Exception in thread "main" java.lang.StackOverflowError 
    at java.util.Random.nextDouble(Random.java:409) 
    at java.lang.Math.random(Math.java:712) 
    at mod.rand(mod.java:12) 
    at mod.rank(mod.java:16) 
    at mod.rank(mod.java:25)

我想，也許蘭特（）是導致此問題，但我我不確定。我也不知道如何解決它。

來源

2013-07-09 city

沒有，很可能'等級（'這就是問題 – hexafraction

可能你的遞歸永遠不會結束 – Kostia

@Kostia你的意思是絕對的，你可以舉一個例子，說明它失敗了，這將使修復更容易，而不是找到我們自己的例子 – aaronman

我假設你想要你的rand方法返回一個介於左（含）和右（含）之間的數字。但是，Math.random（）方法會返回一個介於0.0（包含）和1.0（不包含）之間的數字。因此，在所評估的子陣列的大小爲2（即，left = 4和right = 5）的情況下，作爲結果，rand函數將僅能夠返回4。嘗試在rand函數變化這一行，以確保它可以包括上限：

return left+(int)(Math.random()*(double)(right-left));

爲

return left+(int)(Math.random()*(double)(right-left + 1));

來源

2013-07-09 17:09:38 ZePoLiTaT

是的，我發現了這個問題。感謝任何方式〜 – city

遞歸永不結束不是因爲輸入，而是因爲隨機使用，理論上隨機的使用可以給你每次相同的數字。例如更改爲：

public static int rand(int left, int right) 
{ 
    return right - 1; 
}

嘗試在輸入：

int[] array= {1,2,11,67,35}; 
rank(array, 0, 4, 2);

，你會得到java.lang.StackOverflowError在這個輸入，因爲遞歸永遠不會結束。

來源

2013-07-09 16:24:16 Kostia

爲什麼4而不是'left'？ 4甚至不能保證[左，右]。 –

...對於真正的隨機數，這種引起堆棧溢出所需的數千次的概率是（即使只有兩種選擇是可能的）<2^-1000。這個概率如此接近於零，更有可能是宇宙射線在計算機存儲器中翻轉一點導致失敗（是的，「random」是一個單純的僞隨機生成器，但它的分佈非常接近uniform。 *不*保持返回相同的號碼）。 – meriton

問題是我沒有處理在子數組中只有兩個元素的情況，而不像你說的那樣。 – city

的StackOverflowError的Javadoc中說：

Thrown when a stack overflow occurs because an application recurses too deeply.

由於默認的限制是相當高的，一個通常的StackOverflowError表示無限遞歸。

爲了有效地診斷這些錯誤，請使用帶有調試支持的體面的IDE，爲StackOverflowError設置異常斷點，運行程序並檢查堆棧中的局部變量，一旦命中斷點。

這樣做，在這裏，我們得到以下堆棧：

Random.nextDouble() line: 444 [local variables unavailable] 
Math.random() line: 716 
Test.rand(int, int) line: 5 
Test.rank(int[], int, int, int) line: 9 
Test.rank(int[], int, int, int) line: 18  
Test.rank(int[], int, int, int) line: 18  
Test.rank(int[], int, int, int) line: 18  
Test.rank(int[], int, int, int) line: 18  
Test.rank(int[], int, int, int) line: 18  
Test.rank(int[], int, int, int) line: 18  
Test.rank(int[], int, int, int) line: 18  
Test.rank(int[], int, int, int) line: 18  
Test.rank(int[], int, int, int) line: 18  
Test.rank(int[], int, int, int) line: 18  
Test.rank(int[], int, int, int) line: 18  
Test.rank(int[], int, int, int) line: 18  
Test.rank(int[], int, int, int) line: 18  
...

這樣看來，排名調用本身循環往復從18行讓我們通過檢查局部變量驗證這一點。在管線18中的最上面的堆棧幀：

left 97 
right 107 
rank 5 
pivot 102 
leftend 107 
size 11

爲一個它下面：

left 97 
right 107 
rank 5 
pivot 101 
leftend 107 
size 11

爲低於

left 97 
right 107 
rank 5 
pivot 105 
leftend 107 
size 11

實際上，一個，left和right在這些相同堆棧幀，即算法已停止進展。我們也看到，即使每次選擇不同的樞軸指數，leftend仍然等於right。

看問題的數組索引，我們可以看到：

[97] 10 
[98] 10 
[99] 10 
[100] 10 
[101] 10 
[102] 10 
[103] 10 
[104] 10 
[105] 10 
[106] 10 
[107] 10

這看起來像你沒有處理，其中在小範圍的所有元素都是平等的正確的特殊情況。

事實上，看代碼，我們看到partition總是在這樣的情況下返回right和rank將調用自身以相同的參數，遞歸循環往復。

帶回家的消息：

在失敗的那一刻檢查程序的狀態（例如使用調試器和突破點），在查找錯誤是非常有用的。
不要忽視轉角情況。

來源

2013-07-09 17:05:22 meriton

選擇排名算法

回答

相關問題