PqDn Feb 5 2018 at 17:02

Реализация параллельной быстрой сортировки при помощи ForkJoinPool

2 min

12K

Tutorial

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

Есть 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. Представлено время в секундах. i7-7700 3.6GHz, 16Гб, 4 ядра

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

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

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

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

Update 1

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

Update 2

Для любителей сортировки подсчетом, время выделения в куче памяти 4Гб составляет около 13 секунд. Это даже без учета сaмой сортировки, что уже хуже любого из представленных вариантов.

Tags:

java

Hubs: