0

配列の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;
}
4

1 に答える 1

1

@Dcoderは確かに正しいですが、それQ - n%qは正しくありません。する必要がありますn%Q。さらに、計算size = (3*n)/4は信頼できません。ベクトルを指定してn = 6（確かに、実際には5であると仮定して）試してみてください。Q[1, 2, 3, 4, 5, 0]

すべての配列添え字の割り当てでインデックスの値をチェックするだけで、コードを多くの人が見ないようにすることができます（ただし、内部の割り当ては検出されませんでしたがqsort、以下で詳しく説明します）。

非常に多くのメモリを使用して単純な操作を実行していることに気付いたはずですが、実際にはその場で実行できます。通常、インプレース操作を回避する理由は、元のベクトルを保持する必要があるためですがqsort、インプレースで並べ替える中央値を計算しているため、元のベクトルは既に変更されています。それが許容できる場合は、残りの中央値の中央値アルゴリズムをインプレースで実行しない理由はありません。[1]

ちなみに、私は確かに浮動小数点計算を恐れる人ではありませんが、理由はまったくありませんcountSets = ceil(float(n)/float(Q))。(n + Q - 1)/Qうまく動作します。そのイディオムは、計算にも使用できたはずですが、そもそもsizeどこ3n/4から計算を取得したのかはまったくわかりません。

[注1]ヒント：連続してグループ化する代わりに、ベクトルを5つの領域に分割し、各領域のi番目の要素の中央値を見つけます。見つけたら、最初のリージョンのi番目の要素と交換します。それが完了すると、最初の領域（ベクトルの最初の5分の1）に中央値が含まれ、そのサブベクトルで再帰できます。つまり、実際には中央値のコードを一連の比較として書き出すことを意味します。これは面倒ですが、を呼び出すよりもはるかに高速ですqsort。これにより、前述の縮退したケースも回避されます。この場合、中央値の中央値の計算では、ベクトル内の最小の要素が誤って返されます。

于 2012-11-17T15:20:01.843 に答える