Comments 42
Я думаю, что здесь даже можно было бы наверное обойтись без быстрой сортировки и просто выставлять битики в массиве на 125 млн char’ов (или байтов). И потом в цикле вывести :). Не знаю, насколько было бы медленней или быстрее, но памяти бы точно меньше потратили.
Числа ведь могут повторяться. Так что битиками тут не обойтись. Скорее на каждое число по 4 байта нужно (итого 4 гб)
Тут по памяти используется только исходный массив, доп ресурсы практически не выделяются
И это даже работать быстрее может (а может и нет, потому что не параллелится и константа большая) — если Вы про Radix Sort, то её сложность O(NK), а для QuickSort — O(NlogNK), где К разрядов.
В JavaScript можно реализовать так:
В данном случае можно не создавать вложенные циклы для 100 млн'ого массива. Конечно, на некоторое время массив res будет весить очень много из-за млрд пустых элементов, но после выхода из функции переменная будет уничтожена и не будет утечки памяти.
Так вот, можно ли на Java реализовать сортировку этим же методом?
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 реализовать сортировку этим же методом?
Скорее всего тут будет stack overflow
Ага, в Java тоже есть GC. И на всякий случай: у вас есть гарантия когда уничтожится переменная, но нет гарантии когда уничтожится объект на который указывает переменная.
temp[] в худшем случае будет весить 4-8 гига
а теперь представим, что req отсортирован, и его значения [..., 1/4млд, 1/2млд, 1млд]
Тогда при каждой итерации
будет внутренний массив temp переаллоцирован (то есть будет заново выделятся массив в два раза больше)
Мне даже страшно предположить сколько времени потребуется, хотя можно предположить, если взять из моего теста время на аллокацию (13 сек на 4 гига), то это будет сумма такого ряда {13 сек, 13сек/2, 13сек/4 ...} Это же самое настоящие зависание программы будет
Причем Res так же будет много раз переаллоцирован, хоть на нем так проблема и не будет заметна, по сравнению с первым.
А теперь представим, что минимальный квант информации в js 8 байт (x64). Делайте выводы
по памяти в худшем случае
9,600 Гб на одни ток данные (тоесть если у вас мало оперативки, то хип будет захватывать стек и наоборот, а потом крах)
а теперь представим, что req отсортирован, и его значения [..., 1/4млд, 1/2млд, 1млд]
Тогда при каждой итерации
будет внутренний массив temp переаллоцирован (то есть будет заново выделятся массив в два раза больше)
Мне даже страшно предположить сколько времени потребуется, хотя можно предположить, если взять из моего теста время на аллокацию (13 сек на 4 гига), то это будет сумма такого ряда {13 сек, 13сек/2, 13сек/4 ...} Это же самое настоящие зависание программы будет
Причем Res так же будет много раз переаллоцирован, хоть на нем так проблема и не будет заметна, по сравнению с первым.
А теперь представим, что минимальный квант информации в js 8 байт (x64). Делайте выводы
по памяти в худшем случае
9,600 Гб на одни ток данные (тоесть если у вас мало оперативки, то хип будет захватывать стек и наоборот, а потом крах)
Нет, неверно. Я наконец-то понял о чем говорил этот товарищ.
Вот этот вот код в js отработает моментально:
Потому что в js массивы могут быть разреженными. Интересная особенность языка, о которой легко забыть. И тогда они внутре хранятся точно также как HashMap (или OrderedMap, в зависимости от реализации движка).
temp в таком случае будет весить порядка 100 млн умноженное на константу (для 16 байт это будет порядка 1.6гб)
Если это распараллелить, то по памяти примерно 1.6гб и выйдет.
А вот комбинирование результатов угарное. Асимптотика для непараллельного алгоритма будет порядка O(maxValue + arrayLength), но амортизированная.
Вот этот вот код в js отработает моментально:
let a = [];
a[1000 * 1000 * 1000] = 1;
Потому что в js массивы могут быть разреженными. Интересная особенность языка, о которой легко забыть. И тогда они внутре хранятся точно также как HashMap (или OrderedMap, в зависимости от реализации движка).
temp в таком случае будет весить порядка 100 млн умноженное на константу (для 16 байт это будет порядка 1.6гб)
Если это распараллелить, то по памяти примерно 1.6гб и выйдет.
А вот комбинирование результатов угарное. Асимптотика для непараллельного алгоритма будет порядка O(maxValue + arrayLength), но амортизированная.
Ну я предлагаю бенчи для данного алгоритма на js предоставить.
Кстати если рассуждать теоретически, то хеш таблица с увеличением — перестраиваться, а это извините большие накладные расходы.
Потом если числа будут иметь плохие хеши, то велика вероятность что время доступа (к одному элементу) в вырожденном случае будет либо n, либо log(n) в зависимости от реализации в интерпретаторе
Не имеет смысла что-то говорить о js в плане производительно без полноценных тестов. Простота несёт огромные расходы
Кстати если рассуждать теоретически, то хеш таблица с увеличением — перестраиваться, а это извините большие накладные расходы.
Потом если числа будут иметь плохие хеши, то велика вероятность что время доступа (к одному элементу) в вырожденном случае будет либо n, либо log(n) в зависимости от реализации в интерпретаторе
Не имеет смысла что-то говорить о js в плане производительно без полноценных тестов. Простота несёт огромные расходы
А что с повторениями?
Можно ещё быстрее. Подсчитаем сколько раз каждое число встречается в массиве. А затем просто в цикле от 0 до 1 миллиарда будем проверять входит ли i в map и если да то выводим i ровно map[i] раз.
Это неэффективно, т.к. диапазон намного больше самого массива
По памяти но не по скорости.
скриншот в студию )
Причем желательно, чтоб вы и мой тест при этом повторили, клонируйте мой проект
Причем желательно, чтоб вы и мой тест при этом повторили, клонируйте мой проект
Я не java разработчик а python и c++. Считаем теоретическую сложность. Пробежаться и посчитать сколько каждое число встречается это O(n). Вывести результат это тоже будет O(n). И того O(2n) => сложность O(n). Но это при условии что нет коллизии. Для этого заранее можно выделить размер под 1 миллиард переменных. Поэтому я и сказал, что проигрываем по памяти, а по скорости O(n) вместо O(nlogn).
На самом деле время выделения в хипе 4х гигов, если они еще будут, больше чем представленная параллельная сортировка.
К слову выделение памяти 400Мб у меня больше секунды шло
К слову выделение памяти 400Мб у меня больше секунды шло
Нет. Это две разные линии. Время работы такой программы — это примерно O(N + 2**K) для K — разрядных чисел. Т.е. на плохих тестах вообще экспоненциальное.
Откуда? Это ж, вроде, обычная «сортировка подсчётом», сложность O(n + k), где, для данного случая, n = 100 000 (размер массива), k = 1 000 000 000 (число возможных элементов). Смысл, правда, оно имеет только при k << n, что не наш случай, но даже в нашем случае n*log(n) = 1842068074, а n+k = 1000100000, т. е. быстрее почти в два раза.
Сортировка подсчетом. Для этого есть навание. Так будет бьстрее, но чтобы держать в памяти массив в млрд значений нужно потратить 1млрд * 4 байт, не много не мало а 4гб
Вот что нашел при быстром поиске (возможно есть еще что-то, но не копал уже).
1. В java-сообществе уже давно публиковать бенчи не на jmh считается неприлично.
2. Ваш вариант с int v = a[lo]; все-таки уж очень плохой. Если запустить повторную сортировку на массиве из примера, то ее результата мы уже никогда не дождемся. Банальная замена на int v = a[ThreadLocalRandom.current().nextInt(lo, hi + 1)]; полностью все исправляет.
3. Сравнение со стримами тоже плохое. Вы сортируете массив на месте, а стримы создают новый не трогая исходный.
4. В связи с последним особенно интересно что памяти ваш вариант выделяет столько же, сколько и стримы.
Но вообще очень показательно получилось. Очень хорошо видно что на таком кол-ве данных в первую очередь важна именно асимптотика, и не смотря на все отличия/оптимизации в решении, итоговый результат зависит от них довольно мало.
1. В java-сообществе уже давно публиковать бенчи не на jmh считается неприлично.
2. Ваш вариант с int v = a[lo]; все-таки уж очень плохой. Если запустить повторную сортировку на массиве из примера, то ее результата мы уже никогда не дождемся. Банальная замена на int v = a[ThreadLocalRandom.current().nextInt(lo, hi + 1)]; полностью все исправляет.
3. Сравнение со стримами тоже плохое. Вы сортируете массив на месте, а стримы создают новый не трогая исходный.
4. В связи с последним особенно интересно что памяти ваш вариант выделяет столько же, сколько и стримы.
Но вообще очень показательно получилось. Очень хорошо видно что на таком кол-ве данных в первую очередь важна именно асимптотика, и не смотря на все отличия/оптимизации в решении, итоговый результат зависит от них довольно мало.
1 полностью согласен
2 приятно, что вы и по ссылке гита прошлись )
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 посмотреть что там происходит.
могу предположить, что это хип заполняется экземплярами SortAction
Очевидное предположение, но хотелось проверить. Да, именно они. У меня получается их 16-19кк обычно. По 40 байт на каждый. 840кк все равно не получается, но тут уже близко очень. Может не везет просто. Ладно, я всё. Дальнейший анализ оставляю вам.
Спасибо. Было приятно поддержать диалог
А есть какие-либо минусы у параллельной сортировки стримами?
Судя по фразе «от 0 до 1млрд» — речь о целых числах. В таком случае отлично годится «Быстрая сортировка Хоара» (она — вполне «на уровне 11 класса»), причём на каждом шаге мы берём среднее арифметическое между самым большим и самым маленьким элементом сортируемой части массива. Потребуется 30 раз просмотреть весь массив («30» — это количество битов, в которых можно разместить числа в диапазоне «от 0 до 1млрд»).
Ну и потребуется рекурсия с глубиной в те же 30 итераций или менее. Тут надо не забыть, что рекурсивно надо сортировать только меньшую половину массива, а остальную часть массива — итерационно, т.к. там сразу за рекурсивным вызовом следует возврат.
Ну и потребуется рекурсия с глубиной в те же 30 итераций или менее. Тут надо не забыть, что рекурсивно надо сортировать только меньшую половину массива, а остальную часть массива — итерационно, т.к. там сразу за рекурсивным вызовом следует возврат.
сети сортировок изначально допускающие хорошее распараллеливание типа Бетчера/bitonic/pairwise даже не рассматривали?
Недавно на Go делал сортировки, вот результат: imgur.com/a/5ZniZ, вот код: gist.github.com/trigun117/5ba95f9eef17ceb35b8a8c58330d7be3
Для любителей сортировки подсчетом, время выделения в куче памяти 4Гб составляет около 13 секунд. Это даже без учета сaмой сортировки, что уже хуже любого из представленных вариантов.
Можно использовать поразрядную сортировку. Диапазон в 1 миллиард легко разбивается на 2 разряда по 4 и 5 знаков. Или можно даже разряды от 0 до 31622 сделать.
1) Фоллбек к bubble sort на отрезке длины 16 это замечательно.
2) Мне кажется, что не стоит параллелить до упора — накладные расходы никто не отменял. Подозреваю, что можно форсировать отсутствие параллельного режима на отрезках длины порядка 10^3
3) Для последовательной сортировки популярна оптимизация через хвостовую рекурсию. Мне кажется, что в данном конкретном случае выигрыш будет еще больше. Но не уверен.
4) Я не очень хорошо знаком с Java. Скажите, поле типа final int (не static) будет выброшено из экземпляра класса или будет занимать лишнее место?
5) А нет никаких веселых эффектов связанных с тем, что сбрасываете кэши из-за малых размеров блоков?
2) Мне кажется, что не стоит параллелить до упора — накладные расходы никто не отменял. Подозреваю, что можно форсировать отсутствие параллельного режима на отрезках длины порядка 10^3
3) Для последовательной сортировки популярна оптимизация через хвостовую рекурсию. Мне кажется, что в данном конкретном случае выигрыш будет еще больше. Но не уверен.
4) Я не очень хорошо знаком с Java. Скажите, поле типа final int (не static) будет выброшено из экземпляра класса или будет занимать лишнее место?
5) А нет никаких веселых эффектов связанных с тем, что сбрасываете кэши из-за малых размеров блоков?
Sign up to leave a comment.
Реализация параллельной быстрой сортировки при помощи ForkJoinPool