私は今、同時実行のクラスを受講していて、最初の (ばかばかしいほど単純な) プロジェクトを完成させました。
私のコードでは、2 番目の配列の値ごとに、配列を介してバイナリ検索を行っています。2 番目の配列の値ごとに、スレッドを生成しています。これはシーケンシャル ソリューションよりも遅いことが判明したため、少数のスレッドを生成し、実行が完了するたびに新しいキーを渡すことを考えました。
いくつか問題があります。1 つ目は、キーがなくなったときにスレッドを終了させるにはどうすればよいかということです。
新しいキーを渡すにはどうすればよいですか?
新しいキーを待っている間、スレッドが古いキーで実行されないようにするにはどうすればよいですか (条件付き待機について読んでいて、それが必要だと思います)。
これが私の現在の(効果のない)解決策です。
#define ARRAYSIZE 50000
#define KEY_NOT_FOUND -1
#define KEY_FOUND 0
#include <pthread.h>
#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>
int binary_search(int *array, int key, int min, int max);
void *worker(void *arg);
int count = 0;
pthread_mutex_t L;
int l_array[ARRAYSIZE * 2];
int main(void)
{
int r_array[ARRAYSIZE];
int *p;
pthread_t *threads;
int ix = 0;
int jx = 0;
struct timeval start, stop;
double elapsed;
for(ix = 0; ix < ARRAYSIZE; ix++)
{
r_array[ix] = ix;
}
for(ix = 0; ix < ARRAYSIZE * 2; ix++)
{
l_array[ix] = ix + 2;
}
gettimeofday(&start, NULL);
threads = (pthread_t *) malloc(ARRAYSIZE * sizeof(pthread_t));
for (jx = 0; jx < ARRAYSIZE; jx++) {
p = (int *) malloc(sizeof(int));
*p = r_array[jx];
pthread_create(&threads[jx], NULL, worker, (void *)(p));
}
for (jx = 0; jx < ARRAYSIZE; jx++) {
pthread_join(threads[jx], NULL);
}
fprintf(stderr, "%d\n", count);
gettimeofday(&stop, NULL);
elapsed = ((stop.tv_sec - start.tv_sec) * 1000000+(stop.tv_usec-start.tv_usec))/1000000.0;
printf("time taken is %f seconds\n", elapsed);
return 0;
}
void* worker(void *arg)
{
int boolean = 0;
int key = *((int *) arg);
boolean = binary_search(l_array, key, 0, ARRAYSIZE * 2);
if(boolean == 1)
{
pthread_mutex_lock(&L);
count++;
pthread_mutex_unlock(&L);
}
}
int binary_search(int *array, int key, int min, int max)
{
int mid = 0;
if (max < min) return 0;
else
{
mid = (min + max) / 2;
if (array[mid] > key) return binary_search(array, key, min, mid - 1);
else if (array[mid] < key) return binary_search(array, key, mid + 1, max);
else
{
return 1;
}
}
}