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

У меня есть однопоточная версия сортировки слиянием 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, то он уже отсортирован. В противном случае:
  • Разделите несортированный список на два подсписка примерно вдвое меньшего размера.
  • Сортируйте каждый подсписок рекурсивно, повторно применяя сортировку слиянием.
  • Объедините два подсписка обратно в один отсортированный список.

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


java multithreading mergesort
person Upvote    schedule 06.05.2011    source источник

Ответы (2)


arrow_upward
4
arrow_downward

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

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

Изменить, чтобы ответить на ваш комментарий:

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

person John Vint    schedule 06.05.2011
comment
Хороший намек. Но на самом деле я хочу свою собственную реализацию для этого. - person Upvote; 06.05.2011
comment
@ArtWorkAD. Вы можете использовать фреймворк, чтобы реализовать его самостоятельно. Статья, на которую я ссылался, была просто для того, чтобы дать вам представление о том, как работает аспект fork/join. - person John Vint; 06.05.2011
comment
@ArtWorkAD однако, чтобы самостоятельно изучить реализацию, я добавил правку. - person John Vint; 06.05.2011

arrow_upward
0
arrow_downward

Используйте класс 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;
    }
} }
person KaviK    schedule 20.01.2014