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

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

Поддержать автора
Поделиться публикацией

Комментарии 36

    0
    Я думаю, что здесь даже можно было бы наверное обойтись без быстрой сортировки и просто выставлять битики в массиве на 125 млн char’ов (или байтов). И потом в цикле вывести :). Не знаю, насколько было бы медленней или быстрее, но памяти бы точно меньше потратили.
      0
      Числа ведь могут повторяться. Так что битиками тут не обойтись. Скорее на каждое число по 4 байта нужно (итого 4 гб)
        0

        Меньше: 100млн.чисел по 4 байта — примерно 400МБ.

          0

          Впрочем, я ошибся.

        0
        Тут по памяти используется только исходный массив, доп ресурсы практически не выделяются
          0

          И это даже работать быстрее может (а может и нет, потому что не параллелится и константа большая) — если Вы про Radix Sort, то её сложность O(NK), а для QuickSort — O(NlogNK), где К разрядов.

          –1
          В JavaScript можно реализовать так:
          function Sort(req){
            var temp, res = [];
          
            for(let i =0; i != req.length; ++i)
              temp[ req[i] ] = true;
          
            for(let i in temp){
              if( typeof temp[i] !== "undefined"  )
                res.push( temp[i] );
            }
          
            return res;
          }
          


          В данном случае можно не создавать вложенные циклы для 100 млн'ого массива. Конечно, на некоторое время массив res будет весить очень много из-за млрд пустых элементов, но после выхода из функции переменная будет уничтожена и не будет утечки памяти.

          Так вот, можно ли на Java реализовать сортировку этим же методом?
            0
            Скорее всего тут будет stack overflow
              0
              Ага, в Java тоже есть GC. И на всякий случай: у вас есть гарантия когда уничтожится переменная, но нет гарантии когда уничтожится объект на который указывает переменная.
                0
                temp[] в худшем случае будет весить 4-8 гига

                а теперь представим, что req отсортирован, и его значения [..., 1/4млд, 1/2млд, 1млд]
                Тогда при каждой итерации
                будет внутренний массив temp переаллоцирован (то есть будет заново выделятся массив в два раза больше)

                Мне даже страшно предположить сколько времени потребуется, хотя можно предположить, если взять из моего теста время на аллокацию (13 сек на 4 гига), то это будет сумма такого ряда {13 сек, 13сек/2, 13сек/4 ...} Это же самое настоящие зависание программы будет

                Причем Res так же будет много раз переаллоцирован, хоть на нем так проблема и не будет заметна, по сравнению с первым.

                А теперь представим, что минимальный квант информации в js 8 байт (x64). Делайте выводы

                по памяти в худшем случае
                9,600 Гб на одни ток данные (тоесть если у вас мало оперативки, то хип будет захватывать стек и наоборот, а потом крах)
                  0
                  Нет, неверно. Я наконец-то понял о чем говорил этот товарищ.

                  Вот этот вот код в js отработает моментально:
                  let a = [];
                  a[1000 * 1000 * 1000] = 1;
                  


                  Потому что в js массивы могут быть разреженными. Интересная особенность языка, о которой легко забыть. И тогда они внутре хранятся точно также как HashMap (или OrderedMap, в зависимости от реализации движка).

                  temp в таком случае будет весить порядка 100 млн умноженное на константу (для 16 байт это будет порядка 1.6гб)
                  Если это распараллелить, то по памяти примерно 1.6гб и выйдет.

                  А вот комбинирование результатов угарное. Асимптотика для непараллельного алгоритма будет порядка O(maxValue + arrayLength), но амортизированная.
                    0
                    Ну я предлагаю бенчи для данного алгоритма на js предоставить.
                    Кстати если рассуждать теоретически, то хеш таблица с увеличением — перестраиваться, а это извините большие накладные расходы.
                    Потом если числа будут иметь плохие хеши, то велика вероятность что время доступа (к одному элементу) в вырожденном случае будет либо n, либо log(n) в зависимости от реализации в интерпретаторе
                    Не имеет смысла что-то говорить о js в плане производительно без полноценных тестов. Простота несёт огромные расходы
                0
                А что с повторениями?
                0
                Можно ещё быстрее. Подсчитаем сколько раз каждое число встречается в массиве. А затем просто в цикле от 0 до 1 миллиарда будем проверять входит ли i в map и если да то выводим i ровно map[i] раз.
                  0
                  Это неэффективно, т.к. диапазон намного больше самого массива
                    0
                    По памяти но не по скорости.
                      +1
                      скриншот в студию )
                      Причем желательно, чтоб вы и мой тест при этом повторили, клонируйте мой проект
                        +1
                        Я не java разработчик а python и c++. Считаем теоретическую сложность. Пробежаться и посчитать сколько каждое число встречается это O(n). Вывести результат это тоже будет O(n). И того O(2n) => сложность O(n). Но это при условии что нет коллизии. Для этого заранее можно выделить размер под 1 миллиард переменных. Поэтому я и сказал, что проигрываем по памяти, а по скорости O(n) вместо O(nlogn).
                          0
                          На самом деле время выделения в хипе 4х гигов, если они еще будут, больше чем представленная параллельная сортировка.
                          К слову выделение памяти 400Мб у меня больше секунды шло
                            0

                            Нет. Это две разные линии. Время работы такой программы — это примерно O(N + 2**K) для K — разрядных чисел. Т.е. на плохих тестах вообще экспоненциальное.

                              0
                              Откуда? Это ж, вроде, обычная «сортировка подсчётом», сложность O(n + k), где, для данного случая, n = 100 000 (размер массива), k = 1 000 000 000 (число возможных элементов). Смысл, правда, оно имеет только при k << n, что не наш случай, но даже в нашем случае n*log(n) = 1842068074, а n+k = 1000100000, т. е. быстрее почти в два раза.
                                0
                                тут наверно в бой вступают таинственные множители m*n, где m некоторой целое число )
                                  –1

                                  Ок. тест
                                  Два числа.
                                  Первое — К нулей
                                  Второе — К единиц
                                  Время работы программы — O(2 ** K).
                                  Размер входных данных — O(K).
                                  Т.е. на таком тесте алгоритм работает за экспоненциальное от размера входных данных время.

                        0
                        Сортировка подсчетом. Для этого есть навание. Так будет бьстрее, но чтобы держать в памяти массив в млрд значений нужно потратить 1млрд * 4 байт, не много не мало а 4гб
                        +2
                        Вот что нашел при быстром поиске (возможно есть еще что-то, но не копал уже).

                        1. В java-сообществе уже давно публиковать бенчи не на jmh считается неприлично.
                        2. Ваш вариант с int v = a[lo]; все-таки уж очень плохой. Если запустить повторную сортировку на массиве из примера, то ее результата мы уже никогда не дождемся. Банальная замена на int v = a[ThreadLocalRandom.current().nextInt(lo, hi + 1)]; полностью все исправляет.
                        3. Сравнение со стримами тоже плохое. Вы сортируете массив на месте, а стримы создают новый не трогая исходный.
                        4. В связи с последним особенно интересно что памяти ваш вариант выделяет столько же, сколько и стримы.

                        Но вообще очень показательно получилось. Очень хорошо видно что на таком кол-ве данных в первую очередь важна именно асимптотика, и не смотря на все отличия/оптимизации в решении, итоговый результат зависит от них довольно мало.
                          0
                          1 полностью согласен
                          2 приятно, что вы и по ссылке гита прошлись )
                          3 умолчал специально
                          4 стримы жрут всяко больше памяти

                            0

                            Ну так я же не сам придумал. Честно, был безумно удивлен когда это обнаружил. На что именно уходит память не анализировал еще. Получается что QuickSort и Arrays.sort не выделяют ничего. Arrays.parallelSort выделяет 400кк байт — это ровно еще один наш массив интов (и там действительно внутри есть new int[n]). А вот стримы (независимо от параллельности) и ParallelQuickSort выделяют дополнительно 800кк.


                            Более того, в стримах результат очень стабильный и там 800кк почти ровно.


                            Benchmark                            Mode  Cnt          Score            Error   Units
                            SortBench.sort:·gc.alloc.rate.norm   avgt    5  800036601.600 ±        839.235    B/op

                            А вот в ParallelQuickSort какой-то расколбас.


                            Benchmark                            Mode  Cnt          Score            Error   Units
                            SortBench.sort:·gc.alloc.rate.norm   avgt    5  840529246.400 ±    126746.361    B/op

                            Надо через jmc посмотреть что там происходит.

                              0
                              могу предположить, что это хип заполняется экземплярами SortAction
                                0
                                Очевидное предположение, но хотелось проверить. Да, именно они. У меня получается их 16-19кк обычно. По 40 байт на каждый. 840кк все равно не получается, но тут уже близко очень. Может не везет просто. Ладно, я всё. Дальнейший анализ оставляю вам.
                                  0
                                  Спасибо. Было приятно поддержать диалог
                          0
                          Судя по фразе «от 0 до 1млрд» — речь о целых числах. В таком случае отлично годится «Быстрая сортировка Хоара» (она — вполне «на уровне 11 класса»), причём на каждом шаге мы берём среднее арифметическое между самым большим и самым маленьким элементом сортируемой части массива. Потребуется 30 раз просмотреть весь массив («30» — это количество битов, в которых можно разместить числа в диапазоне «от 0 до 1млрд»).
                          Ну и потребуется рекурсия с глубиной в те же 30 итераций или менее. Тут надо не забыть, что рекурсивно надо сортировать только меньшую половину массива, а остальную часть массива — итерационно, т.к. там сразу за рекурсивным вызовом следует возврат.
                            0
                            сети сортировок изначально допускающие хорошее распараллеливание типа Бетчера/bitonic/pairwise даже не рассматривали?
                              0
                              нет, даже не слышал честно говоря.
                              0
                              Недавно на Go делал сортировки, вот результат: imgur.com/a/5ZniZ, вот код: gist.github.com/trigun117/5ba95f9eef17ceb35b8a8c58330d7be3
                                +1
                                Для любителей сортировки подсчетом, время выделения в куче памяти 4Гб составляет около 13 секунд. Это даже без учета сaмой сортировки, что уже хуже любого из представленных вариантов.

                                Можно использовать поразрядную сортировку. Диапазон в 1 миллиард легко разбивается на 2 разряда по 4 и 5 знаков. Или можно даже разряды от 0 до 31622 сделать.

                                  0
                                  1) Фоллбек к bubble sort на отрезке длины 16 это замечательно.
                                  2) Мне кажется, что не стоит параллелить до упора — накладные расходы никто не отменял. Подозреваю, что можно форсировать отсутствие параллельного режима на отрезках длины порядка 10^3
                                  3) Для последовательной сортировки популярна оптимизация через хвостовую рекурсию. Мне кажется, что в данном конкретном случае выигрыш будет еще больше. Но не уверен.
                                  4) Я не очень хорошо знаком с Java. Скажите, поле типа final int (не static) будет выброшено из экземпляра класса или будет занимать лишнее место?
                                  5) А нет никаких веселых эффектов связанных с тем, что сбрасываете кэши из-за малых размеров блоков?

                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                  Самое читаемое