Реализация рабочих потоков для алгоритма сортировки слиянием - PullRequest
Новая
       0

Реализация рабочих потоков для алгоритма сортировки слиянием

3 голосов
/ 06 мая 2011

У меня есть однопотоковая версия сортировки слиянием http://pastebin.com/2uMGjTxr

Он создает массив, заполняет его случайными числами и вызывает метод сортировки, который выполняет сортировку слиянием: 

private static int[] sort(int[] array) {
    //TODO: use multiple threads to speed up the sorting

    return mergeSort(array, 0, array.length);
}

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

Сортировка слиянием является алгоритмом разделения и завоевания:

  • Если список имеет длину 0 или 1, то он уже отсортирован.В противном случае:
  • Разделите несортированный список на два подсписка размером примерно в половину.
  • Рекурсивно сортируйте каждый подсписок, повторно применив сортировку слиянием.
  • Объедините два подспискав один отсортированный список.

Так что я бы фактически начал поток для каждого подсписка.Как вы думаете?Как сортировка слиянием может быть распараллелена согласно реализации Give?Кто-нибудь знает, почему я должен редактировать метод сортировки?

Ответы [ 2 ]

4 голосов
/ 06 мая 2011

Это отличное упражнение для использования ForkJoin Framework , установленного для выпуска в Java 7.0. Это именно то, что вы ищете. Вы просто отправляете (разворачиваете) задачи рекурсивного слияния в пул и присоединяете результаты по завершении.

Вы можете загрузить JSR 166 Binary . Для получения дополнительной информации это хорошая статья

Изменить адрес вашего комментария:

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

0 голосов
/ 20 января 2014

Использование RecursiveAction класс в Java 7 

public class ParallelMergeSort {

private static final ForkJoinPool threadPool = new ForkJoinPool();
private static final int SIZE_THRESHOLD = 16;

public static void sort(Comparable[] a) {
    sort(a, 0, a.length-1);
}

public static void sort(Comparable[] a, int lo, int hi) {
    if (hi - lo < SIZE_THRESHOLD) {
        insertionsort(a, lo, hi);
        return;
    }

    Comparable[] tmp = new Comparable[a.length];
    threadPool.invoke(new SortTask(a, tmp, lo, hi));
}

/**
 * This class replaces the recursive function that was
 * previously here.
 */
static class SortTask extends RecursiveAction {
    Comparable[] a;
    Comparable[] tmp;
    int lo, hi;
    public SortTask(Comparable[] a, Comparable[] tmp, int lo, int hi) {
        this.a = a;
        this.lo = lo;
        this.hi = hi;
        this.tmp = tmp;
    }

    @Override
    protected void compute() {
        if (hi - lo < SIZE_THRESHOLD) {
            insertionsort(a, lo, hi);
            return;
        }

        int m = (lo + hi) / 2;
        // the two recursive calls are replaced by a call to invokeAll
        invokeAll(new SortTask(a, tmp, lo, m), new SortTask(a, tmp, m+1, hi));
        merge(a, tmp, lo, m, hi);
    }
}

private static void merge(Comparable[] a, Comparable[] b, int lo, int m, int hi) {
    if (a[m].compareTo(a[m+1]) <= 0)
        return;

    System.arraycopy(a, lo, b, lo, m-lo+1);

    int i = lo;
    int j = m+1;
    int k = lo;

    // copy back next-greatest element at each time
    while (k < j && j <= hi) {
        if (b[i].compareTo(a[j]) <= 0) {
            a[k++] = b[i++];
        } else {
            a[k++] = a[j++];
        }
    }

    // copy back remaining elements of first half (if any)
    System.arraycopy(b, i, a, k, j-k);

}

private static void insertionsort(Comparable[] a, int lo, int hi) {
    for (int i = lo+1; i <= hi; i++) {
        int j = i;
        Comparable t = a[j];
        while (j > lo && t.compareTo(a[j - 1]) < 0) {
            a[j] = a[j - 1];
            --j;
        }
        a[j] = t;
    }
} }
...