Что я уже понял
Я понимаю, что медианный алгоритм медиан (я буду обозначать как MoM) является алгоритмом с высоким постоянным коэффициентом O (N). Он находит медианы k-групп (обычно 5) и использует их в качестве наборов следующей итерации для поиска медиан. Разворот после нахождения этого будет между 3/10n и 7/10n исходного набора, где n — количество итераций, которое потребовалось, чтобы найти один медианный базовый случай.
Я продолжаю получать ошибку сегментации, когда запускаю этот код для MoM, но я не уверен, почему. Я отладил его и считаю, что проблема заключается в том, что я звоню medianOfMedian(medians, 0, medians.size()-1, medians.size()/2);
. Однако я подумал, что это логично, поскольку мы должны были рекурсивно найти медиану, вызвав саму себя. Возможно, мой базовый случай неверен? В руководстве YogiBearian на YouTube (профессор из Стэнфорда, ссылка: 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);
}
}
Некоторые дополнительные функции для помощи в модульном тестировании
Вот несколько модульных тестов, которые я написал для этих двух функций. Надеюсь, они помогут.
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
Кажется, все в порядке, пока не возникнет ошибка сегментации. Я уверен, что моя функция разбиения тоже работает (была одна из реализаций вопроса leetcode).
Отказ от ответственности: это не проблема домашнего задания, а скорее мое собственное любопытство по поводу алгоритма после того, как я использовал quickSelect в наборе задач leetcode.
Пожалуйста, дайте мне знать, если мой предложенный вопрос требует дополнительной проработки для MVCE, спасибо!
РЕДАКТИРОВАТЬ: я понял, что схема разделения рекурсии неверна в моем коде. Как указал Прадхан, у меня каким-то образом есть пустые векторы, которые приводят к тому, что начало и конец равны 0 и -1 соответственно, что приводит к ошибке сегментации из-за бесконечного цикла ее вызова. Все еще пытаюсь понять эту часть.
[ ]
для доступа к элементам вектора наvector::at()
. Почему? Чтобы убедиться, что вы не вышли за пределы при доступе к своим векторным элементам. Если вы выйдете за пределы допустимого диапазона,at()
выдаст исключение, предоставив вам дополнительную информацию. Если вы просто используете[ ]
, поведение кода не определено, если вы выходите за пределы. В SO было несколько сообщений о сбоях векторов и сегментов, и почти всегда решение можно найти, используяat()
для выявления проблем с граничным доступом. - person PaulMcKenzie   schedule 19.06.2016min(vec.begin()+i+GROUP_SIZE, vec.end())
должно бытьmin(vec.begin()+i+GROUP_SIZE, vec.begin()+end)
- person Sergey Kalinichenko   schedule 19.06.2016vec.begin()+end
иvec.end()
. - person OneRaynyDay   schedule 19.06.2016