c++ - 为什么我的中位数中位数快速选择算法段错误？

Question

我很难找到我的代码中的错误，该错误会导致中位数快速选择算法的中位数在输入量适中时出现段错误。当我得到输出时，输出是正确的。以下是使用给定测试参数在我的系统上造成段错误的完整代码。

#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>

using namespace std;

void swap(vector<int> &A, const uint &index1, const uint &index2)
{
    int temp = A.at(index1);
    A.at(index1) = A.at(index2);
    A.at(index2) = temp;
}

void insertionSort(vector<int> &A, const int &begin, const int &end)
{
    // Begin inner loop from each element
    for(int i=begin; i<end; i++)
    {
        // If current item is smaller than the next, swap them.
        for(int j=i; j>begin && A.at(j-1)>A.at(j); j--)
        {
            swap(A, j, j-1);
        }
    }
}

int partition(vector<int> &A, const int &begin, const int &end, const int &pivot)
{
    int left = begin, right = end - 1;
    while(left<right)
    {
        while(A.at(left)<pivot && left<=right)
        {
            left++;
        }
        while(A.at(right)>pivot && right>=left)
        {
            right--;
        }

        if(left>=right)
        {
            break;
        }
        else if(A.at(left)==A.at(right))
        {
            left++;
            continue;
        }

        swap(A, left, right);
    }
    return --left;
}

int linearSelect(vector<int> &A, const int &begin, const int &end, const int &k, const int &groupSize)
{
    int elements = (end-begin),
        numOfGroups = (elements/groupSize);
    vector<int> medians;

    // Base case, input is small. Just sort and return element at k.
    if(elements<(groupSize*2))
    {
        //insertionSort(A, begin, end);
        sort(A.begin(), A.end());
        return A.at(begin+k);
    }

    int i = 0;
    // Divide and sort full groups.
    for(int g=0; g<numOfGroups; g++, i+=groupSize)
    {
        //insertionSort(A, i, i+groupSize);
        sort(A.begin()+i, A.begin()+(i+groupSize));
        medians.push_back(A.at(i+(groupSize/2)));
    }
    // Sort remainder group if there is one.
    if(i<elements)
    {
        //insertionSort(A, i, i+(elements%groupSize));
        sort(A.begin()+i, A.begin()+(i+(elements%groupSize)));
        medians.push_back(A.at(i+((elements%groupSize)/2)));
    }

    // Find median of medians, then partition around that.
    int median = linearSelect(medians, 0, medians.size(), medians.size()/2, groupSize),
        pivot = partition(A, begin, end, median),
        lessSize = pivot - begin + 1;

    // Answer is in lesser group
    if(k<lessSize)
    {
        return linearSelect(A, begin, pivot, k, groupSize);
    }
    // Answer is in greater group.
    else if(k>lessSize)
    {
        return linearSelect(A, pivot+1, end, k-lessSize, groupSize);
    }
    // Answer is at k
    else
    {
        return A.at(k);
    }
}

int main()
{
    vector<int> A;

    for(int i=0; i<1000; i++)
    {
        A.push_back(i);
    }

    cout << linearSelect(A, 0, A.size(), 50, 7) << endl;

    return 0;
}

Answer 1

当我使用Address Sanitizer(使用最近的GCC的-fsanitize=address)对程序进行检测时，它将报告:

