Почему моя медиана медиан быстро выбирает алгоритм segfault?
Мне трудно найти ошибку в моем коде, из-за которой алгоритм быстрого выбора медианы медиан переходит в сегфоут, когда ввод даже умеренно большой. Вывод правильный, когда я получаю вывод. Ниже приведен полный код, который вызывает ошибку в моей системе с заданными параметрами теста.
#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;
}
Решение
Когда я использую вашу программу с 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-й и все последующие рекурсивные вызовы получают одинаковые параметры, что приводит к бесконечной рекурсии.
Другие решения
Других решений пока нет …