ПОЛУЧЕНИЕ ОПТИМАЛЬНОЙ ПРОИЗВОДИТЕЛЬНОСТИ АЛГОРИТМА СОРТИРОВКИ ЗА СЧЕТ СОЧЕТАНИЯ РАЗЛИЧНЫХ ПРИЕМОВ

GETTING OPTIMAL SORTING ALGORITHM PERFORMANCE BY COUNTING COMBINATIONS OF DIFFERENT TECHNIQUES

Egor Barsukov

student, Department of Comtutational Mathematics and Programming, Moscow Aviation Institute (National Research University) (MAI),

Russia, Moscow

АННОТАЦИЯ

Практически любая программа так или иначе использует алгоритмы сортировки. Без их помощи невозможно представить работу фильтров на сайтах, отображение списков файлов в проводнике Windows, работу с базами данных и так далее. Именно поэтому производительность таких алгоритмов является одним из важнейших вопросов, который исследуется до сих пор. Оптимальная производительность достигается не только за счёт использования новых алгоритмов, но и путем особой комбинации уже существующих. Примером такой комбинации других алгоритмов является Pattern-defeating quicksort.

ABSTRACT

Almost any program uses sorting algorithms in one way or another. Without their help, it is impossible to imagine how filters work on websites, displaying file lists in Windows Explorer, working with databases, and so on. That is why the performance of such algorithms is one of the most important issues that is still being investigated. Optimal performance is achieved not only through the use of new algorithms, but also through a special combination of existing ones. An example of such a combination of other algorithms is the Pattern-defeating quicksort.

Ключевые слова: алгоритмы сортировки, quicksort, производительность.

Keywords: sorting algorithms, quicksort, performance.

ВВЕДЕНИЕ

Традиционно принято измерять производительность алгоритмов с помощью O-нотации (О-большое нотации). O-большое позволяет сравнить асимптотическое поведение функций – т.е. характер изменения функции при стремлении ее аргумента к заданному значению.

Обычно замеры производительности алгоритмов сортировки делят на три случая: худший, средний и лучший. Все три являются показательными и на них стоит обращать внимание. Наиболее популярные алгоритмы, такие как, например, quicksort, или «быстрая сортировка», показывают очень хорошие результаты производительности во всех случаях – O(N*log(N)), где N – размер исходного массива данных для сортировки.

ПРОБЛЕМАТИКА

Алгоритм быстрой сортировки основан на стратегии «разделяй и властвуй». Принцип работы состоит в выборе опорного элемента – пивота (pivot). Все элементы меньше пивота перемещаются в левую часть сортируемого массива, а большие – в правую часть. Действия рекурсивно повторяются для левой и правой частей массива, пока массив будет не отсортирован. Алгоритм не зря называется «быстрой сортировкой», описанные выше действия позволяют эффективно сортировать большие массивы данных. Однако, у quicksort есть свои особенности, которые стоит учитывать при работе. Время работы алгоритма напрямую зависит от выбора пивота. Если пивот выбран правильно, это позволяет существенно ускорить алгоритм. Существуют различные алгоритмы оптимального выбора пивота. Скорость выполнения так же может уменьшиться из-за особых паттернов в массиве, например, когда массив отсортирован в обратном порядке или когда он является почти отсортированным (за исключением одного элемента).

ВЫБОР ТЕХНОЛОГИЙ

Для частичного устранения недостатков и оптимизации работы quicksort Орсоном Р. Л. Питерсом был предложен алгоритм Pattern-defeating quicksort - pdqsort (сортировка с устранением шаблонов). Новый алгоритм сортировки сочетает быстрый средний случай быстрой сортировки с быстрым наихудшим случаем сортировки по куче (heap sort), а также обеспечивает при этом линейное время обработки входных данных с определенными шаблонами – например, если массив уже является почти отсортированным. Сортировка с помощью pdqsort не является стабильной – т.е. при наличии в исходном массиве двух одинаковых по значению элементов их относительный порядок может измениться.

Разберем работу алгоритма в составе стандартной библиотеки языка Golang (Go). Сигнатура алгоритма выглядит следующим образом:

pdqsort(data Interface, a, b, limit int)

Функция сортирует массив data[a:b], где limit – заданное максимальное число плохо выбранных пивотов (при превышении limit функция переключится на сортировку с использованием heap sort). Данные должны удовлетворять интерфейсу Interface – т.е. должны реализовывать методы