ASAN:DEADLYSIGNAL
=================================================================
==97243==ERROR: AddressSanitizer: stack-overflow on address 0x7fffda79bff8 (pc 0x7f3999017979 bp 0x7fffda79c880 sp 0x7fffda79c000 T0)
    #0 0x7f3999017978 in __asan::asan_memalign(unsigned long, unsigned long, __sanitizer::BufferedStackTrace*, __asan::AllocType) ../../../../libsanitizer/asan/asan_allocator.cc:702
    #1 0x7f39990b1c48 in operator new(unsigned long) ../../../../libsanitizer/asan/asan_new_delete.cc:60
    #2 0x404708 in __gnu_cxx::new_allocator<int>::allocate(unsigned long, void const*) /usr/local/gcc-svn-r239225/include/c++/7.0.0/ext/new_allocator.h:104
    #3 0x403dc5 in std::allocator_traits<std::allocator<int> >::allocate(std::allocator<int>&, unsigned long) /usr/local//gcc-svn-r239225/include/c++/7.0.0/bits/alloc_traits.h:416
    #4 0x403599 in std::_Vector_base<int, std::allocator<int> >::_M_allocate(unsigned long) /usr/local/gcc-svn-r239225/include/c++/7.0.0/bits/stl_vector.h:172
    #5 0x402b5c in void std::vector<int, std::allocator<int> >::_M_realloc_insert<int const&>(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, int const&) /usr/local/gcc-svn-r239225/include/c++/7.0.0/bits/vector.tcc:399
    #6 0x40279e in std::vector<int, std::allocator<int> >::push_back(int const&) /usr/local/gcc-svn-r239225/include/c++/7.0.0/bits/stl_vector.h:954
    #7 0x401d71 in linearSelect(std::vector<int, std::allocator<int> >&, int const&, int const&, int const&, int const&) /tmp/t.cc:77
    #8 0x4020e4 in linearSelect(std::vector<int, std::allocator<int> >&, int const&, int const&, int const&, int const&) /tmp/t.cc:100
    #9 0x4020e4 in linearSelect(std::vector<int, std::allocator<int> >&, int const&, int const&, int const&, int const&) /tmp/t.cc:100
    #10 0x4020e4 in linearSelect(std::vector<int, std::allocator<int> >&, int const&, int const&, int const&, int const&) /tmp/t.cc:100
    #11 0x4020e4 in linearSelect(std::vector<int, std::allocator<int> >&, int const&, int const&, int const&, int const&) /tmp/t.cc:100
    #12 0x4020e4 in linearSelect(std::vector<int, std::allocator<int> >&, int const&, int const&, int const&, int const&) /tmp/t.cc:100
...

结论:您的递归基础案例已被废除。看着GDB崩溃:

