Сбой алгоритма BFPRT (медиана медиан) после массива 185000

Question

Мой алгоритм BFPRT дает сбой, как только я помещаю массив размером 1300.000 int, но он отлично работает ниже этого.Я знаю, что, вероятно, это проблема с выделением памяти, но я боролся в течение нескольких дней и не смог найти ответ.
Я думаю, что выделил свой массив для кучи, так что это не должно быть переполнением стека, верно?Как вы думаете, замена моего массива вектором решит проблему?Я попробовал это, но не совсем заставил это работать.(векторы действительно сбивают с толку меня, атм)

Мой отладчик говорит:

>Program received signal SIGSEGV, Segmentation fault.  
>In ?? () ()

>[debug]> bt 30  
>[debug]#0  0x0000002b in ?? ()  
>[debug]Backtrace stopped: Cannot access memory at address 0x0  
>[debug]>>>>>>cb_gdb:  

Любая помощь будет благодарна Это мой код:

#include <iostream>
#include <math.h>
#include <random>
#include <chrono>
#include <fstream>
#include <algorithm>
#include <stdint.h>

using namespace std;

int32_t ithSmallest(int32_t arr[],int32_t low, int32_t high, int32_t iosto);

//sinartisi poy ftiaxnei ton pinaka
void arrayMaker (){
        int32_t n = 185000;
        int32_t *values = new int32_t[n];


        //apotelesmata simfwna me omoiomorfh katanomh
        std::random_device                  rand_dev;
        std::mt19937                        generator(rand_dev());
        std::uniform_int_distribution<int64_t>  unif(1,pow(10,10));

        for (int32_t i = 0; i < n; i++){
            values[i] = unif(generator);
        }

        ithSmallest(values,0,n-1,2);

        delete[] values;
}

int32_t vresMeso(int32_t arr[],int32_t n){
    sort (arr, arr+n);
    return arr[n/2];
}

int32_t partitionise(int32_t arr[], int32_t l, int32_t r, int32_t x)
{
    // Search for x in arr[l..r] and move it to end
    int32_t i;
    for (i=l; i<r; i++)
        if (arr[i] == x)
           break;
    swap(&arr[i], &arr[r]);

    // Standard partition algorithm
    i = l;
    for (int32_t j = l; j <= r - 1; j++)
    {
        if (arr[j] <= x)
        {
            swap(&arr[i], &arr[j]);
            i++;
        }
    }
    swap(&arr[i], &arr[r]);
    return i;
}

//Xeiroterhs periptwshs
int32_t ithSmallest(int32_t arr[],int32_t low, int32_t high, int32_t iosto){

    //an to noymero poy psaxnoyme yparxei kapoy mesa ston pinaka
    if (iosto > 0 && iosto <= high-low+1){
        //plithos stoixeiwn pinaka
        int32_t n = high - low + 1;
        //max (n+4)/5 group
        int32_t median[(n+4)/5];
        int32_t i;
        //Ftiaxe ta groupakia
        for (i=0; i<n/5; i++){
            median[i] = vresMeso(arr+low+i*5, 5);
            //cout << "gamw " << median[i] << endl;
        }
        //Gia to teleytaio groupaki an exei ligotera stoixeia
        if (n%5 != 0)
        {
            median[i] = vresMeso(arr+low+i*5, n%5);
            i++;
        }
        /*for (int32_t b = 0; b < i; b++){
                cout << "mediansPrwta = " << median[b] << endl;
        }*/


        //Vres ton meso twn meso me anadromh
        //Ama exeis 1 stoixeio mhn kaneis anadromh
        int32_t medOfMed = (i == 1)? median[i-1]:
                                 ithSmallest(median, 0, i-1, i/2);


        int32_t pos = partitionise(arr, low, high, medOfMed);

        // If position is same as k
        if (pos-low == iosto - 1)
            return arr[pos];
        if (pos-low > iosto - 1)  // If position is more, recur for left
            return ithSmallest(arr, low, pos-1, iosto);

        // Else recur for right subarray
        return ithSmallest(arr, pos+1, high, iosto-pos+low-1);
    }

    // If k is more than number of elements in array
    return INT_MAX;

}

int main()
{
    arrayMaker();
}

Answer 1

Попробуйте:

int32_t n = 185000;
double *values = new int32_t[n];

...

delete[] values;

или

int32_t n = 185000;
std::vector<int32_t> values;

Также это:

std::uniform_int_distribution<int32_t>  unif(1,pow(10,10));

выглядит плохо, потому что это pow плохо описанная магиячисло.Может быть, вы имели в виду это ...

#include <limits>
std::uniform_int_distribution<int32_t>  unif(1,std::numeric_limits<int32_t>::max());