Комментарии 23
Интересно, а каков оптимальный radix скажем для диапазона int32? 2, 16, 256? Если он мал, то велико количество итераций с генерацией промежуточных результатов, и длина списка в каждой ячейке велика. Если он большой — то сканирование самого radix-массива занимает время…
Для чисел int32 на тестах быстрее всего работает сортировка с radix значением 8 бит, т.е. сортировка всего массива выполняется в 4 прохода. Еще сортировка тестировалась с radix значением 16 бит, но размер radix массива получается большой, не влазит в кеш CPU, из-за этого хоть прохода надо 2, но итоговая скорость ниже, да, и проход массива занимает больше времени, конечно
После прочтения статьи у меня появилось два вопроса:
- с чего вы взяли, что QuickSort не поддается распараллеливанию? Например, parallel_sort в intel tbb использует QuickSort;
- с чего вы взяли, что QuickSort не использует дополнительной памяти? Классическая рекурсивная реализация использует как минимум log N памяти;
1. Имелось в виду массивное распаралливание на GPU, насколько знаю такого нет.
2. Имелась в виду не параллельная версия QSort, в ней работа с массивом идет inplace, не требут дополнительной памяти.
Спасибо что сказали про parallel_sort, интересно сравнить со стандартным QSort, какие-то тесты есть, интересно? Radix Sort тоже можно неплохо распараллелить на несколько CPU, думаю он тоже будет быстрее в этом случае.
2. Имелась в виду не параллельная версия QSort, в ней работа с массивом идет inplace, не требут дополнительной памяти.
Спасибо что сказали про parallel_sort, интересно сравнить со стандартным QSort, какие-то тесты есть, интересно? Radix Sort тоже можно неплохо распараллелить на несколько CPU, думаю он тоже будет быстрее в этом случае.
Имелось в виду массивное распаралливание на GPU, насколько знаю такого нет.
ок, я неправильно понял фразу в первом параграфе.
не требут дополнительной памяти.
если вы не используете какую-то экзотическую версию QuickSort, то вы не правы. Дополнительная память требуется, как минимум на стек, и в лучшем случае можно добиться, чтобы глубина не превышала log N, но так чтобы свести дополнительную память до константы в QuickSort, я бы с радостью почитал статью про это.
ок, я неправильно понял фразу в первом параграфе.
Сейчас попробую поправить статью, буду искать как это сделать.
если вы не используете какую-то экзотическую версию QuickSort, то вы не правы. Дополнительная память требуется, как минимум на стек, и в лучшем случае можно добиться, чтобы глубина не превышала log N, но так чтобы свести дополнительную память до константы в QuickSort, я бы с радостью почитал статью про это.
Т.е. QSort требует памяти Log(N )? Понятно, да, не знал, спасибо что подсказали, опять же попробую поправить.
Хотите Quicksort без памяти на стек? Это очень просто, но, разумеется, увеличит время.
1) Вспоминаем, что с помощью разделения массива, используемого в quicksort, мы можем разделить его на две части произвольно заданного размера (0..K-1 и K..N-1) в среднем за O(N) операций, причём без использования рекурсии;
2) Учимся без рекурсии перебирать фрагменты массива, длина которых равна степени двойки, а смещение — кратно этой степени. Причём отрезки перебираем в порядке уменьшения длины.
3) Каждый такой отрезок делим на две части с помощью алгоритма из п.1. Если правая часть не пересекается с сортируемым массивом, ничего не делаем.
Так, для массива из 13 элементов нам надо будет выполнить деления:
0-7 и 8-12
0-3 и 4-7
8-11 и 12-12
0-1 и 2-3
4-5 и 6-7
8-9 и 10-11
и упорядочить каждый 2-элементный фрагмент.
1) Вспоминаем, что с помощью разделения массива, используемого в quicksort, мы можем разделить его на две части произвольно заданного размера (0..K-1 и K..N-1) в среднем за O(N) операций, причём без использования рекурсии;
2) Учимся без рекурсии перебирать фрагменты массива, длина которых равна степени двойки, а смещение — кратно этой степени. Причём отрезки перебираем в порядке уменьшения длины.
3) Каждый такой отрезок делим на две части с помощью алгоритма из п.1. Если правая часть не пересекается с сортируемым массивом, ничего не делаем.
Так, для массива из 13 элементов нам надо будет выполнить деления:
0-7 и 8-12
0-3 и 4-7
8-11 и 12-12
0-1 и 2-3
4-5 и 6-7
8-9 и 10-11
и упорядочить каждый 2-элементный фрагмент.
В QuickSort вы не выбираете размеры подмасивов, вы выбираете опорный элемент, а в зависимости от опорного элемента получаются разные размеры подмасивов, так что ваша стройная теория о делении пополам не работает.
Почему? Я продолжаю делить тот подмассив, в который попала середина. Как, по-вашему, работает быстрый поиск медианы, и вообще, n-й статистики?
Другой вариант. После того, как разделили массив на три части (меньше опорного элемента — равные ему — больше его), находим в первой части минимальный элемент, и ставим его в конец этой части. Переходим к сортировке последней части. Чтобы найти начало последней неотсортированной части, берём её последний элемент X, и просматриваем массив в обратную сторону в поисках элемента, меньшего X (это можно делать как линейным, так и бинарным поиском). Первый встреченный (т.е. последний по массиву) такой элемент и будет опорным, неотсортированный фрагмент начинается сразу за ним. Если все просмотренные элементы были больше X, нам надо сортировать начало массива.
То есть, стек кодируется непосредственно порядком элементов.
Число сравнений, к сожалению, в 3-4 раза больше, чем при обычном quicksort.
То есть, стек кодируется непосредственно порядком элементов.
Число сравнений, к сожалению, в 3-4 раза больше, чем при обычном quicksort.
Quick Sort, который на данный момент не поддается распараллеливанию
А можно здесь подробнее? Quick Sort ведь классический пример подхода «разделяй и властвуй», который в целом неплохо распараллеливается: разделил массив на 2 части (бОльшую и меньшую, чем якорь) и обрабатывай их параллельно, каждая часть в итоге может ветвиться точно также.
В «классической» реализации Radix Sort хранить значения предлагается в самом radix массиве, т.е. каждый элемент это тоже массив, в который записываются исходные числа, как раз здесь скрыта причина высокого расхода памяти.
Это где вы такую реализацию видели? O_o
Если позиция копирования числа уже занята, то ищем первый не занятый элемент в итоговом массиве.
И далеко вы собираетесь идти искать?
В результате был найден третий способ, более оптимально использующий память, но требующий дополнительного прохода radix массива после его заполнения
Как ваш способ соотносится со стандартной реализацией?
Возможность параллельного вычисления
Не очевидно это. Как вы собираетесь распараллеливать?
Локальность данных при обработке — Достаточная
Финальная фаза, где заполняется результирующий массив, пишет элементы в разные участки памяти на каждой итерации. Трудно придумать сценарий хуже. Вы как-бы и сами пишете, что доступ к памяти «Умеренно случайный», что намекает.
А можно здесь подробнее? Quick Sort ведь классический пример подхода «разделяй и властвуй», который в целом неплохо распараллеливается: разделил массив на 2 части (бОльшую и меньшую, чем якорь) и обрабатывай их параллельно, каждая часть в итоге может ветвиться точно также.
Про QuickSort: имелось в виду массивно-параллельные вычисления, на GPU, хотелось бы посмотреть на реализацию такого распараллеливания, если это возможно.
В «классической» реализации Radix Sort хранить значения предлагается в самом radix массиве
Это где вы такую реализацию видели? O_o
Нигде, т.к. это взято из доступных описаний алгоритма Radix Sort, видимо практически такой вариант использовать нельзя.
И далеко вы собираетесь идти искать?
Спасибо что вникли в суть рассуждений, но понятно что именно так не собирается никто делать, в реализации схема чуть-чуть посложнее. Написал про поиск чтобы понятнее был ход рассуждений по алгоритму.
Не очевидно это. Как вы собираетесь распараллеливать?
Будет во второй части статьи, пока рано говорить, но вроде бы найден способ, который должен неплохо работать на GPU. Надо делать до конца и тестировать. Вторую часть быстро не обещаю, т.к. статья пишется параллельно с основной работой.
Финальная фаза, где заполняется результирующий массив, пишет элементы в разные участки памяти на каждой итерации. Трудно придумать сценарий хуже. Вы как-бы и сами пишете, что доступ к памяти «Умеренно случайный», что намекает.
Про «умеренный случай» как раз это имелось в виду, написал так, потому что:
1. При чтении массива на первом проходе доступ линейный.
2. Случайная запись гораздо лучше случайного чтения, т.к.: а) в CPU есть буферы записи б) не всегда запись случайная в) в такой ситуации помогают кеши CPU.
Вот поэтому результаты сортировки неплохие по скорости получаются (по сравнению со стандартным QSort), что ж еще надо?
Спасибо за статью. Во второй части статьи (radix на GPU) очень хотелось бы посмотреть на сравнение radix с bitonic.
В итоге вам понадобилось, всё-таки, не менее 2*N ячеек (включая исходный массив)? Достаточно использовать N+R*(K+1) (R^K не меньше диапазона чисел, т.е. 2^32), т.е. хранить K копий счётчиков/указателей элементов — на рекурсию. Сортировать надо будет со старших разрядов, индекс извлекать прямо из значения, а при перекладывании элементов в нужные участки не заботиться об их порядке. По памяти получается экономнее, а по фрагментарности доступа — не хуже, чем со вспомогательным массивом.
Да не нужно хранить пары, достаточно завести radix массив размером radix+1 (11 в случае десятичных чисел) и при подсчете адресоваться к элементам idx[i+1], idx[0] не трогать. Затем сделать дополнительный проход по radix массиву, в котором в элементы записать сумму текущего и предыдущего элемента: idx[i] = idx[i] + idx[i-1] (idx[0] остается равным 0). Таким образом, в radix массиве будут индексы, по которым следует писать в вспомогательный массив. В итоге, делая проход по исходному массиву, адресуясь по элементам radix массива и инкрементируя их, можно заполнить вспомогательный массив.
хочется проду
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Алгоритм сортировки Radix Compact. Часть 1: реализация на CPU