Параллельная quicksort в c

Ответ 1

Не было бы гораздо быстрее разделить 1 миллион строк по числу потоки (в моем случае, 24 потока) и имейте каждую работу над разделом, и затем выполните слияние?

Это хорошая идея.

Но вы можете сделать некоторые замечания, написав программы для игрушек quick-sort и merge-sort и воспользоваться преимуществами их алгоритмического/run-time-поведения.

Например. quick-sort сортирует, а процесс dividing (элемент pivot будет помещен в свое конечное место в конце этой итерации), а merge-sort сортирует while merging (сортировка выполняется после разбивки всего рабочего набора (разделены) на очень зернистые единицы, где он может быть непосредственно сравнен с другими зернистыми единицами (== или strcmp()).

Смешивание алгоритмов, основанных на характере рабочего набора, является хорошей идеей.

Что касается параллельной сортировки, вот мой parallel merge-sort для начала.

#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>

#define NOTHREADS 2

/*

gcc -ggdb -lpthread parallel-mergesort.c 


NOTE: 
The mergesort boils downs to this.. 
Given two sorted array how do we merge this?

We need a new array to hold the result of merging
otherwise it is not possible to do it using array, 
so we may need a linked list

*/

int a[] = {10, 8, 5, 2, 3, 6, 7, 1, 4, 9};

typedef struct node {
int i;
int j;
} NODE;

void merge(int i, int j)
{
        int mid = (i+j)/2;
        int ai = i;
        int bi = mid+1;

        int newa[j-i+1], newai = 0;

        while(ai <= mid && bi <= j) {
                if (a[ai] > a[bi])
                        newa[newai++] = a[bi++];
                else                    
                        newa[newai++] = a[ai++];
        }

        while(ai <= mid) {
                newa[newai++] = a[ai++];
        }

        while(bi <= j) {
                newa[newai++] = a[bi++];
        }

        for (ai = 0; ai < (j-i+1) ; ai++)
                a[i+ai] = newa[ai];

}

void * mergesort(void *a)
{
                NODE *p = (NODE *)a;
                NODE n1, n2;
                int mid = (p->i+p->j)/2;
                pthread_t tid1, tid2;
                int ret;

                n1.i = p->i;
                n1.j = mid;

                n2.i = mid+1;
                n2.j = p->j;

                if (p->i >= p->j) return;

                ret = pthread_create(&tid1, NULL, mergesort, &n1);
                if (ret) {
                        printf("%d %s - unable to create thread - ret - %d\n", __LINE__, __FUNCTION__, ret);    
                        exit(1);
                }


                ret = pthread_create(&tid2, NULL, mergesort, &n2);
                if (ret) {
                        printf("%d %s - unable to create thread - ret - %d\n", __LINE__, __FUNCTION__, ret);    
                        exit(1);
                }

                pthread_join(tid1, NULL);
                pthread_join(tid2, NULL);

                merge(p->i, p->j);
                pthread_exit(NULL);
}


int main()
{
                int i;
                NODE m;
                m.i = 0;
                m.j = 9;
                pthread_t tid;

                int ret; 

                ret=pthread_create(&tid, NULL, mergesort, &m);
                if (ret) {
                        printf("%d %s - unable to create thread - ret - %d\n", __LINE__, __FUNCTION__, ret);    
                        exit(1);
                }

                pthread_join(tid, NULL);

                for (i = 0; i < 10; i++)
                                printf ("%d ", a[i]);

                printf ("\n");

                // pthread_exit(NULL);
                return 0;
}

Удачи!

Ответ 2

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

Почему бы не сделать это в одном потоке, а затем создать другой поток и делегировать его на одну половину, в то время как существующий поток занимает вторую половину и т.д. и т.д.?

Ответ 3

Рассматривали ли вы использование алгоритма сортировки, специально разработанного для сортировки строк? Похоже, что это может быть лучше, чем попытка реализовать пользовательскую quicksort. Конкретный выбор алгоритмов, вероятно, зависит от длины строк и от того, насколько они отличаются от сортировки radix, вероятно, неплохая ставка.

Быстрый google search появился статью о сортировка строк. Я не читал его, но Седжвик и Бентли действительно знают свои вещи. Согласно реферату, их алгоритм является амальгамом сортировки Quicksort и radix.

Еще одно возможное решение - обернуть алгоритм параллельной сортировки из С++. Реализация GNU STL имеет параллельный режим, который содержит параллельную реализацию quicksort. Это, вероятно, самое простое решение.

Ответ 4

Чтобы сделать многопоточную быстродействующую сортировку, необходимо оптимизировать доступ к памяти, чтобы большая часть работы сортировки выполнялась внутри не разделяемых кешей (L1 и L2). Моя ставка заключается в том, что однопоточная быстродействующая сортировка будет быстрее, чем muli-threaded, если вы не готовы выполнить много работы.

Одним из подходов к тестированию может быть один поток для сортировки верхней половины, а другой для сортировки нижнего.

Что касается специальной, упорядоченной по строкам процедуры сортировки, то для меня это звучит странно. Я имею в виду, что не так много случаев, когда сортировка вектора только строк (или целых чисел) особенно полезна. Обычно данные будут организованы в таблицу со столбцами и строками, и вы захотите отсортировать строки по одному столбцу, содержащему буквы, и, если они равны, вы будете сортировать, используя дополнительный столбец, содержащий отметку времени или ранжирование или что-то другое. Таким образом, процедура сортировки должна иметь возможность обрабатывать многоуровневый набор правил сортировки, который может указывать любые типы данных (логические, целые числа, даты, строки, с плавающей запятой и т.д.) В любом направлении (восходящем или нисходящем), присутствующем в столбцах таблицы.