có nó không thể nhanh hơn nhiều để chia 1 triệu chuỗi bằng của số đề (trong trường hợp của tôi, 24 bài), và có họ từng làm việc trên một phần, và sau đó làm một mergesort ?
Đó là một ý tưởng hay.
Nhưng bạn có thể thực hiện một số quan sát bằng cách viết chương trình đồ chơi cho quick-sort và merge-sort và tận dụng lợi thế của thuật toán/thời gian chạy-hành vi của chúng.
Ví dụ: quick-sort sắp xếp trong khi dividing quá trình (pivot phần tử sẽ được đặt ở vị trí cuối cùng ở cuối của lần lặp đó) và merge-sort sắp xếp trong khi merging (sắp xếp được thực hiện sau khi toàn bộ nhóm làm việc được chia nhỏ (chia) thành các đơn vị rất chi tiết có thể được so sánh trực tiếp với hạt-đơn vị khác (== hoặc strcmp()).
Trộn lên các thuật toán dựa vào bản chất của bộ lao động là một ý tưởng tốt.
liên quan đến việc phân loại song song với, đây là parallel merge-sort của tôi để bạn bắt đầu.
#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;
}
Chúc bạn may mắn!
có thể. phụ thuộc. về vấn đề này. trên phần cứng. – Anycorn
http://en.wikipedia.org/wiki/Quicksort#Parallelization –
http://en.wikipedia.org/wiki/External_sorting –