Резюме. Мы обсуждаем здесь наилучшие способы оптимизации сортировки больших массивов составных объектов по нечисловым ключам. Также рассматривается способ уменьшения количества выполняемых операций (сложность) имеющихся алгоритмов сортировки. Конкретный базовый алгоритм сортировки выбирается разработчиком по своему усмотрению (см. условие 1 в замечаниях).
Введение: Проблематикой имплементации паралелльной сортировки занимаются разные специалисты по всему миру. Подавляющее число специалистов рассматривает платформы GPU и их суперскалярность как эффективную (в вычислительном плане) базу для разработки новых алгоритмов. На Хабре исследованиями в этой области занимались [KS1], [KILY1], [PatZ1], [Ms1].
Стоит отметить несколько минусов выбранного авторами похода:
объем обрабатываемого массива жестко ограничен возможностями оборудования
в исследованиях уделяется вопрос сортировки исключительно простых типов данных: натуральных чисел; вопрос сортировки более сложных и составных типов не рассматривается
при сортировке на GPU отсутствует возможность эффективной работы с указателями; как следствие сложно обеспечить сортировку составных объектов, по не числовым/составным ключам, особенно, когда сортируемые объекты хранятся во внешней памяти
проблема останова (трудно в концепции SIMD сформировать условие завершения работы алгоритма)
Автор полагает, что приведенные недостатки при сортировке на GPU и подобных суперскалярных платформах (использование концепции SIMD вообще), являются фундаментально неустранимыми.
Проведенные автором методики полностью лишены указанных недостатков, более ̶ позволяют разработчику выбирать базовый алгоритм сортировки в соответствии с требованиями к результату (устойчивость, память, ..), однако требует соблюдения следующих условий:
Условие 1: К описанной далее оптимизации склонны только алгоритмы со сложностью в худшем и среднем случаях O(NlogN)
Условие 2: Сортируемые объекты должны быть способны к группировке (кластеризации) по своим ключам[1]
Условие 3: Объекты одного класса (элементы одной группы), должны быть строго меньше/больше объектов других классов.
[1] Например сортируемыми объектами могут выступать записи вида {name: 'latin_string', age: number, born: date}, хранимые на жестком диске. Здесь сортируемый ключ: поле 'name' объектов - английская строка неопределенной длины
Условие3 позволяет упорядочивать группы объектов между собой.
Как показали исследования условиям 2 и 3 соответствуют не только объекты с числовыми ключами, но и со строковыми (текстовыми), логическими и вещественными ключами (см. ниже "кластеризация объектов с не числовыми ключами")
Рассмотрим алогоритм сортировки со сложностью 
и массив из N объектов (удовлетворяющих условиям 2 и 3). Выполним кластеризацию элементов и разобьем массив на k>0 групп (предельное значение k определяется природой сортируемых объектов). Отсортируем каждую группу объектов независимо от других. При этом (учитывая условие 1) мы потратим в среднем 
операций.А на независимую сортировку всех k групп мы потратим в среднем ![k*[N/k log (N/k) ]](https://habrastorage.org/getpro/habr/upload_files/fc5/e5a/f3f/fc5e5af3f1ffd2d5eada146f37b66509.svg)
. Преобразуя это выражение получим:
(2)
Из (2) видно, что суммарное число потраченных на сортировку операций снижается. Как не трудно заметить чем выше k (больше групп в исходном массиве), тем меньше итоговая (конечная) сложность сортировки. В купе с возможностью сортировки каждой группы элементов массива независимо, такой подход открывает путь для построения высокоэффективных алгоритмов сортировки без строгих ограничений на объем и природу сортируемых данных.
Сортировка массива таким способом требует предварительной обработки: кластеризации элементов. Наиболее эффективным алгоритмом кластеризации со сложностью O(n) является поразрядная сортировка (называемая другими авторами "Американский флаг" [VM2]). Данный класс алгоритмов способен к потоковой обработке массива в один проход, а также допускает паралеллизацию (с неизбежным интенсивным обменом между процессами по кластеризации). В качестве дополнительного бонуса предварительной обработки сортируемого массива является возможность проведения аналитики массива. Возможно массив вообще не требует сортировки или элементы одного класса (группы) уже упорядочены и данная группа может быть исключена из обработки.
кластеризация объектов с нечисловыми ключами. Кластеризация объектов, ключи которых представляют собой текстовые строки, может производиться по первым буквам строк, порождая тем самым 26 групп. Возможно снизить количество групп, объединяя уже сами буквы в группы. Например, все объекты с ключами, начинающимися с букв a-f относят к группе 0, начинающимися с букв g-l относят к группе 1, и так далее.
Кластеризация объектов с ключами в виде вещественных чисел легко производится по диапазонам значений (предварительно необходимо уточнить реальные границы ключей: мин.макс).
Измерения. Автором был проверен предложенный подход на практике, с получением следующих результатов (табл.1). Сбор статистики осуществлял специальный прокси-массив, подсчитывающий реальное число обменов, сравнений и обращений к ключам сортируемых объектов. Сортировка производилась при помощи алгоритмов "Плавная сортировка" и "Сортировка восходящей кучей".В полученных данных учтены также операции, выполненные на этапах кластеризации массива.
Таблица 1. Подсчет выполненных операций над массивами при разных техниках сортировки:
N/k | обменов | сравнений | доступов к указателю | перезаписей указателя | обращений к ключу |
64/1 | 356 | 390 | 611 | 452 | 908 |
64/16 | 232 | 260 | 356 | 264 | 520 |
512/1 | 4319 | 4683 | 6366 | 5087 | 10390 |
512/16 | 3422 | 3691 | 4442 | 3678 | 7382 |
10k/1 | 126855 | 135333 | 166854 | 141855 | 290666 |
10k/16 | 110872 | 118006 | 130868 | 115872 | 236012 |
1M/16 | 19283612 | 20130313 | 23283611 | 20783612 | 42260626 |
| 17668264 | 18434186 | 19668260 | 18168264 | 36868372 |
первая строка таблицы - затраты на сортировку массива из 64 элементов целиком
вторая строка таблицы - затраты на сортировку того же массива, после разделения на 16 частей
третья строка - затраты на сортировку массива 512 элементов
четвертая строка - затраты на сортировку того же массива после разделения на 16 частей
последние две строки таблицы - данные о сортировке массива из 1 млн. элементов (стоит обратить внимание, что сортировка такого массива 16ю независимыми частями сокращает на 14 млн. число выполняемых операций даже с учетом операций по предварительной кластеризации поразрядной сортировкой)
Ссылки на другие работы по теме:
[KS1] Параллельная сортировка методом пузырька на CUDA
[KILY1] Сортировка массивов фиксированной длины с применением SIMD
[PatZ1] Параллельная сортировка данных в GPU
[Ms1] Параллельный метод сортировки массива std::thread
[VM2] Сортировка «Американский флаг»