0

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

#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;
}
4

1 回答 1

0

当我使用 Address Sanitizer（-fsanitize=address使用最新的 GCC）检测您的程序时，它会报告：

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 次和所有后续的递归调用都获得相同的参数，导致无限递归。

于 2016-12-03T23:01:03.713 回答