Проекты

Подбор оптимального значения minrun

Работа победителя открытой городской научно-практической конференции «Курчатовский проект – от знаний к практике, от практики к результату» в секции «Метод»

Направление работы: Программирование
Авторы работы: ГБОУ Школа имени Маршала В.И. Чуйкова
Предметы: Информатика
Классы: 9 класс
Мероприятия: Открытая городская научно-практическая конференция «Курчатовский проект – от знаний к практике, от практики к результату» 2021 года

Актуальность

Теоретические оценки времени работы различных сортировок основаны на предположениях о распределении сортируемых перестановок, которые не всегда выполняются на реальных данных. На практике массивы случайны, но они случайны неравномерно. Если распределение реальных сортируемых данных известно, сортировку можно ускорить. Тогда можно предложить такую задачу: пользователь передаёт программе набор данных из того же распределения, что и сортируемые. Требуется отсортировать новый набор быстрее стандартной сортировки.

Цель

Подбор оптимального значения minrun.

Задачи

  1. Изучить способы решения данной задачи.
  2. Предложить алгоритм решения задачи.
  3. Проанализировать эффективность полученного алгоритма.
  4. Описание

Описание

Было решено использовать алгоритм сортировки Timsort, так как в нём есть параметры, которые можно подобрать, основываясь на паттерне массива.

Принцип работы Timsort:

  1. Разбивает массив на подмассивы размера minrun.
  2. Сортирует каждый из массивов по отдельности сортировкой вставками.
  3. Соединяет отсортированные массивы.

Minrun – важный параметр Timsort

В стандартном алгоритме Timsort minrun зависит только от размера подаваемого массива.

Например, мы хотим отсортировать массив из 13 элементов:

1 2 3 4 5 6 1 2 3 4 5 6 1

При minrun = 6 - Timsort-у потребуется 6 * 2 + 1 = 13 действий

При minrun = 9 - Timsort-у потребуется 12 + 18 = 30 действий

Разница в три раза. Получается, что minrun может зависеть не только от размера массива, но и от его паттерна.

Результаты работы/выводы

На графиках приведены длительности сортировки данных с kaggle COVID-19 Open Research Dataset Challenge на разных по сложности моделях.

Генерируемые minrun-ы на массивах до 3 * 10^5 в среднем работают на 0.003% медленнее, чем стандартная сортировка в Python, но на массивах от 3 * 10^5 до 15 * 10^6 сортировка с нестандартными minrun работает в среднем на 0.02% быстрее.

Мнение автора

«В будущем я планирую реализовать алгоритм, который позволит ускорить сортировку пользовательских массивов при наличии заранее известных выборок данных, оптимизировать и улучшать алгоритм генерации нейросетей, попробовать алгоритм на распределениях, отличных от равномерных»