3

下面是选择排名算法的一个实现，它用于查找数组中第 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)

我认为也许 rand() 导致了这个问题，但我不确定。我也不知道如何解决它。

4

3 回答 3

2

我假设您希望您的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-09T17:09:38.887 回答
1

StackOverflowError 的 Javadoc 说：

当由于应用程序递归太深而发生堆栈溢出时引发。

由于默认限制非常高，因此 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 行开始，rank 似乎无限地调用自身。让我们通过检查局部变量来验证这一点。对于第 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会用相同的参数调用自己，无限循环。

带回家留言：

  1. 在失败时检查程序的状态（例如使用调试器和断点）对于发现错误非常有用。
  2. 不要忽略极端情况。
于 2013-07-09T17:05:22.857 回答
1

递归永远不会结束，不是因为输入而是因为随机的使用，理论上随机可以每次都给你相同的数字。例如更改为：

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-09T16:24:16.640 回答