Комментарии 34
Тут всё зависит от сценария использования, величин n и m. При больших m можно пойти ещё дальше и вместо сортировки вставками использовать оптимизированную структуру, например, кучу.
P.S. А преждевременная оптимизация — зло. Ведь куда проще написать (C#):
var result = array.OrderBy(...).Take(...).ToArray();чем придумывать велосипед, который ещё надо реализовывать и тестировать.
Это я сагрился на "умельцы" и "алгоритмическое варварство".
«Ведь куда проще написать» — конечно. Но что бы вы делали без C#? Вызвать библиотечную функцию — это одно, уметь самому реализвать ее функциональность — другое.
эта задача решается классическим алгоритмом с линейной сложностью, реализованным например в C++ STL. Получение его из быстрой сортировки — отличная поучительная задача по теме. Вместо этого вы устраиваете какие-то "вычислительные эксперименты" с наивным алгоритмом квадратичной сложности.
Ну что тут можно сказать. Сочувствую вашим учащимся, представляю их шок, когда они столкнутся с задачами с какого-нибудь отбора к всеросу.
Если вы занимаетесь написанием высокопроизводительного кода на Python или даже Java, то вы явно делаете что-то не так.
Обратите внимание на время выполнения алгоритмов на приведённых вами графиках. Реализация на Python на 3 порядка медленнее реализации на Java. Ну и какой тогда в ней смысл?
Вот только у питона не 120, а 120000.
А по оптимизированной реализации ещё хуже: 60000 против 50. Оно и понятно: питон — скриптовый язык.
«А по оптимизированной реализации ещё хуже: 60000 против 50» — какая это оптимизированная версия? Вы о чем?
Так у вас на графике для Python почему-то числа шестизначные. А ещё в коде для питона итерации идут до 500000, а в java — до 5000000.
Я прогнал тесты на своей системе. Получилось:
Python 3.9.1: 500000 0.07408 0.02520
Java (OpenJDK 14.0.2): 500000 0.02453 0.00598
Да, разница не на три порядка (видимо, запятая на графике — десятичная запятая, а не разделитель порядков). Но все равно: Java в несколько раз быстрее Python. А ваши графики говорят об обратном — так быть не может.
Про линейную сложность выборки m элементов из массива длины n вы загнули.
https://en.cppreference.com/w/cpp/algorithm/partial_sort
Approximately (last-first)log(middle-first) applications of cmp.
Про сам алгоритм можно прочитать например здесь
Классический – это какой? Сложить всё в кучу и выбрать m элементов из неё? O(n+mlog(n)), но требует памяти.
Или прогнать всё через кучу на m элементов? O(nlog(m)).
Upd: а, вы про поиск m-го элемента? Да, и в самом деле, его можно переделать.
В большинстве случаев задачу и стоит решать сортировкой. Все правильно ваши студенты делают. Да, есть небольшой перерасход ресурсов, но код выходит в большинстве случаев менее бажным. А если искать самое оптимальное решение, то стоит разобрать целую кучу граничных случаев, напрмер, когда надо найти число максимумов большее или сравнимое в с размером заданного массива. И потратить кучу времени на покрытие этого кода тестами.
Игры в ассимптотическую сложность далеко не всегда имеют смысл на практике. Более того любители ассимптотической сложности часто забывают, что ассимптотический анализ верен только для "достаточно больших значений". Ну, просто как простейший пример — hash map контейнер для 2-5 элементов в нем в подавляющем большинстве случаев окажется медленнее, чем тупейший линейный список. Вот и вся ассимптотика....
В частности, предлагается алгоритм, похожий на Quicksort, но существенно упрощенный, с асимптотической сложностью O(n), где n — размер массива.
Поиск m максимальных элементов — это ещё не самый трудный вариант данной задачи. Что если в массиве из 10000 элементов надо найти такой, который находится на 5000м месте по величине? Это, между прочим, задача поиска медианы, часто встречается на практике.
И если у разработчика нет специализированного алгоритма выбора элемента с заданным рангом — то быстрее всего приемлемое решение можно реализовать именно через сортировку.
Этот процесс имеет вычислительную сложность O(nm)
А разве я писал про «сложности»
Вы не видите разницы между O(nm) и O(n log m)?
Полная сортировка — n log n. Вставка в упорядоченный массив — log m. M максимумов — N log M
Ну очевидно, что при очень малых М — линейная вставка быстрее. И что? Это тема для статьи?
Вариант 1. Для хранения найденных значений используем не упорядоченный массив длины m, а пирамиду (heap), упорядоченную по возрастанию — получаем вычислительную сложность O(n * log(m))
Вариант 2. Преобразуем исходный массив в пирамиду O(n), упорядоченную по убыванию, и выбираем из пирамиды m максимальных значений O(m * log(n)) — получаем вычислительную сложность O(n + m * log(n))
Задача о m максимумах