Для начала посмотрим на общую схему алгоритма Radix Sort, по шагам выполнения:
Итак, возьмём массив двухзначных десятичных чисел (десятичных для упрощения рассуждений), которые нужно отсортировать по возрастанию значений:
12, 10, 45, 29, 74, 32, 11, 47, 22,27.
Для выполнения сортировки нужно создать вспомогательный массив (в текущей статье он называется radix массив). Размер массива должен быть 10 элементов, заметим, что количество элементов должно быть равно максимальному значению числа сортировки (что такое число сортировки будет понятно из дальнейших рассуждений). Вспомогательный массив вначале пуст и выглядит так:
| |
Проход 1 заполнения radix массива.
Начинаем заполнять radix массив: для этого берем первое число из массива сортировки: 12, берем его последнюю цифру (2) и сохраняем число 12 в элементе radix массива с индексом 2, radix массив будет выглядеть так:
| Idx0 |
Idx1 | Idx2 | Idx3 | Idx4 | Idx5 | Idx6 | Idx7 | Idx8 | Idx9 |
| |
12 |
| Idx0 |
Idx1 | Idx2 | Idx3 | Idx4 | Idx5 | Idx6 | Idx7 | Idx8 | Idx9 |
| |
12 | 45 |
| Idx0 |
Idx1 | Idx2 | Idx3 | Idx4 | Idx5 | Idx6 | Idx7 | Idx8 | Idx9 |
| 10 | 11 | 12,32,22 | 74 | 45 | 47,27 | 29 |
После того как все числа скопированы в radix массив копируем их уже в новый массив, начиная с первого элемента radix массива, получится такой результат:
10,11,12,32,22,74,45,47,27,29.
Как видим, исходные числа еще не отсортированы, нужно выполнить дополнительный проход заполнения radix массива (заметим, что для двузначных десятичных чисел всего нужно сделать 2 прохода, для трехзначных 3, для четырехзначных 4, и т.д.).
Проход 2 заполнения radix массива.
Берем первое число из промежуточного массива сортировки: 10, берем его предпоследнюю цифру (1) и сохраняем число 10 в элементе radix массива с индексом 1:
| Idx0 |
Idx1 | Idx2 | Idx3 | Idx4 | Idx5 | Idx6 | Idx7 | Idx8 | Idx9 |
| |
10 |
| Idx0 |
Idx1 | Idx2 | Idx3 | Idx4 | Idx5 | Idx6 | Idx7 | Idx8 | Idx9 |
| |
10,11 |
| Idx0 |
Idx1 | Idx2 | Idx3 | Idx4 | Idx5 | Idx6 | Idx7 | Idx8 | Idx9 |
| |
10,11,12 | 22,27,29 | 32 | 45,47 | 74 |
10,11,12,22,27,29,32,45,47,74.
Сейчас рассмотрим как реализуется запись в radix массив практически, при выполнении кода сортировки на CPU. Понятно, что значения чисел, которыми заполняется radix массив надо где-то хранить, причем делать это максимально быстро (это критически важно для алгоритмов сортировки). В «классической» реализации Radix Sort хранить значения предлагается в самом radix массиве, т.е. каждый элемент это тоже массив, в который записываются исходные числа, как раз здесь скрыта причина высокого расхода памяти. Из-за того, что мы не знаем заранее какие исходные числа нам нужно сортировать, то приходится резервировать место в каждом элементе radix массива под все числа исходного массива. Для нашего упрощенного примера пришлось бы резервировать память в размере 10x10 элементов, в случае же рабочего варианта потребовался бы размер памяти 256*10, что много. Посмотрим иллюстрацию организации памяти radix массива для нашего примера, на втором проходе заполнения:
| |
|||||||||
| |
|||||||||
| |
|||||||||
| |
|||||||||
| |
|||||||||
| |
|||||||||
| |
|||||||||
| |
12 | 29 | |||||||
| |
11 | 27 | 47 | ||||||
| |
10 | 22 | 32 | 45 | 74 |
Как видим, такая схема выделения памяти приводит к ее перерасходу, схема избыточна и затратна. Попробуем найти способ организации radix массива, который не требовал бы перерасхода памяти. Вначале подумаем: а сколько памяти вообще надо? Столько, сколько элементов в исходном массиве! Как же практически реализовать хранение исходных чисел? Автором были рассмотрены разные схемы: динамическое выделение памяти, при такой схеме radix массив выглядит так (упрощенно):
| void* | void* | void* | void* | void* | void* | void* | void* | void* | void* |
Вторая схема заключалась в выделении памяти в дополнительном массиве, числа из одного элемента radix массива хранятся в виде связанного списка, а в radix массиве хранится индекс первого элемента списка.
Оба этих способа позволяют сократить расход памяти до приемлемого уровня, но при практической реализации показали низкую скорость работы: самым медленным оказался способ с динамическим выделением памяти, быстрее был способ использующий связанные списки. Причина низкого быстродействия оказалась в затратном вызове функции перераспределении памяти для первого случая и высоких задержках при случайном доступе к памяти во втором случае.
В результате был найден третий способ, более оптимально использующий память, но требующий дополнительного прохода radix массива после его заполнения (но т.к. в radix массиве небольшое количество элементов, то это приемлемо), итак схема такая: создаем дополнительный массив в котором храним исходные числа, но не в виде связанного списка, а в виде: исходное число, индекс числа в radix массиве. А в radix массиве храним общее количество исходных чисел для каждого элемента radix массива. После прохода 2 эти массивы будут выглядеть так:
Radix массив:
| Idx0 |
Idx1 | Idx2 | Idx3 | Idx4 | Idx5 | Idx6 | Idx7 | Idx8 | Idx9 |
| count: 0 | count: 3 | count: 3 | count: 1 | count: 2 | count: 0 | count: 0 | count: 1 | count: 0 | count: 0 |
| 10,1 | 11,1 | 12,1 | 32,3 | 22,2 | 74,7 | 45,4 | 47,4 | 27,2 | 29,2 |
| Idx0 |
Idx1 | Idx2 | Idx3 | Idx4 | Idx5 | Idx6 | Idx7 | Idx8 | Idx9 |
| IdxR: -1 | IdxR:0 | IdxR:3 | IdxR:6 | IdxR:7 | IdxR: -1 | IdxR: -1 | IdxR:9 | IdxR: -1 | IdxR: -1 |
И наконец заполняем итоговый массив числами из дополнительного массива (используя значения из промежуточного массива): например для первого числа (10,1) позиция копирования будет 0, для четвертого числа (32,3) позиция копирования будет 6, для шестого числа (74,7) позиция копирования будет 9. Если позиция копирования числа уже занята, то ищем первый не занятый элемент в итоговом массиве.
Полученный массив:
10,11,12,22,27,29,32,45,47,74.
Как видим, результат верен.
Описанный способ сортировки был назван Radix Compact, по его свойству: пониженному расходу памяти, по сравнению с оригинальным Radix Sort.
Сейчас сравним общие свойства алгоритма Radix Compact со свойствами алгоритма Quick Sort (для случая сортировки 32-х битных чисел и radix значению 8 бит):
| Radix Compact | Quick Sort | |
| Вычислительная сложность, лучший случай |
N*( 2 ) + 256*1 | N*Log(N) |
| Вычислительная сложность, худший случай |
N*( 8 ) + 256*4 | N2 |
| Дополнительный объем памяти | N + size(radix array) | Log(N) |
| Возможность массивно-параллельного вычисления |
Да | Нет |
| Доступ к памяти | Умеренно случайный | Линейный |
| Локальность данных при обработке (важна для размещения данных в кэше CPU) |
Достаточная | Высокая |
Теоретически алгоритм Radix Compact имеет неплохие характеристики, что же, проверим это на практике. Для начала сравним результаты работы алгоритмов на «домашнем поле» Quick Sort: в однопоточной реализации на массивах 32-х битных чисел:
Тестирование проводилось на CPU Intel i5-3330 (3000 МГц), объем памяти: 16 ГБ, ОС: Windows 8.0 64-бит. Код сортировки Radix Compact написан на C++, реализация Quick Sort: std::sort(). Примечание: тестировался немного доработанный Radix Compact, а так же время работы Radix Compact не включает время выделения памяти.
Как видим, даже в самых выигрышных для Quick Sort условиях Radix Compact превосходит его в скорости работы до 7 раз, проигрывая только на массивах маленького размера (до 100 элементов). Это понятно, т.к. в Radix Compact требуется дополнительная обработка небольшого radix массива, для массивов большого размера это время практически не влияет на результат, но для маленьких массивов оно оказывается существенным. Впрочем в целом результаты Radix Compact вполне достойные. В следующей части статьи я напишу о результате адаптации алгоритма к выполнению на GPU, распараллеливание вычислений обещает дать еще больший выигрыш по сравнению со стандартным Quick Sort.
Комментарии (20)
kmu1990
15.06.2015 18:11После прочтения статьи у меня появилось два вопроса:
- с чего вы взяли, что QuickSort не поддается распараллеливанию? Например, parallel_sort в intel tbb использует QuickSort;
- с чего вы взяли, что QuickSort не использует дополнительной памяти? Классическая рекурсивная реализация использует как минимум log N памяти;
DenGor Автор
15.06.2015 20:181. Имелось в виду массивное распаралливание на GPU, насколько знаю такого нет.
2. Имелась в виду не параллельная версия QSort, в ней работа с массивом идет inplace, не требут дополнительной памяти.
Спасибо что сказали про parallel_sort, интересно сравнить со стандартным QSort, какие-то тесты есть, интересно? Radix Sort тоже можно неплохо распараллелить на несколько CPU, думаю он тоже будет быстрее в этом случае.kmu1990
15.06.2015 20:25Имелось в виду массивное распаралливание на GPU, насколько знаю такого нет.
ок, я неправильно понял фразу в первом параграфе.
не требут дополнительной памяти.
если вы не используете какую-то экзотическую версию QuickSort, то вы не правы. Дополнительная память требуется, как минимум на стек, и в лучшем случае можно добиться, чтобы глубина не превышала log N, но так чтобы свести дополнительную память до константы в QuickSort, я бы с радостью почитал статью про это.DenGor Автор
15.06.2015 20:35ок, я неправильно понял фразу в первом параграфе.
Сейчас попробую поправить статью, буду искать как это сделать.
если вы не используете какую-то экзотическую версию QuickSort, то вы не правы. Дополнительная память требуется, как минимум на стек, и в лучшем случае можно добиться, чтобы глубина не превышала log N, но так чтобы свести дополнительную память до константы в QuickSort, я бы с радостью почитал статью про это.
Т.е. QSort требует памяти Log(N )? Понятно, да, не знал, спасибо что подсказали, опять же попробую поправить.
Mrrl
15.06.2015 23:13Хотите 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-элементный фрагмент.kmu1990
15.06.2015 23:23В QuickSort вы не выбираете размеры подмасивов, вы выбираете опорный элемент, а в зависимости от опорного элемента получаются разные размеры подмасивов, так что ваша стройная теория о делении пополам не работает.
Mrrl
15.06.2015 23:24Почему? Я продолжаю делить тот подмассив, в который попала середина. Как, по-вашему, работает быстрый поиск медианы, и вообще, n-й статистики?
Mrrl
15.06.2015 23:43Другой вариант. После того, как разделили массив на три части (меньше опорного элемента — равные ему — больше его), находим в первой части минимальный элемент, и ставим его в конец этой части. Переходим к сортировке последней части. Чтобы найти начало последней неотсортированной части, берём её последний элемент X, и просматриваем массив в обратную сторону в поисках элемента, меньшего X (это можно делать как линейным, так и бинарным поиском). Первый встреченный (т.е. последний по массиву) такой элемент и будет опорным, неотсортированный фрагмент начинается сразу за ним. Если все просмотренные элементы были больше X, нам надо сортировать начало массива.
То есть, стек кодируется непосредственно порядком элементов.
Число сравнений, к сожалению, в 3-4 раза больше, чем при обычном quicksort.
kvark
15.06.2015 18:39+3Quick Sort, который на данный момент не поддается распараллеливанию
А можно здесь подробнее? Quick Sort ведь классический пример подхода «разделяй и властвуй», который в целом неплохо распараллеливается: разделил массив на 2 части (бОльшую и меньшую, чем якорь) и обрабатывай их параллельно, каждая часть в итоге может ветвиться точно также.
В «классической» реализации Radix Sort хранить значения предлагается в самом radix массиве, т.е. каждый элемент это тоже массив, в который записываются исходные числа, как раз здесь скрыта причина высокого расхода памяти.
Это где вы такую реализацию видели? O_o
Если позиция копирования числа уже занята, то ищем первый не занятый элемент в итоговом массиве.
И далеко вы собираетесь идти искать?
В результате был найден третий способ, более оптимально использующий память, но требующий дополнительного прохода radix массива после его заполнения
Как ваш способ соотносится со стандартной реализацией?
Возможность параллельного вычисления
Не очевидно это. Как вы собираетесь распараллеливать?
Локальность данных при обработке — Достаточная
Финальная фаза, где заполняется результирующий массив, пишет элементы в разные участки памяти на каждой итерации. Трудно придумать сценарий хуже. Вы как-бы и сами пишете, что доступ к памяти «Умеренно случайный», что намекает.DenGor Автор
15.06.2015 20:10+1А можно здесь подробнее? Quick Sort ведь классический пример подхода «разделяй и властвуй», который в целом неплохо распараллеливается: разделил массив на 2 части (бОльшую и меньшую, чем якорь) и обрабатывай их параллельно, каждая часть в итоге может ветвиться точно также.
Про QuickSort: имелось в виду массивно-параллельные вычисления, на GPU, хотелось бы посмотреть на реализацию такого распараллеливания, если это возможно.
В «классической» реализации Radix Sort хранить значения предлагается в самом radix массиве
Это где вы такую реализацию видели? O_o
Нигде, т.к. это взято из доступных описаний алгоритма Radix Sort, видимо практически такой вариант использовать нельзя.
И далеко вы собираетесь идти искать?
Спасибо что вникли в суть рассуждений, но понятно что именно так не собирается никто делать, в реализации схема чуть-чуть посложнее. Написал про поиск чтобы понятнее был ход рассуждений по алгоритму.
Не очевидно это. Как вы собираетесь распараллеливать?
Будет во второй части статьи, пока рано говорить, но вроде бы найден способ, который должен неплохо работать на GPU. Надо делать до конца и тестировать. Вторую часть быстро не обещаю, т.к. статья пишется параллельно с основной работой.
Финальная фаза, где заполняется результирующий массив, пишет элементы в разные участки памяти на каждой итерации. Трудно придумать сценарий хуже. Вы как-бы и сами пишете, что доступ к памяти «Умеренно случайный», что намекает.
Про «умеренный случай» как раз это имелось в виду, написал так, потому что:
1. При чтении массива на первом проходе доступ линейный.
2. Случайная запись гораздо лучше случайного чтения, т.к.: а) в CPU есть буферы записи б) не всегда запись случайная в) в такой ситуации помогают кеши CPU.
Вот поэтому результаты сортировки неплохие по скорости получаются (по сравнению со стандартным QSort), что ж еще надо?
Mrrl
15.06.2015 23:23В итоге вам понадобилось, всё-таки, не менее 2*N ячеек (включая исходный массив)? Достаточно использовать N+R*(K+1) (R^K не меньше диапазона чисел, т.е. 2^32), т.е. хранить K копий счётчиков/указателей элементов — на рекурсию. Сортировать надо будет со старших разрядов, индекс извлекать прямо из значения, а при перекладывании элементов в нужные участки не заботиться об их порядке. По памяти получается экономнее, а по фрагментарности доступа — не хуже, чем со вспомогательным массивом.
boolivar
16.06.2015 01:26+1Да не нужно хранить пары, достаточно завести radix массив размером radix+1 (11 в случае десятичных чисел) и при подсчете адресоваться к элементам idx[i+1], idx[0] не трогать. Затем сделать дополнительный проход по radix массиву, в котором в элементы записать сумму текущего и предыдущего элемента: idx[i] = idx[i] + idx[i-1] (idx[0] остается равным 0). Таким образом, в radix массиве будут индексы, по которым следует писать в вспомогательный массив. В итоге, делая проход по исходному массиву, адресуясь по элементам radix массива и инкрементируя их, можно заполнить вспомогательный массив.
gleb_l
Интересно, а каков оптимальный radix скажем для диапазона int32? 2, 16, 256? Если он мал, то велико количество итераций с генерацией промежуточных результатов, и длина списка в каждой ячейке велика. Если он большой — то сканирование самого radix-массива занимает время…
DenGor Автор
Для чисел int32 на тестах быстрее всего работает сортировка с radix значением 8 бит, т.е. сортировка всего массива выполняется в 4 прохода. Еще сортировка тестировалась с radix значением 16 бит, но размер radix массива получается большой, не влазит в кеш CPU, из-за этого хоть прохода надо 2, но итоговая скорость ниже, да, и проход массива занимает больше времени, конечно
alexeykuzmin0
Вероятно, уже очень скоро размер кеша L1 превысит 256 КБайт, и, соответственно, наиболее эффективным будет использование 16 бит
DenGor Автор
Откуда информация про L1 размером 256 КБайт? По-моему его не делают такого размера из-за проблем с проектированием CPU, то есть просто не могут.