quicksort parallèle en c

Ne serait-il pas plus rapide de diviser
plus de 1 million de chaînes par le nombre de
threads (dans mon cas, 24 threads), et
demandez à chacun de travailler sur une section, et
puis faire un mergesort?

C'est une bonne idée.

Mais vous pouvez faire de l'observation par écrit jouet programmes pour quick-sort et merge-sort et de profiter des avantages de leurs algorithmique-/run-time-comportement.

Par exemple. quick-sort sortes tout dividing processus (pivot élément sera mis en sa place définitive à la fin de l'itération) et merge-sort sortes tout merging (le tri est fait, après tout le travail est décomposé (divisé) en très granulaire-unités où il peut être directement comparé avec d'autres granulaire-unités (== ou strcmp()).

Mélanger les algorithmes basés sur la nature de l'ensemble de travail est une bonne idée.

À l'égard de la parallèle le tri, voici mon parallel merge-sort pour vous obtenir a commencé.

#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's 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;
}

Bonne chance!

Avez-vous envisagé d'utiliser un algorithme de tri spécialement conçu pour trier les chaînes?
Il semble que cela pourrait être une meilleure idée que d'essayer de mettre en œuvre une coutume de quicksort. Le choix des algorithmes probablement dépend de la longueur des chaînes et comment ils sont différents, mais un tri radix n'est probablement pas un mauvais pari.

Un rapide recherche google tourné un article sur le tri des chaînes de caractères. Je n'ai pas lu, mais Sedgewick et Bentley connaissent vraiment leur truc. Selon le résumé, leur algorithme est un amalgame de Quicksort et de tri radix.

Une autre solution possible consiste à envelopper un parallèle algorithme de tri à partir de C++. GNU STL mise en œuvre a un mode parallèlequi contient, en parallèle, une implémentation rapide.
C'est probablement la solution la plus simple.