Реализация параллельной быстрой сортировки при помощи ForkJoinPool05.02.2018 23:33

habr.png

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


Есть 100 млн. чисел, каждое из которых от 0 до 1 млрд.
Нужно отсортировать по возрастанию.
В самом начале программа случайно их заполняет, а потом сортирует.


Подвох был в том, что туже самую таску давали и другим выпускникам нашего курса. Задание дали на дом на 1 день, после скайп интервью.


Сразу стало понятно, что реализация сортировки на уровне 11 класса, тут не прокатит.


Двигаясь от простого к сложному, реализовал сначало обычную быструю сортировку


Быстрая сортировка
/**
 * Классический алгоритм быстрой сортировки
 */
public class QuickSort extends AbstractQuickSort {
    public void sort(int[] a) {
        sort(a, 0, a.length - 1);
    }

    private void sort(int[] a, int lo, int hi) {
        if(hi <= lo) return;

        // Находим средний элемент
        int j = partition(a, lo, hi);

        // Рекусивное вызов левой / правой подчасти
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }
}


Затем алгоритм распараллелил, при помощи ForkJoinPool


Параллельная быстрая сортировка
/**
 * Классический алгоритм быстрой сортировки с применением fork join для распаралеливания вычеслений
 */
public class ParallelQuickSort extends AbstractQuickSort {
    public void sort(int[] a) {
        ForkJoinPool.commonPool().invoke(new SortAction(a, 0, a.length - 1));
    }

    /**
     * Реализация ForkJoinTask для рекурсивной сортировки частей массива
     */
    private class SortAction extends RecursiveAction{
        private final int bubbleBlock = 16;

        int[] a;
        int lo;
        int hi;

        SortAction(int[] a, int lo, int hi) {
            this.a = a;
            this.lo = lo;
            this.hi = hi;
        }

        @Override
        protected void compute() {
            if(hi <= lo) return;

            if ((hi - lo) > bubbleBlock) {
                // Находим средний элемент
                int j = partition(a, lo, hi);

                // Рекусивное вызов левой / правой подчасти
                invokeAll(new SortAction(a, lo, j - 1), new SortAction(a, j + 1, hi));
            }else{
                // Для маленького массива применим пызырьковую сортировку
                bubbleSort(a, lo, hi + 1);
            }
        }

        /**
         * Сортировка пузырьком, для ускорении сортировки маленьких подблоков
         */
        private void bubbleSort(int[] a, int lo, int hi){
            for (int i = lo; i < hi; i++) {
                for (int j = i; j < hi; j++) {
                    if (a[i] > a[j]) {
                        int tmp = a[i];
                        a[i] = a[j];
                        a[j] = tmp;
                    }
                }
            }
        }
    }
}


Для проверки качества решения, сравню полученные алгоритмы с сортировкой Stream API. Представлено время в секундах.


Алгоритм Моя быстрая сортировка Stream API
Обычный 11,64 10,2
Параллельный 5,02 3,9


Неудивительно, что моё решение менее производительно, по сравнению с нативной реализацией в Stream API. Главное — порядок тот же, свою задачу я выполнил, получил прирост в скорости после распараллеливания.


Интервьюер дал положительную обратную связь. Однако в ту компанию я так и не устроился, так как меня перехватили в другой компании, где я собеседовался в то же время.


1) Ссылка на гит
2) Книга где взял базовый алгоритм


Update 1


Ребята в статье речь прежде всего идет про внедрение ForkJoinPool, а не про саму быструю сортировку.

© Habrahabr.ru