Как бы я изменил свою функцию, чтобы создать только один новый поток вместо двух, и при этом достичь того же отсортированного результата?

Question

Я пишу параллельную сортировку слиянием, используя pthreads, Прямо сейчас я создаю два потока, и каждый сортирует половину данных. Затем результаты этих двух потоков объединяются. Тем не менее, я пытаюсь изменить свой код в функции, чтобы вместо этого создать только 1 поток без изменения существующих аргументов или возвращаемого типа функции.

Итак, я пытаюсь заставить функцию сначала отсортировать половину данных, а затем создать только один новый поток (вместо двух), чтобы отсортировать другую половину.

Это код, который я написал для функции, которая создает два потока:

// sort and return float array x, of length n
// using merge sort
void *pmerge_sort(void *args) {

  // unpack arguments
  Sort_args *sargs = (Sort_args *)args;
  float *x = sargs->x;
  int n = sargs->len;

  // if n < k, the array is sorted directly
  // using another sort algorithm
  int k = 100;
  if (n < k) {
    return(gsort(x, n));
  }

  // create 2 threads; each sorts half the data
  int m = ((float)n)/2.0;

  // pack arguments to recursive call
  Sort_args args1, args2;
  args1.x = x;
  args1.len = m;
  args2.x = &x[m];
  args2.len = n-m;

  int rc;
  pthread_t p1, p2;
  rc = pthread_create(&p1, NULL, pmerge_sort, (void *)&args1);  assert(rc == 0);
  rc = pthread_create(&p2, NULL, pmerge_sort, (void *)&args2);  assert(rc == 0);

  // merge the results from the threads
  float *x1, *x2;
  pthread_join(p1, (void **) &x1);
  pthread_join(p2, (void **) &x2);
  float *y = merge(x1, m, x2, n-m);

  // copy the result back to x and free y
  memcpy((void *)x, (void *)y, n*sizeof(float));
  free(y);

  return (void *)x;
}

Как бы я изменил свой код для создания только одного нового потока, но при этом достиг бы того же отсортированного результата, что и в коде, который создает два новых потока?

Answer 1

Если вы хотите отсортировать половину по родительскому элементу, а второй по дочернему, то вот одно из возможных решений:

  int rc;  
  pthread_t p;
  rc = pthread_create(&p, NULL, pmerge_sort, (void *)&args1);  assert(rc == 0);

  // merge the results from the threads
  float *x1, *x2;

  // let worker thread finish first
  pthread_join(p, (void **) &x1);

  // then sort other half here
  x2 = (float*)(*pmerge_sort)((void *)&args2);

  // then merge
  float *y = merge(x1, m, x2, n-m);

Есть и другие способы, мы можем изменить порядок вещей и использовать опрос. Однако это самое простое / наименьшее изменение, необходимое для удовлетворения ваших требований. (изменение для первого блока кода)