Многопоточные алгоритмы сортировки

Question

Я должен реализовать многопоточную сортировку слиянием и быстрой сортировкой на Java для моего класса алгоритмов и сравнить их с однопоточными версиями.Тем не менее, я никогда не использовал многопоточность.

Может ли код быть многопоточным или мне нужно начинать заново?

Вот мой код для алгоритмов однопотоковой сортировки слиянием.Метод sort () является частью шаблона стратегии, который я должен реализовать.

    @Override
public int[] sort(int[] list) {
    int array_size = list.length;
    list = msort(list, 0, array_size-1);
    return list;
}

int[] msort(int numbers[], int left, int right) {
    int mid;
    if (left<right) {
        mid = (right + left) / 2;
        msort(numbers, left, mid);
        msort(numbers, mid+1, right);
        merge(numbers, left, mid, mid+1, right);
    }
    return numbers;
}

void merge(int numbers[], int startA, int endA, int startB, int endB) {
    int finalStart = startA;
    int finalEnd = endB;
    int indexC = 0;
    int[] listC = new int[numbers.length];

    while(startA <= endA && startB <= endB){
        if(numbers[startA] < numbers[startB]){
            listC[indexC] = numbers[startA];
            startA = startA+1;
        }
        else{
            listC[indexC] = numbers[startB];
            startB = startB +1;
        }
        indexC++;
    }

    if(startA <= endA){
        for(int i = startA; i < endA; i++){
            listC[indexC]= numbers[i];
            indexC++;
        }
    }

    indexC = 0;
    for(int i = finalStart; i <= finalEnd; i++){
        numbers[i]=listC[indexC];
        indexC++;
    }
}

Вот моя быстрая сортировка

    @Override
public int[] sort(int[] list) {
    int[] array = quickSort(list, 0, list.length-1);
    return array;
}
int partition(int arr[], int left, int right)
{
      int i = left, j = right;
      int tmp;
      int pivot = arr[(left + right) / 2];

      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };

      return i;
}

int[] quickSort(int arr[], int left, int right) {
      int index = partition(arr, left, right);
      if (left < index - 1)
            quickSort(arr, left, index - 1);
      if (index < right)
            quickSort(arr, index, right);
      return arr;
}

Ура!

Answer 1

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

Ключевыми элементами, которые делают эти "легкие" распараллеливания, являются:

• В каждой реализации есть два рекурсивных вызова
• Эти два рекурсивных вызова работают с отдельными частями данных - они не должны конфликтовать друг с другом (например, даже при работе внутри одного и того же).массив, они работают с разными индексами)
• Метод, выполняющий эти рекурсивные вызовы, не может продолжаться, пока оба не будут завершены
• То, что не имеет значения, в каком порядке эти два вызова сделаны в

Это ответ на некоторые ваши вопросы, надеюсь.

---

Еще несколько советов, не уверен, насколько это будет полезно:

• Если вы поставите обарекурсивные вызовы в новый поток, тогда текущий поток будет бездействовать, ожидая, пока они оба завершатся
• Когда число элементов, над которыми осталось работать, малонакладные расходы на многопоточность могут быть выше, чем прирост.
• Возможно, вы захотите ограничить количество потоков, используемых для этой задачи в целом, - вы можете использовать некоторую форму пула потоков или рабочую очередь сфиксированное количество потоков.

Answer 2

Главный совет в этом случае (ошибка, которую я допустил, когда я был у вас на ногах, и я видел, как это делают многие другие) - не допускать, чтобы количество потоков росло без контроля. Помните, что если вы запускаете один поток на каждую ветвь рекурсии, основной поток порождает один дочерний поток (при условии, что один рекурсивный вызов выполняется на самом основном), дочерний поток будет порождать дополнительный поток и так далее, пока вы не закроете систему, если Ваш набор данных большой.

Более понятная альтернатива - запускать один поток на один рекурсивный вызов, так что каждый поток порождает два дочерних потока и затем присоединяет их.

В любом случае, убедитесь, что вы установили ограничение на глубину рекурсии, которая порождает потоки (скажем, равное количеству ядер ЦП), и, если предел превышен, последовательно вызывайте метод сортировки на остальных уровнях.