Не может генерировать большое случайное число целых чисел без переполнения - PullRequest
Новая
       19

Не может генерировать большое случайное число целых чисел без переполнения

0 голосов
/ 08 февраля 2019

Я создал алгоритмы сортировки, которые используют многопоточную быструю сортировку.Входные данные создаются случайным образом.100 миллионов целых чисел рандомизируются и вставляются в массив, а затем сортируются.Дело в том, что я хочу проверить скорость, с которой возрастает сложность алгоритма, когда вводится больше данных.

Проблема: 100 миллионов выглядит так, как будто это верхний предел количества чисел, которые я могу сгенерировать и / или вставить в массив.Вопросы: как увеличить размер стека / кучи, чтобы можно было использовать больше чисел.Я планирую сделать что-то вроде 100 миллиардов.PS RAM не является проблемой.

Часть, в которой определяется число сгенерированных целых чисел, записывает в строке: "// число сгенерированных целых чисел".

Спасибо.

Код: 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <sys/time.h>
#include <pthread.h>
struct Params
{
    int *start;
    size_t len;
       int depth;
};
pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;
void *merge_sort_thread(void *pv);
void merge(int *start, int *mid, int *end)
{
    int *res = malloc((end - start)*sizeof(*res));
    int *lhs = start, *rhs = mid, *dst = res;
    while (lhs != mid && rhs != end)
        *dst++ = (*lhs < *rhs) ? *lhs++ : *rhs++;
    while (lhs != mid)
        *dst++ = *lhs++;
    // copy results
    memcpy(start, res, (rhs - start) * sizeof *res);
    free(res);
}
// initialization
   void merge_sort_mt(int *start, size_t len, int depth)
{
    if (len < 2)
        return;
    if (depth <= 0 || len < 4)
    {
          merge_sort_mt(start, len/2, 0);
        merge_sort_mt(start+len/2, len-len/2, 0);
    }
    else
    {
        struct Params params = { start, len/2, depth/2 };
        pthread_t thrd;
        pthread_mutex_lock(&mtx);
        printf("Starting subthread...\n");
        pthread_mutex_unlock(&mtx);
        pthread_create(&thrd, NULL, merge_sort_thread, &params);
        merge_sort_mt(start+len/2, len-len/2, depth/2);
        pthread_join(thrd, NULL);
        pthread_mutex_lock(&mtx);
        printf("Finished subthread.\n");
        pthread_mutex_unlock(&mtx);
    }
    merge(start, start+len/2, start+len);
}
void *merge_sort_thread(void *pv)
{
    struct Params *params = pv;
    merge_sort_mt(params->start, params->len, params->depth);
    return pv;
}
void merge_sort(int *start, size_t len)
{
    merge_sort_mt(start, len, 8);
}
int main()
{
clock_t start, stop;
    static const unsigned int N = 100000000; //number of generated integers
    int *data = malloc(N * sizeof(*data));
    unsigned int i;
    srand((unsigned)time(0));
    for (i=0; i<N; ++i)
    {
    data[i] = rand() % 500;
  //  printf("%4d ", data[i]);
   //     if ((i+1)%8 == 0)
          // printf("\n");
    }
  //  printf("\n");
   start = clock();
    merge_sort(data, N);
    for (i=0; i<N; ++i)
    {
       // printf("%4d ", data[i]);
     //   if ((i+1)%8 == 0)
        //    printf("\n");
    }
   stop = clock();
       printf("Elapsed: %f seconds\n", (double)(stop - start) / CLOCKS_PER_SEC);
   // printf("\n");
    free(data);
    getchar();
    getchar();
    getchar();
    getchar();
    getchar();
    return 0;
}
...