4

私がすでに理解していること

Median of medians アルゴリズム (MoM と表記します) は、高定数係数 O(N) アルゴリズムであることを理解しています。k グループ (通常は 5) の中央値を見つけ、それらを次の反復のセットとして使用して中央値を見つけます。これを見つけた後のピボットは、元のセットの 3/10n から 7/10n の間になります。ここで、n は、1 つの中央値ベース ケースを見つけるのにかかった反復回数です。

MoM でこのコードを実行すると、セグメンテーション エラーが発生し続けますが、その理由はわかりません。私はそれをデバッグしましたが、問題は私が呼び出しているという事実にあると信じていますmedianOfMedian(medians, 0, medians.size()-1, medians.size()/2);。しかし、それ自体を呼び出して再帰的に中央値を見つけることになっていたので、これは論理的に正しいと思いました。おそらく私の基本的なケースは正しくありませんか？YouTube の YogiBearian によるチュートリアル (スタンフォード大学の教授、リンク: https://www.youtube.com/watch?v=YU1HfMiJzwg ) で、彼は O(N/5) を処理するための追加の基本ケースについて述べていません。 MoM での再帰の操作。

完全なコード

注: 提案に従って、基本ケースを追加し、ベクターで .at() 関数を使用しました。

static const int GROUP_SIZE = 5;
/* Helper function for m of m. This function divides the array into chunks of 5 
 * and finds the median of each group and puts it into a vector to return.
 * The last group will be sorted and the median will be found despite its uneven size.
 */
vector<int> findMedians(vector<int>& vec, int start, int end){
    vector<int> medians;
    for(int i = start; i <= end; i+= GROUP_SIZE){
        std::sort(vec.begin()+i, min(vec.begin()+i+GROUP_SIZE, vec.end()));
        medians.push_back(vec.at(min(i + (GROUP_SIZE/2), (i + end)/2)));
    }
    return medians;
}

/* Job is to partition the array into chunks of 5(subject to change via const)
 * And then find the median of them. Do this recursively using select as well.
 */
int medianOfMedian(vector<int>& vec, int start, int end, int k){
    /* Acquire the medians of the 5-groups */
    vector<int> medians = findMedians(vec, start, end);

    /* Find the median of this */
    int pivotVal;
    if(medians.size() == 1)
        pivotVal = medians.at(0);
    else
        pivotVal = medianOfMedian(medians, 0, medians.size()-1, medians.size()/2);

    /* Stealing a page from select() ... */
    int pivot = partitionHelper(vec, pivotVal, start, end);

    cout << "After pivoting with the value " << pivot << " we get : " << endl;
    for(int i = start; i < end; i++){
        cout << vec.at(i) << ", ";
    }
    cout << "\n\n" << endl;
    usleep(10000);
    int length = pivot - start + 1;
    if(k < length){
        return medianOfMedian(vec, k, start, pivot-1);
    }
    else if(k == length){
        return vec[k];
    }
    else{
        return medianOfMedian(vec, k-length, pivot+1, end);
    }

}

単体テストを支援するためのいくつかの追加機能

これらの 2 つの関数に対して作成した単体テストを次に示します。うまくいけば、彼らは助けてくれます。

vector<int> initialize(int size, int mod){
    int arr[size];
    for(int i = 0; i < size; i++){
    arr[i] = rand() % mod;
    }
    vector<int> vec(arr, arr+size);
    return vec;
}

/* Unit test for findMedians */
void testFindMedians(){
    const int SIZE = 36;
    const int MOD = 20;
    vector<int> vec = initialize(SIZE, MOD);
    for(int i = 0; i < SIZE; i++){
        cout << vec[i] << ", ";
    }
    cout << "\n\n" << endl;

    vector<int> medians = findMedians(vec, 0, SIZE-1);

    cout << "The 5-sorted version: " << endl;
    for(int i = 0; i < SIZE; i++){
        cout << vec[i] << ", ";
    }
    cout << "\n\n" << endl;

    cout << "The medians extracted: " << endl;
    for(int i = 0; i < medians.size(); i++){
        cout << medians[i] << ", ";
    }
    cout << "\n\n" << endl;
}

/* Unit test for medianOfMedian */
void testMedianOfMedian(){
    const int SIZE = 30;
    const int MOD = 70;
    vector<int> vec = initialize(SIZE, MOD);
    cout << "Given array : " << endl;
    for(int i = 0; i < SIZE; i++){
        cout << vec[i] << ", ";
    }
    cout << "\n\n" << endl;
    int median = medianOfMedian(vec, 0, vec.size()-1, vec.size()/2); 
    cout << "\n\nThe median is : " << median << endl;

    cout << "As opposed to sorting and then showing the median... : " << endl;
    std::sort(vec.begin(), vec.end());
    cout << "sorted array : " << endl;
    for(int i = 0; i < SIZE; i++){
        if(i == SIZE/2)
            cout << "**";
        cout << vec[i] << ", ";
    }
    cout << "Median : " << vec[SIZE/2] << endl;
}

取得している出力に関する追加セクション

Given array :
7, 49, 23, 48, 20, 62, 44, 8, 43, 29, 20, 65, 42, 62, 7, 33, 37, 39, 60, 52, 53, 19, 29, 7, 50, 3, 69, 58, 56, 65,

After pivoting with the value 5 we get :
23, 29, 39, 42, 43,

After pivoting with the value 0 we get :
39,

Segmentation Fault: 11

セグメンテーション違反までは、大丈夫でダンディに見えます。私のパーティション関数も同様に機能すると確信しています（リートコードの質問の実装の1つでした）。

免責事項: これは宿題の問題ではなく、leetcode 問題セットで quickSelect を使用した後のアルゴリズムに関する私自身の好奇心です。

提案された質問で MVCE についてさらに詳しく説明する必要がある場合はお知らせください。ありがとうございます。

編集:コードで再帰パーティションスキームが間違っていることがわかりました。プラダンが指摘したように、私はどういうわけか、開始と終了がそれぞれ0と-1になる空のベクトルを持っているため、それを呼び出す無限ループからセグメンテーション違反が発生します。まだこの部分を理解しようとしています。

4

2 に答える 2

3

MoM は常に( を計算するためにpivot) 自分自身を呼び出すため、無限再帰を示します。これは、再帰アルゴリズムの「基本指令」に違反しています。ある時点で、問題が「小さい」ため、再帰呼び出しが必要ありません。

于 2016-06-19T00:21:00.077 に答える