Ich gruesse euch liebe Community,
Ich habe aktuell folgendes probiert:
Habe mir einen Multithreadtauglichen Mergesort Algorithmus gebaut, und einen normalen Heapsort Algorithmus.
Das Problem ist nun folgendes:
Ich erstelle bei beiden ein Random Array mit einer Groesse von z.B. 10000.
Ab dem Zeitpunkt wird die Zeit vom Sortiervorgang gemessen, sowohl bei Mergesort als auch Heapsort.
Sind beides unabhaengige ausfuehrbare Dateien.
Das Problem ist: Mergesort braucht trotz Multicore Optimierung 4 mal solange wie mein Heapsort Algorithmus.
Woran kann das liegen?
Einmal Mergesort
C
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MIN_LENGTH 4
int DEBUG;
typedef struct
{
int *array;
int left;
int right;
int tid;
} thread_data_t;
int number_of_threads;
pthread_mutex_t lock_number_of_threads;
int my_comp(const void *larg, const void *rarg)
{
int l = *(int *)larg;
int r = *(int *)rarg;
if (l < r)
{
return -1;
}
else if (l == r)
{
return 0;
}
return 1;
}
void merge(int *data, int left, int right, int tid)
{
if (DEBUG)
{
printf("[%d] Merging %d to %d\n", tid, left, right);
}
int ctr = 0;
int i = left;
int mid = left + ((right - left) / 2);
int j = mid + 1;
int *c = (int *) malloc((right - left + 1) * sizeof(int));
while (i <= mid && j <= right)
{
if (data[i] <= data[j])
{
c[ctr++] = data[i++];
}
else
{
c[ctr++] = data[j++];
}
}
if (i == mid + 1)
{
while (j <= right)
{
c[ctr++] = data[j++];
}
}
else
{
while (i <= mid)
{
c[ctr++] = data[i++];
}
}
i = left;
ctr = 0;
while (i <= right)
{
data[i++] = c[ctr++];
}
free(c);
return;
}
void *merge_sort_threaded(void *arg)
{
thread_data_t *data = (thread_data_t *) arg;
int l = data->left;
int r = data->right;
int t = data->tid;
if (r - l + 1 <= MIN_LENGTH)
{
if (DEBUG)
{
printf("[%d] Calling qsort(%d, %d).\n", t, l, r);
}
qsort(data->array + l, r - l + 1, sizeof(int), my_comp);
}
else
{
int m = l + ((r - l) / 2);
thread_data_t data_0;
data_0.left = l;
data_0.right = m;
data_0.array = data->array;
pthread_mutex_lock(&lock_number_of_threads);
data_0.tid = number_of_threads++;
pthread_mutex_unlock(&lock_number_of_threads);
pthread_t thread0;
int rc = pthread_create(&thread0,
NULL,
merge_sort_threaded,
&data_0);
int created_thread_0 = 1;
if (rc)
{
if (DEBUG)
{
printf("[%d] Failed to create thread, calling qsort.", data_0.tid);
}
created_thread_0 = 0;
qsort(data->array + l, m - l + 1, sizeof(int), my_comp);
}
thread_data_t data_1;
data_1.left = m + 1;
data_1.right = r;
data_1.array = data->array;
pthread_mutex_lock(&lock_number_of_threads);
data_1.tid = number_of_threads++;
pthread_mutex_unlock(&lock_number_of_threads);
pthread_t thread1;
rc = pthread_create(&thread1,
NULL,
merge_sort_threaded,
&data_1);
int created_thread_1 = 1;
if (rc)
{
if (DEBUG)
{
printf("[%d] Failed to create thread, calling qsort.", data_1.tid);
}
created_thread_1 = 0;
qsort(data->array + m + 1, r - m, sizeof(int), my_comp);
}
if (created_thread_0)
{
pthread_join(thread0, NULL);
}
if (created_thread_1)
{
pthread_join(thread1, NULL);
}
merge(data->array, l, r, t);
}
pthread_exit(NULL);
return NULL;
}
void merge_sort(int *array, int start, int finish)
{
thread_data_t data;
data.array = array;
data.left = start;
data.right = finish;
number_of_threads = 0;
pthread_mutex_init(&lock_number_of_threads, NULL);
data.tid = 0;
pthread_t thread;
int rc = pthread_create(&thread,
NULL,
merge_sort_threaded,
&data);
if (rc)
{
if (DEBUG)
{
printf("[%d] Failed to create thread, calling qsort.",
data.tid);
}
qsort(array + start,
finish - start + 1,
sizeof(int),
my_comp);
}
pthread_join(thread, NULL);
return;
}
int main()
{
int size=0,loop,qrand;
int *array;
printf("Array-Groesse eingeben: ");
scanf("%d", &size);
array = (int *) malloc(size * sizeof(int));
if(array != NULL)
{
printf("\nSpeicher ist reserviert\n");
printf("\nFilling array.\n");
for(loop=0;loop<size;loop++)
{
qrand=rand() %20;
array[loop]=qrand;
printf("%d",qrand);
}
}
else printf("\nKein freier Speicher vorhanden.\n");
printf("\nMerge Sort..\n");
clock_t t;
t = clock();
merge_sort(array, 0, size - 1);
for(loop=0;loop<size;loop++)
{
printf("%d",array[loop]);
}
if((size * sizeof(int)) < 1000)
{
printf("\n %lu Bytes wurden freigegeben\n",(size * sizeof(int)));
}
else if((size *sizeof(int))>=1000)
{
printf("\n %lu Kilobytes wurden freigegeben\n",((size * sizeof(int))/1000));
}
else if((size * sizeof(int))>=1000*1000)
{
printf("\n %lu Megabytes wurden freigegeben\n", ((size * sizeof(int))/1000*1000));
}
free(array);
pthread_mutex_destroy(&lock_number_of_threads);
t = clock() - t;
printf("Sorting took %f seconds to finish \n", time_taken);
return 0;
}
Ist es eventuell falsch implementiert?
C
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void quicksort(int *A, int len);
int max (int *a, int n, int i, int j, int k)
{
int m = i;
if (j < n && a[j] > a[m]) {
m = j;
}
if (k < n && a[k] > a[m]) {
m = k;
}
return m;
}
void downheap (int *a, int n, int i)
{
while (1) {
int j = max(a, n, i, 2 * i + 1, 2 * i + 2);
if (j == i) {
break;
}
int t = a[i];
a[i] = a[j];
a[j] = t;
i = j;
}
}
void heapsort (int *a, int n)
{
int i;
for (i = (n - 2) / 2; i >= 0; i--) {
downheap(a, n, i);
}
for (i = 0; i < n; i++) {
int t = a[n - i - 1];
a[n - i - 1] = a[0];
a[0] = t;
downheap(a, n - i - 1, 0);
}
}
void quicksort(int *A, int len)
{
if (len < 2) return;
int pivot = A[len / 2];
int i, j;
for (i = 0, j = len - 1; ; i++, j--)
{
while (A[i] < pivot) i++;
while (A[j] > pivot) j--;
if (i >= j) break;
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
quicksort(A, i);
quicksort(A + i, len - i);
}
int main()
{
int size=0,loop,qrand;
int *array;
printf("Array-Groesse eingeben: ");
scanf("%d", &size);
// Allocate memory
array = (int *) malloc(size * sizeof(int));
if(array != NULL)
{
printf("\nSpeicher ist reserviert\n");
printf("\nFilling array.\n");
for(loop=0;loop<size;loop++)
{
qrand=rand() %20;
array[loop]=qrand;
printf("%d",qrand);
}
}
else printf("\nKein freier Speicher vorhanden.\n");
printf("\nHeapsort..\n");
clock_t t;
t = clock();
heapsort(array,size);
for(loop=0;loop<size;loop++)
{
printf("%d",array[loop]);
}
if((size * sizeof(int)) < 1000)
{
printf("\n %lu Bytes wurden freigegeben\n",(size * sizeof(int)));
}
else if((size *sizeof(int))>=1000)
{
printf("\n %lu Kilobytes wurden freigegeben\n",((size * sizeof(int))/1000));
}
else if((size * sizeof(int))>=1000*1000)
{
printf("\n %lu Megabytes wurden freigegeben\n", ((size * sizeof(int))/1000*1000));
}
free(array);
//Reallocate memory above
t = clock() - t;
double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds
printf("Sorting took %f seconds to finish \n", time_taken);
return 0;
}Verfuegbar sind 24 Threads beim System