(gdb) bt -20
#20941 0x00000000004020e5 in linearSelect (A=std::vector of length 143, capacity 256 = {...}, begin=@0x7fffffffc0b4: 38, end=@0x7fffffffda50: 72, k=@0x7fffffffc0b8: 33, groupSize=@0x7fffffffdcd0: 7) at t.cc:100
#20942 0x00000000004020e5 in linearSelect (A=std::vector of length 143, capacity 256 = {...}, begin=@0x7fffffffc244: 38, end=@0x7fffffffda50: 72, k=@0x7fffffffc248: 33, groupSize=@0x7fffffffdcd0: 7) at t.cc:100
#20943 0x00000000004020e5 in linearSelect (A=std::vector of length 143, capacity 256 = {...}, begin=@0x7fffffffc3d4: 38, end=@0x7fffffffda50: 72, k=@0x7fffffffc3d8: 33, groupSize=@0x7fffffffdcd0: 7) at t.cc:100
#20944 0x00000000004020e5 in linearSelect (A=std::vector of length 143, capacity 256 = {...}, begin=@0x7fffffffc564: 38, end=@0x7fffffffda50: 72, k=@0x7fffffffc568: 33, groupSize=@0x7fffffffdcd0: 7) at t.cc:100
#20945 0x00000000004020e5 in linearSelect (A=std::vector of length 143, capacity 256 = {...}, begin=@0x7fffffffc6f4: 38, end=@0x7fffffffda50: 72, k=@0x7fffffffc6f8: 33, groupSize=@0x7fffffffdcd0: 7) at t.cc:100
#20946 0x00000000004020e5 in linearSelect (A=std::vector of length 143, capacity 256 = {...}, begin=@0x7fffffffc884: 38, end=@0x7fffffffda50: 72, k=@0x7fffffffc888: 33, groupSize=@0x7fffffffdcd0: 7) at t.cc:100
#20947 0x00000000004020e5 in linearSelect (A=std::vector of length 143, capacity 256 = {...}, begin=@0x7fffffffca14: 38, end=@0x7fffffffda50: 72, k=@0x7fffffffca18: 33, groupSize=@0x7fffffffdcd0: 7) at t.cc:100
#20948 0x00000000004020e5 in linearSelect (A=std::vector of length 143, capacity 256 = {...}, begin=@0x7fffffffcba4: 38, end=@0x7fffffffda50: 72, k=@0x7fffffffcba8: 33, groupSize=@0x7fffffffdcd0: 7) at t.cc:100
#20949 0x00000000004020e5 in linearSelect (A=std::vector of length 143, capacity 256 = {...}, begin=@0x7fffffffcd34: 38, end=@0x7fffffffda50: 72, k=@0x7fffffffcd38: 33, groupSize=@0x7fffffffdcd0: 7) at t.cc:100
#20950 0x00000000004020e5 in linearSelect (A=std::vector of length 143, capacity 256 = {...}, begin=@0x7fffffffcec4: 38, end=@0x7fffffffda50: 72, k=@0x7fffffffcec8: 33, groupSize=@0x7fffffffdcd0: 7) at t.cc:100
#20951 0x00000000004020e5 in linearSelect (A=std::vector of length 143, capacity 256 = {...}, begin=@0x7fffffffd054: 38, end=@0x7fffffffda50: 72, k=@0x7fffffffd058: 33, groupSize=@0x7fffffffdcd0: 7) at t.cc:100
#20952 0x00000000004020e5 in linearSelect (A=std::vector of length 143, capacity 256 = {...}, begin=@0x7fffffffd1e4: 38, end=@0x7fffffffda50: 72, k=@0x7fffffffd1e8: 33, groupSize=@0x7fffffffdcd0: 7) at t.cc:100
#20953 0x00000000004020e5 in linearSelect (A=std::vector of length 143, capacity 256 = {...}, begin=@0x7fffffffd374: 38, end=@0x7fffffffda50: 72, k=@0x7fffffffd378: 33, groupSize=@0x7fffffffdcd0: 7) at t.cc:100
#20954 0x00000000004020e5 in linearSelect (A=std::vector of length 143, capacity 256 = {...}, begin=@0x7fffffffd504: 38, end=@0x7fffffffda50: 72, k=@0x7fffffffd508: 33, groupSize=@0x7fffffffdcd0: 7) at t.cc:100
#20955 0x00000000004020e5 in linearSelect (A=std::vector of length 143, capacity 256 = {...}, begin=@0x7fffffffd694: 38, end=@0x7fffffffda50: 72, k=@0x7fffffffd698: 33, groupSize=@0x7fffffffdcd0: 7) at t.cc:100
#20956 0x00000000004020e5 in linearSelect (A=std::vector of length 143, capacity 256 = {...}, begin=@0x7fffffffd824: 38, end=@0x7fffffffda50: 72, k=@0x7fffffffd828: 33, groupSize=@0x7fffffffdcd0: 7) at t.cc:100
#20957 0x00000000004020e5 in linearSelect (A=std::vector of length 143, capacity 256 = {...}, begin=@0x7fffffffdbe0: 0, end=@0x7fffffffda50: 72, k=@0x7fffffffdb48: 71, groupSize=@0x7fffffffdcd0: 7) at t.cc:100
#20958 0x0000000000402041 in linearSelect (A=std::vector of length 143, capacity 256 = {...}, begin=@0x7fffffffdbe0: 0, end=@0x7fffffffdb44: 143, k=@0x7fffffffdb48: 71, groupSize=@0x7fffffffdcd0: 7) at t.cc:95
#20959 0x0000000000401f42 in linearSelect (A=std::vector of length 1000, capacity 1024 = {...}, begin=@0x7fffffffdca4: 0, end=@0x7fffffffdca8: 1000, k=@0x7fffffffdcac: 50, groupSize=@0x7fffffffdcd0: 7) at t.cc:88
#20960 0x0000000000402356 in main () at t.cc:118

我们可以看到，第3次和所有后续递归调用都使用相同的参数，从而导致无限递归。