Быстрая сортировка с несколькими потоками оставляет последнюю 1/6 несортированной - PullRequest
Новая
       22

Быстрая сортировка с несколькими потоками оставляет последнюю 1/6 несортированной

0 голосов
/ 11 апреля 2020

Моя цель - создать программу, которая берет большой список несортированных целых чисел (1-10 миллионов) и делит его на 6 частей, где поток одновременно сортирует их. После сортировки я объединяю его в один отсортированный массив, чтобы быстрее найти медиану и режим.

Входной файл будет выглядеть примерно так: 

# 1000000
314
267
213
934

, где число, следующее за #, идентифицирует количество целых чисел в списке.

В настоящее время я могу сортировать идеально и быстро без потоков, однако, когда я начал работу с потоками, я столкнулся с проблемой. Для 1 000 000 наборов данных он сортирует только первые 833 333 целых числа, оставляя последние 166 666 (1/6) несортированными. 

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
#include <time.h>
#define BUF_SIZE 1024

int sum; /* this data will be shared by the thread(s) */
int * bigArr;
int size;
int findMedian(int array[], int size)
{
    if (size % 2 != 0)
        return array[size / 2];

    return (array[(size - 1) / 2] + array[size / 2]) / 2;
}
/*compare function for quicksort*/
int _comp(const void* a, const void* b) {
    return ( *(int*)a - *(int*)b);
}

/*This function is the problem method*/
/*indicate range of array to be processed with the index(params)*/
void *threadFct(int param)
{
    int x= size/6;
    if(param==0)x= size/6;
    if(param>0&&param<5)x= (size/6)*param;
    if(param==5)x= (size/6)*param+ (size%size/6);/*pass remainder into last thread*/
    qsort((void*)bigArr, x, sizeof(bigArr[param]), _comp);
    pthread_exit(0);
}

int main(int argc, char *argv[])
{
    FILE *source;
    int i =0;

    char buffer[BUF_SIZE];

    if(argc!=2){
        printf("Error. please enter ./a followed by the file name");
        return -1;}

    source= fopen(argv[1], "r");
    if (source == NULL) { /*reading error msg*/
        printf("Error. File not found.");
        return 1;
    }
    int count= 0;
    while (!feof (source)) {
        if (fgets(buffer, sizeof (buffer), source)) {
            if(count==0){  /*Convert string to int using atoi*/
                char str[1];
                sprintf(str, "%c%c%c%c%c%c%c%c%c",buffer[2],buffer[3],buffer[4],buffer[5],buffer[6],buffer[7],buffer[8],buffer[9],buffer[10]);/*get string of first */
                size= atoi(str); /* read the size of file--> FIRST LINE of file*/
                printf("SIZE: %d\n",size);
                bigArr= malloc(size*sizeof(int));
            }
            else{
                //printf("[%d]= %s\n",count-1, buffer); /*reads in the rest of the file*/
                bigArr[count-1]= atoi(buffer);
            }
            count++;
        }
    }

/*thread the unsorted array*/
    pthread_t tid[6]; /* the thread identifier */
    pthread_attr_t attr; /* set of thread attributes */

// qsort((void*)bigArr, size, sizeof(bigArr[0]), _comp);  <---- sorts array without threading
    for(i=0; i<6;i++){
        pthread_create(&tid[i], NULL, &threadFct, i);
        pthread_join(tid[i], NULL);
    }

    printf("Sorted array:\n");

    for(i=0; i<size;i++){
        printf("%i \n",bigArr[i]);
    }

    fclose(source);
}

Так что прояснить проблему можно по моему threadFct(). Чтобы объяснить, что делает функция, параметр (номер потока) определяет, какой кусок массива нужно быстро сортировать. Я делю размер на 6 частей, и, поскольку он четный, оставшаяся часть чисел go помещается в последний фрагмент. Так, например, 1 000 000 целых чисел у меня будет первая 5/6 сортировка по 166 666 каждая, а последние 1/6 отсортируют остаток (166670).

Я знаю, что

  • Многопоточность не сильно ускоряется даже для 10 миллионов целых чисел
  • Это не самый эффективный способ найти медиану / режим

Спасибо за чтение и любую помощь получено с благодарностью.

1 Ответ

2 голосов
/ 11 апреля 2020

Вы сортируете начало массива при каждом вызове qsort. Вы только изменяете количество элементов, которые сортирует каждый поток, устанавливая x. Вы также устанавливаете x в одно и то же значение в потоках 0 и 1.

. Вам необходимо вычислить смещение в массиве для каждого потока, равное size/6 * param. Количество элементов будет size/6 за исключением последнего фрагмента, который использует модуль для получения остатка.

Как упоминалось в комментариях, аргумент функции потока должен быть указателем, а не int. Вы можете скрыть целое число в указателе, но вам нужно использовать явные приведения. 

void *threadFct(void* param_ptr)
{
    int param = (int)param_ptr;
    int start = size/6 * param;
    int length;
    if (param < 5) {
        length = size/6;
    } else {
        length = size - 5 * (size/6);
    }
    qsort((void*)(bigArr+start), length, sizeof(*bigArr), _comp);
    pthread_exit(0);
}

и более поздние 

pthread_create(&tid[i], NULL, &threadFct, (void*)i);
...