Len() int;

Less(i, j int) bool;

Swap(i, j int)

Массивы в Golang по умолчанию реализуют интерфейс Interface. В начале алгоритма определена константа:

maxInsertion = 12

Опытным путем было определено, что для массивов длины меньшей либо равной maxInsertion, эффективнее всего использовать сортировку вставками. Далее будет описан основной цикл работы алгоритма.

Выполняется проверка на длину исходного массива и переход к сортировке вставками в соответствующем случае (если длина менее, чем maxInsertion). Если limit стал нулевым – т.е. если мы исчерпали число попыток выбора пивота – выполняется переход к сортировке на куче (heap sort).

В ходе работы используются две булевы переменные – wasBalanced и wasPartitioned. Переменная wasBalanced определяет, сбалансирован ли сортируемый массив на данный момент. Критерием сбалансированности Питерсом была выбрана длина подмассивов, образованных разделением исходного массива пивотом. Если длина подмассива больше, чем одна восьмая от длины массива – считается, что массив сбалансирован. Это соотношение было определено опытным путем Питерсом, который описал его в виде графика, изображенного на рисунке 1.

Рисунок 1. Отношение p-factor

Здесь p – положение пивота в массиве. Чем оно ближе к 0.5, тем более сбалансированным считается распределение данных в массиве. Factor показывает отклонение от идеального случая времени сортировки. Данный график так же показывает, почему быстрая сортировка, лежащая в основе pdqsort, в целом является настолько быстрой – при достаточно сильном отклонении пивота от идеального мы все равно получаем относительно небольшое ухудшение производительности (по сравнению с другими популярными алгоритмами). Переменная wasPartitioned показывает, был ли произведен шаг разбиения quicksort.

Далее следует выбор пивота. Это важный шаг, который помогает pdqsort избегать худших случаев, которые могут привести к временной сложности O(N^2). Для небольших массивов (менее 8 элементов) используется статический пивот – обычно, центральный. В случае массивов длины до 50 элементов применяется метод медианы трех – выбирается три элемента i, j, k из разных частей массива, а пивотом считается их медиана. Для больших массивов, длиной более или равной 50 элементов, используется метод Tukey’s ninther. Он вычисляет медиану трех соседних элементов для каждого из i, j, k, а затем из полученных значений снова выбирается медиана, которая становится пивотом.

На данном этапе так же определяется hint – «подсказка», которая помогает алгоритму «угадать» характер упорядоченности массива. increasingHint возвращается в том случае, если есть основания полагать, что он может быть уже отсортирован по возрастанию (при вычислении медиан было использовано 0 перестановок внутри массива), выполняется частичная сортировка вставками. decreasingHint – обратный случай, возвращается при числе перестановок меньшем, чем заданный maxSwaps – 12. Массив будет инвертирован. В остальных случаях возвращается unknownHint – не удалось определить характер упорядоченности массива.

Массив проверяется на дубликаты – если рассматриваемая левая граница массива a больше 0 и элемент перед a меньше пивота, выполняется группировка равных элементов вместе, что ускоряет обработку.

В финальной части цикла выполняется стандартный шаг алгоритма quicksort, массив разбивается по пивоту, обновляется wasBalanced и wasPartitioned. Описанные шаги рекурсивно запускаются для полученных подмассивов.

Все описанные выше оптимизации дают pdqsort прирост производительности по времени относительно quicksort и сложность во всех случаях O(N*log(N)).

ОПИСАНИЕ РАБОТЫ

Проведем анализ производительности. Для этого напишем программу на языке Go, реализующую quicksort. Реализация pdqsort встроена в Go как сортировка по умолчанию и поэтому не требует дополнительной реализации. Для целей демонстрации сортировать во всех разобранных случаях будем целые числа (тип int).

func quicksort(arr []int) {

    if len(arr) < 2 {

             return

    }

    pivotIdx := rand.Intn(len(arr))

    pivot := arr[pivotIdx]

    left, right := 0, len(arr)-1

    arr[pivotIdx], arr[right] = arr[right], arr[pivotIdx]

    for i := range arr {

             if arr[i] < pivot {

                       arr[i], arr[left] = arr[left], arr[i]

                       left++

             }

    }

    arr[left], arr[right] = arr[right], arr[left]

    quicksort(arr[:left])

    quicksort(arr[left+1:])

}

