Эшу быдлокодит

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

Тестовый массив - 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 #диссер

Wikipedia

Вычислительная сложность

мера ресурсов, требуемых для выполнения алгоритма

www.tgoop.com/eshu_coding/146

200 viewsEshu Marabo, edited  Dec 24, 2020 at 09:44

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

Тестовый массив - 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 #диссер

BY Эшу быдлокодит