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

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

Есть 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мой сортировки, что уже хуже любого из представленных вариантов.

FavoriteLoadingДобавить в избранное

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *