Где-то чуть меньше года назад во время поиска работы, после окончания курсов в Иннополисе один из потенциальных работодателей дал вот такое задание.
Есть 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)
kemply
05.02.2018 18:00В 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 реализовать сортировку этим же методом?
nsinreal
06.02.2018 22:19Ага, в Java тоже есть GC. И на всякий случай: у вас есть гарантия когда уничтожится переменная, но нет гарантии когда уничтожится объект на который указывает переменная.
PqDn Автор
06.02.2018 23:35temp[] в худшем случае будет весить 4-8 гига
а теперь представим, что req отсортирован, и его значения [..., 1/4млд, 1/2млд, 1млд]
Тогда при каждой итерации
будет внутренний массив temp переаллоцирован (то есть будет заново выделятся массив в два раза больше)
Мне даже страшно предположить сколько времени потребуется, хотя можно предположить, если взять из моего теста время на аллокацию (13 сек на 4 гига), то это будет сумма такого ряда {13 сек, 13сек/2, 13сек/4 ...} Это же самое настоящие зависание программы будет
Причем Res так же будет много раз переаллоцирован, хоть на нем так проблема и не будет заметна, по сравнению с первым.
А теперь представим, что минимальный квант информации в js 8 байт (x64). Делайте выводы
по памяти в худшем случае
9,600 Гб на одни ток данные (тоесть если у вас мало оперативки, то хип будет захватывать стек и наоборот, а потом крах)nsinreal
07.02.2018 00:50Нет, неверно. Я наконец-то понял о чем говорил этот товарищ.
Вот этот вот код в js отработает моментально:
let a = []; a[1000 * 1000 * 1000] = 1;
Потому что в js массивы могут быть разреженными. Интересная особенность языка, о которой легко забыть. И тогда они внутре хранятся точно также как HashMap (или OrderedMap, в зависимости от реализации движка).
temp в таком случае будет весить порядка 100 млн умноженное на константу (для 16 байт это будет порядка 1.6гб)
Если это распараллелить, то по памяти примерно 1.6гб и выйдет.
А вот комбинирование результатов угарное. Асимптотика для непараллельного алгоритма будет порядка O(maxValue + arrayLength), но амортизированная.PqDn Автор
07.02.2018 08:24Ну я предлагаю бенчи для данного алгоритма на js предоставить.
Кстати если рассуждать теоретически, то хеш таблица с увеличением — перестраиваться, а это извините большие накладные расходы.
Потом если числа будут иметь плохие хеши, то велика вероятность что время доступа (к одному элементу) в вырожденном случае будет либо n, либо log(n) в зависимости от реализации в интерпретаторе
Не имеет смысла что-то говорить о js в плане производительно без полноценных тестов. Простота несёт огромные расходы
KazAndrey
05.02.2018 18:08Можно ещё быстрее. Подсчитаем сколько раз каждое число встречается в массиве. А затем просто в цикле от 0 до 1 миллиарда будем проверять входит ли i в map и если да то выводим i ровно map[i] раз.
PqDn Автор
05.02.2018 18:09Это неэффективно, т.к. диапазон намного больше самого массива
KazAndrey
05.02.2018 18:10По памяти но не по скорости.
PqDn Автор
05.02.2018 18:13скриншот в студию )
Причем желательно, чтоб вы и мой тест при этом повторили, клонируйте мой проектKazAndrey
05.02.2018 18:29+1Я не java разработчик а python и c++. Считаем теоретическую сложность. Пробежаться и посчитать сколько каждое число встречается это O(n). Вывести результат это тоже будет O(n). И того O(2n) => сложность O(n). Но это при условии что нет коллизии. Для этого заранее можно выделить размер под 1 миллиард переменных. Поэтому я и сказал, что проигрываем по памяти, а по скорости O(n) вместо O(nlogn).
PqDn Автор
05.02.2018 18:35На самом деле время выделения в хипе 4х гигов, если они еще будут, больше чем представленная параллельная сортировка.
К слову выделение памяти 400Мб у меня больше секунды шло
MikailBag
05.02.2018 23:38Нет. Это две разные линии. Время работы такой программы — это примерно O(N + 2**K) для K — разрядных чисел. Т.е. на плохих тестах вообще экспоненциальное.
3aicheg
06.02.2018 06:23Откуда? Это ж, вроде, обычная «сортировка подсчётом», сложность O(n + k), где, для данного случая, n = 100 000 (размер массива), k = 1 000 000 000 (число возможных элементов). Смысл, правда, оно имеет только при k << n, что не наш случай, но даже в нашем случае n*log(n) = 1842068074, а n+k = 1000100000, т. е. быстрее почти в два раза.
PqDn Автор
06.02.2018 08:20тут наверно в бой вступают таинственные множители m*n, где m некоторой целое число )
MikailBag
07.02.2018 17:47-1Ок. тест
Два числа.
Первое — К нулей
Второе — К единиц
Время работы программы — O(2 ** K).
Размер входных данных — O(K).
Т.е. на таком тесте алгоритм работает за экспоненциальное от размера входных данных время.
dikhim
06.02.2018 08:21Сортировка подсчетом. Для этого есть навание. Так будет бьстрее, но чтобы держать в памяти массив в млрд значений нужно потратить 1млрд * 4 байт, не много не мало а 4гб
dougrinch
05.02.2018 18:41+1Вот что нашел при быстром поиске (возможно есть еще что-то, но не копал уже).
1. В java-сообществе уже давно публиковать бенчи не на jmh считается неприлично.
2. Ваш вариант с int v = a[lo]; все-таки уж очень плохой. Если запустить повторную сортировку на массиве из примера, то ее результата мы уже никогда не дождемся. Банальная замена на int v = a[ThreadLocalRandom.current().nextInt(lo, hi + 1)]; полностью все исправляет.
3. Сравнение со стримами тоже плохое. Вы сортируете массив на месте, а стримы создают новый не трогая исходный.
4. В связи с последним особенно интересно что памяти ваш вариант выделяет столько же, сколько и стримы.
Но вообще очень показательно получилось. Очень хорошо видно что на таком кол-ве данных в первую очередь важна именно асимптотика, и не смотря на все отличия/оптимизации в решении, итоговый результат зависит от них довольно мало.PqDn Автор
05.02.2018 20:301 полностью согласен
2 приятно, что вы и по ссылке гита прошлись )
3 умолчал специально
4 стримы жрут всяко больше памяти
dougrinch
05.02.2018 21:17Ну так я же не сам придумал. Честно, был безумно удивлен когда это обнаружил. На что именно уходит память не анализировал еще. Получается что 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 посмотреть что там происходит.
PqDn Автор
05.02.2018 21:34могу предположить, что это хип заполняется экземплярами SortAction
dougrinch
05.02.2018 21:50Очевидное предположение, но хотелось проверить. Да, именно они. У меня получается их 16-19кк обычно. По 40 байт на каждый. 840кк все равно не получается, но тут уже близко очень. Может не везет просто. Ладно, я всё. Дальнейший анализ оставляю вам.
Karpion
05.02.2018 20:00Судя по фразе «от 0 до 1млрд» — речь о целых числах. В таком случае отлично годится «Быстрая сортировка Хоара» (она — вполне «на уровне 11 класса»), причём на каждом шаге мы берём среднее арифметическое между самым большим и самым маленьким элементом сортируемой части массива. Потребуется 30 раз просмотреть весь массив («30» — это количество битов, в которых можно разместить числа в диапазоне «от 0 до 1млрд»).
Ну и потребуется рекурсия с глубиной в те же 30 итераций или менее. Тут надо не забыть, что рекурсивно надо сортировать только меньшую половину массива, а остальную часть массива — итерационно, т.к. там сразу за рекурсивным вызовом следует возврат.
trigun117
06.02.2018 08:22Недавно на Go делал сортировки, вот результат: imgur.com/a/5ZniZ, вот код: gist.github.com/trigun117/5ba95f9eef17ceb35b8a8c58330d7be3
mayorovp
06.02.2018 12:27Для любителей сортировки подсчетом, время выделения в куче памяти 4Гб составляет около 13 секунд. Это даже без учета сaмой сортировки, что уже хуже любого из представленных вариантов.
Можно использовать поразрядную сортировку. Диапазон в 1 миллиард легко разбивается на 2 разряда по 4 и 5 знаков. Или можно даже разряды от 0 до 31622 сделать.
nsinreal
06.02.2018 22:071) Фоллбек к bubble sort на отрезке длины 16 это замечательно.
2) Мне кажется, что не стоит параллелить до упора — накладные расходы никто не отменял. Подозреваю, что можно форсировать отсутствие параллельного режима на отрезках длины порядка 10^3
3) Для последовательной сортировки популярна оптимизация через хвостовую рекурсию. Мне кажется, что в данном конкретном случае выигрыш будет еще больше. Но не уверен.
4) Я не очень хорошо знаком с Java. Скажите, поле типа final int (не static) будет выброшено из экземпляра класса или будет занимать лишнее место?
5) А нет никаких веселых эффектов связанных с тем, что сбрасываете кэши из-за малых размеров блоков?
youROCK
Я думаю, что здесь даже можно было бы наверное обойтись без быстрой сортировки и просто выставлять битики в массиве на 125 млн char’ов (или байтов). И потом в цикле вывести :). Не знаю, насколько было бы медленней или быстрее, но памяти бы точно меньше потратили.
svr_91
Числа ведь могут повторяться. Так что битиками тут не обойтись. Скорее на каждое число по 4 байта нужно (итого 4 гб)
Akon32
Меньше: 100млн.чисел по 4 байта — примерно 400МБ.
Akon32
Впрочем, я ошибся.
PqDn Автор
Тут по памяти используется только исходный массив, доп ресурсы практически не выделяются
MikailBag
И это даже работать быстрее может (а может и нет, потому что не параллелится и константа большая) — если Вы про Radix Sort, то её сложность O(NK), а для QuickSort — O(NlogNK), где К разрядов.