Comments 42
И это даже работать быстрее может (а может и нет, потому что не параллелится и константа большая) — если Вы про Radix Sort, то её сложность O(NK), а для QuickSort — O(NlogNK), где К разрядов.
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 реализовать сортировку этим же методом?
а теперь представим, что req отсортирован, и его значения [..., 1/4млд, 1/2млд, 1млд]
Тогда при каждой итерации
будет внутренний массив temp переаллоцирован (то есть будет заново выделятся массив в два раза больше)
Мне даже страшно предположить сколько времени потребуется, хотя можно предположить, если взять из моего теста время на аллокацию (13 сек на 4 гига), то это будет сумма такого ряда {13 сек, 13сек/2, 13сек/4 ...} Это же самое настоящие зависание программы будет
Причем Res так же будет много раз переаллоцирован, хоть на нем так проблема и не будет заметна, по сравнению с первым.
А теперь представим, что минимальный квант информации в js 8 байт (x64). Делайте выводы
по памяти в худшем случае
9,600 Гб на одни ток данные (тоесть если у вас мало оперативки, то хип будет захватывать стек и наоборот, а потом крах)
Вот этот вот код в js отработает моментально:
let a = [];
a[1000 * 1000 * 1000] = 1;
Потому что в js массивы могут быть разреженными. Интересная особенность языка, о которой легко забыть. И тогда они внутре хранятся точно также как HashMap (или OrderedMap, в зависимости от реализации движка).
temp в таком случае будет весить порядка 100 млн умноженное на константу (для 16 байт это будет порядка 1.6гб)
Если это распараллелить, то по памяти примерно 1.6гб и выйдет.
А вот комбинирование результатов угарное. Асимптотика для непараллельного алгоритма будет порядка O(maxValue + arrayLength), но амортизированная.
Кстати если рассуждать теоретически, то хеш таблица с увеличением — перестраиваться, а это извините большие накладные расходы.
Потом если числа будут иметь плохие хеши, то велика вероятность что время доступа (к одному элементу) в вырожденном случае будет либо n, либо log(n) в зависимости от реализации в интерпретаторе
Не имеет смысла что-то говорить о js в плане производительно без полноценных тестов. Простота несёт огромные расходы
Причем желательно, чтоб вы и мой тест при этом повторили, клонируйте мой проект
К слову выделение памяти 400Мб у меня больше секунды шло
Нет. Это две разные линии. Время работы такой программы — это примерно O(N + 2**K) для K — разрядных чисел. Т.е. на плохих тестах вообще экспоненциальное.
1. В java-сообществе уже давно публиковать бенчи не на jmh считается неприлично.
2. Ваш вариант с int v = a[lo]; все-таки уж очень плохой. Если запустить повторную сортировку на массиве из примера, то ее результата мы уже никогда не дождемся. Банальная замена на int v = a[ThreadLocalRandom.current().nextInt(lo, hi + 1)]; полностью все исправляет.
3. Сравнение со стримами тоже плохое. Вы сортируете массив на месте, а стримы создают новый не трогая исходный.
4. В связи с последним особенно интересно что памяти ваш вариант выделяет столько же, сколько и стримы.
Но вообще очень показательно получилось. Очень хорошо видно что на таком кол-ве данных в первую очередь важна именно асимптотика, и не смотря на все отличия/оптимизации в решении, итоговый результат зависит от них довольно мало.
2 приятно, что вы и по ссылке гита прошлись )
3 умолчал специально
4 стримы жрут всяко больше памяти
Ну так я же не сам придумал. Честно, был безумно удивлен когда это обнаружил. На что именно уходит память не анализировал еще. Получается что 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 посмотреть что там происходит.
Ну и потребуется рекурсия с глубиной в те же 30 итераций или менее. Тут надо не забыть, что рекурсивно надо сортировать только меньшую половину массива, а остальную часть массива — итерационно, т.к. там сразу за рекурсивным вызовом следует возврат.
Для любителей сортировки подсчетом, время выделения в куче памяти 4Гб составляет около 13 секунд. Это даже без учета сaмой сортировки, что уже хуже любого из представленных вариантов.
Можно использовать поразрядную сортировку. Диапазон в 1 миллиард легко разбивается на 2 разряда по 4 и 5 знаков. Или можно даже разряды от 0 до 31622 сделать.
2) Мне кажется, что не стоит параллелить до упора — накладные расходы никто не отменял. Подозреваю, что можно форсировать отсутствие параллельного режима на отрезках длины порядка 10^3
3) Для последовательной сортировки популярна оптимизация через хвостовую рекурсию. Мне кажется, что в данном конкретном случае выигрыш будет еще больше. Но не уверен.
4) Я не очень хорошо знаком с Java. Скажите, поле типа final int (не static) будет выброшено из экземпляра класса или будет занимать лишнее место?
5) А нет никаких веселых эффектов связанных с тем, что сбрасываете кэши из-за малых размеров блоков?
Реализация параллельной быстрой сортировки при помощи ForkJoinPool