Реализуем вспомогательные функции. Функция generateRandomArray создает случайный массив заданной длины size, значения элементов которого находятся в диапазоне от 0 до 1000000. Функция generateUniformArray создает массив из size элементов, все из которых равны value. Функция generateReversedArray возвращает массив длины size, отсортированный в обратном порядке, а функция generateAscWithOneOut создает возврастающий массив длины size, а после меняет 2 элемента местами.

func generateRandomArray(size int) []int {

    arr := make([]int, size)

    for i := range arr {

             arr[i] = rand.Intn(1000000)

    }

    return arr

}

func generateReversedArray(size int) []int {

    arr := generateRandomArray(size)

    quicksort(arr)

    for i := 0; i < len(arr)/2; i++ {

             arr[i], arr[len(arr)-1-i] = arr[len(arr)-1-i], arr[i]

    }

    return arr

}

func generateUniformArray(size int, value int) []int {

    arr := make([]int, size)

    for i := range arr {

             arr[i] = value

    }

    return arr

}

func generateAscWithOneOut(size int) []int {

    arr := make([]int, size)

    for i := range arr {

             arr[i] = i

    }

    arr[size-1], arr[size/2] = arr[size/2], arr[size-1]

    return arr

}

Данные функции потребуются для анализа производительности quicksort и pdqsort в краевых случаях – т.е. в случае, если массив почти отсортирован, если он отсортирован в обратном порядке или если массив состоит из одинаковых по значению элементов.

Реализуем функцию benchmarkSort, которая будет проводить замер времени на сортировку переданного массива arr с помощью sortFunc. Возвращаться будет объект типа time.Duration – время, затраченное на сортировку.

func benchmarkSort(sortFunc func([]int), arr []int) time.Duration {

  arrCopy := make([]int, len(arr))

  copy(arrCopy, arr)

  start := time.Now()

  sortFunc(arrCopy)

  return time.Since(start)

}

ДЕМОНСТРАЦИЯ РАБОТЫ

Запустим тестирование для массивов трех длин: 50000, 100000 и 200000 элементов. Тестирование проводилось на процессоре Intel Core i7-9700 на ОС Windows 10. Результаты представлены в таблицах 1, 2, 3, а также визуализированы на рисунке 2. Видно, что pdqsort действительно работает быстрее, чем quicksort в особенных случаях. В ряде тестов pdqsort отработал за время, меньшее чем разрядность time.Duration. Такие результаты отображаются как 0s, и для наглядности округлены в большую сторону до 0.001ms.

Таблица 1.

Сравнение производительности pdqsort и quicksort (размер исходного массива – 50000 элементов)

Таблица 2.

Сравнение производительности pdqsort и quicksort (размер исходного массива – 100000 элементов)

Таблица 3.

Сравнение производительности pdqsort и quicksort (размер исходного массива – 200000 элементов)

Рисунок 2. Сравнение производительности quicksort и pdqsort

ЗАКЛЮЧЕНИЕ И ВЫВОДЫ

Сочетание различных алгоритмов сортировки и учет особых случаев действительно повышает производительность алгоритмов сортировки. В ходе исследований было выявлено, что наибольший прирост производительности наблюдается при сортировке массива, в котором все элементы одинаковы по значению, т.к. предварительный анализ массива позволяет избежать сортировки. В зависимости от области применения алгоритма, такой паттерн может довольно часто встречаться во входных данных. Однако, выявление особых случаев занимает некоторое время, из-за чего наблюдается небольшое ухудшение производительности в случае случайного входного массива. Можно сделать вывод, что применение различных алгоритмов и приемов для сортировки действительно повышает производительность сортировки, особенно в том случае, если данные имеют некую упорядоченность и/или придерживаются некого паттерна.

Список литературы:

1. orlp/pdqsort: Pattern-defeating quicksort. : сайт. – URL: https://github.com/orlp/pdqsort (дата обращения: 09.03.2024)
2. Orson R. L. Peters, Pattern-defeating Quicksort : сайт – URL: https://arxiv.org/pdf/2106.05123 (дата обращения: 09.03.2024)
3. Алан А. А. Донован, Брайан У. Керниган Язык программирования Go [Текст] / Алан А. А. Донован, Брайан У. Керниган — Москва: Вильямс, 2018 — 432 c.