在递归函数中释放内存时发生堆损坏

我正在实现一种算法来选择数组的第K个最小元素。到目前为止，当我试图免费堆内存我得到这个错误：CRT检测应用程序堆缓冲区结束后写信给记忆......在递归函数中释放内存时发生堆损坏

int SEQUENTIAL_SELECT(int *S , int k , int n) 
{ 
    if(n<=Q) // sort S and return the kth element directly 
    { 
     qsort(S,n,sizeof(int),compare); 
     return S[k]; 
    } 
    // subdivide S into n/Q subsequences of Q elements each 
    int countSets = ceil((float)n/(float)Q); 

    //sort each subsequnce and determine its median 
    int *medians = new int[countSets]; 
    for(int i=0;i<countSets;i++) 
    { 
     if(i==countSets-1) 
     { 
      int size = Q - (n%Q); 
      qsort(&S[Q*i],size,sizeof(int),compare); 
      medians[i] = S[i*Q+size/2]; 
      continue; 
     } 
     qsort(&S[Q*i],Q,sizeof(int),compare); 
     medians[i] = S[i*Q+Q/2]; 
    } 

    // call SEQUENTIAL_SELECT recursively to find median of medians 
    int m = SEQUENTIAL_SELECT(medians,countSets/2,countSets); 
    delete[] medians; 
    int size = (3*n)/4; 

    int* s1 = new int[size]; // contains values less than m 
    int* s3 = new int[size]; // contains values graten than m 

    for(int i=0;i<size;i++) 
    { 
     s1[i] = INT_MAX; 
     s3[i] = INT_MAX; 
    } 
    int i1=0; 
    int i2=0; 
    int i3=0; 
    for(int i=0;i<n;i++) 
    { 
     if(S[i]>m) 
      s3[i3++] = S[i]; 
     else if(S[i]<m) 
      s1[i1++] = S[i]; 
     else 
      i2++; // count number of values equal to m 
    } 

    if(i1>=k) 
     m = SEQUENTIAL_SELECT(s1,k,i1); 
    else if(i1+i2+i3 >= k) 
     m = SEQUENTIAL_SELECT(s3,k-i1-i2,i3); 


    delete[] s3; 
    delete[] s1; 

    return m; 
}

来源

2012-11-17 nasir

**其中**错误是否完全发生？尝试在'valgrind'或类似的内存调试器中运行应用程序。 –

为什么使用'new int []'而不是'std :: vector '？（编辑：行'int size = Q - （n％Q）;'看起来对我不正确。） – DCoder

我想在CUDA程序中使用这个函数，很遗憾，你不能在CUDA内核中使用std :: vector – nasir

@Dcoder肯定是正确的，Q - n%q不正确。它应该是n%Q。另外，计算size = (3*n)/4不可靠;在n = 6（假设，似乎确定的情况下，Q实际上是5）尝试使用向量[1, 2, 3, 4, 5, 0]。

你可以通过简单地检查每个数组下标赋值处的索引值来避免大量的眼睛看着你的代码（尽管这不会捕获qsort内部的任务，但更多的在下面）。

它肯定发生在你身上，你正在使用大量的内存来执行一个简单的操作，事实上它可以在原地完成。通常，避免进行就地操作的原因是您需要保留原始矢量，但是您计算的中位数是qsort，它们就地排序，因此原始矢量已被修改。如果这是可以接受的，那么没有理由不在原地执行中位数中值算法的其余部分。 [1]

顺便说一句，虽然我当然不是那些担心浮点运算的人，但根本没有理由为countSets = ceil(float(n)/float(Q))。 (n + Q - 1)/Q将工作得很好。这个习语也可以用于计算size，尽管我并不确定你从哪里得到3n/4计算。

[注1]提示：代替连续分组，划分向量为五个区域，找到每个区域的第i个^元件的中值。一旦找到它，将它与第一个区域的元素交换;一旦完成，您的第一个区域 - 矢量的前五分之一 - 包含中值，您可以在该子矢量上进行递归。这意味着实际上将中间代码编写为一系列比较，这比单调乏味，但要比致电qsort快得多。这也避免了上面提到的退化情况，其中中值计算错误地返回了向量中的最小元素。

来源

2012-11-17 15:20:01 rici

在递归函数中释放内存时发生堆损坏

回答

相关问题