c - c中的并行快速排序

Question

在用 c 语言搜索并行快速排序的实现方面进行了大量搜索之后，我打算自己动手编写代码。 (我需要对大约 100 万个文本字符串的数组进行排序。)似乎我发现的所有实现都在 qsort 函数本身内部划分了工作，这在划分每个线程相对较少的工作量时产生了大量开销.

将 100 万个字符串除以线程数(在我的例子中是 24 个线程)，然后让它们各自处理一个部分，然后进行归并排序，这样不是更快吗？诚然，这在理论上有一个缺点，即它不是就地排序，但如果有大量可用内存，这不是问题。运行它的机器有 12 个(非常快的)物理内核/24 个逻辑内核和 192 GB(是的，千兆字节)内存。目前，即使在这台机器上，排序也需要将近 8 分钟!

Answer 1

Would it not be much faster to divide the 1 million strings by the number of threads (in my case, 24 threads), and have them each work on a section, and then do a mergesort?

这是个好主意。

但您可以通过为 quick-sort 和 merge-sort 编写玩具程序并利用它们的算法/运行时行为来进行一些观察。

例如。 quick-sort 在 dividing 过程中排序(pivot 元素将在该迭代结束时放在它的最终位置)和 merge -sort 在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'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;
}

祝你好运!