Начал оптимизировать сортировку в своем диссертационном проекте, всплыла прекрасная иллюстрация такого понятия как вычислительная сложность алгоритма.

Тестовый массив - 4 миллиона элементов (классов, содержащих поле типа double, по которому и осуществляется сортировка).

Проверил четыре варианта сортировки массива:
1. Стандартный метод Array.Sort, предоставляемый c# из коробки (под капотом там quicksort O(n*log(n)), как писал выше). Результат - 2.2 секунды
2. Нагугленная реализация quicksort O(n*log(n)) для c#. Результат - 2.7 секунды
3. Нагугленная реализация сортировки вставками O(n^2) . Результат - бесконечность, за 45 минут не отсортировалась даже половина массива, я остановил тест.
4. Нагугленная реализация сортировки слиянием mergesort O(n*log(n)). Результат 4.08 секунды.

Уже из этих цифр видно различия в вычислительной сложности: n^2 по сравнению с n*log(n) начинает проигрывать просто феерически. И да, такой массив - это обыденность: по объему данных это примерно две картинки в full hd.

Выигрыш метода Array.Sort у простой реализации быстрой сортировки "в лоб" заслуживает отдельного внимания, обязательно залезу в исходный код .Net Core и расскажу чем он отличается.

#csharp #диссер

Продолжаю про оптимизацию сортировки массива в диссертационном проекте.

Более-менее успешно распараллелил сортировку: использовал нечто гибридное. Массив разделяется на несколько частей, каждая сортируется параллельно, после чего сливаются во едино функцией Merge из реализации сортировки слиянием из прошлого поста (п. 4).

Результаты меня несколько огорчили. Рост про производительности бесспорно есть. Время обработки сократилось с 2.2 секунд до 1.5 с использованием двух потоков. При этом, с ростом числа потоков, скорость растет на какие-то смешные значения, а то и падает за счёт того, что приходится ждать запаздывающие потоки.

Фантастический сюрприз поджидал меня далее. Я сортирую массив объектов по одному из полей с типом double. При этом используется стандартный инструмент для сравнения пользовательских типов данных внутри метода Array.Sort - реализация интерфейса IComparer. По сути, в сортировку передается функция, с помощью которой можно сравнивать экземпляры сортируемых классов.

Я решил посмотреть, сколько будет сортироваться массив моего размера (4млн) double. 0.08 секунды, почти в 25(!) раз быстрее. Теперь думаю, как по-ловчее перевести алгоритм на такую сортировку.

#csharp

Небольшое уточнение к прошлому посту. В мои замеры прокралась ошибка, на самом деле среднее время сортировки массива из double-ов составляет 0.37 секунды.

Несмотря на это, шестикратная разница в скорости - это тоже неплохо.

Кроме того, у метода Array.Sort есть перегрузка, которая предлагает сортировать один массив относительно другого. Замерял её производительность, вынеся поле, по которому сортирую в отдельный массив. Результат - 1.1 секунды. Т.е. простой вынос поля, по которому осуществляется сортировка в отдельный массив и отказ от использования реализации IComparer там, где это не нужно, уже дает двукратный рост производительности.

Интересно, получится ли выдавить бОльший рост какими-либо другими манипуляциями?

#csharp