Comments 5
А что показывают синие линии - доверительный интервал (разброс измерений)? Обычно эту область закрашивают полупрозрачным цветом, и границы её при этом делают не такими выраженными, это всё делается элементарно через matplotlib. И для сравнения двух алгоритмов графики рисуют либо на одной картинке, либо на двух соседних, со связанной осью. А когда графики представлены на двух разных картинках, сравнивать их приходится в уме, “вручную” сопоставляя значения на осях, что не есть хорошо. Графики же рисуют для удобства восприятия информации, а не просто так для красоты.
Два замечания по Дополнению (спасибо за него, далеко не все авторы работают с комментариями):
Освойте Numpy, там ничего особо сложного на базовом уровне, зато будете генерировать матрицы случайных чисел гораздо проще, быстрее и понятнее
Вся нужная для понимания информация должна быть на графике. Чем отличаются последние два графика должно быть понятно из самих графиков, а не только из сопровождающего текста. Вы можете сделать заголовок графика более информативным, например. Если он (заголовок) будет слишком большой с дефолтными настройками - всегда можно уменьшить шрифт, перенести часть надписи на следующую строку и т.д. Это всё легко делается. В идеале график должен быть самодостаточным для полного понимания, какую информацию он несёт.
Автор: Шуравин Александр, к. т. н., доцент, в IT более 20 лет.
Тут автор чванится своими регалиями. Фи. В интернете так не принято. Как показывает практика, уровень материала с такими подписями часто гораздо ниже чувства собственного величия автора.
Уровень сложности: Средний
Ну как же так, аж целый к.т.н. и всего-то средний материал? Что же вы так по-скромничали?
Ладно, перестаю сарказмировать. Ниже замечания по делу:
Для Senior-разработчика эти эксперименты — не просто упражнения.
Сеньёр-разработчику вся эта статья очевидна, как будто вы тут в столбик и на счетах считаете 11+31. И, внезапно, получаете 42. Но он это число еще читая, что вы собираетесь делать, в уме получает.
Это достаточно тривиальные алгоритмы, чтобы чисто логически вывести точное количество всех операций на отсортированном массиве а также матожидание и дисперсию для случайных данных. И никаких тестов и замеров не надо, чтобы убедиться, что в одном случае будет O(n), а в другом O(n^2).
> Неожиданный результат: вопреки теории, Selection Sort оказался быстрее Insertion Sort на случайных данных во всех замерах (примерно на 30–40%).
Почему вопреки? Оба дают асимптотику O(n^2) на случайных данных. Далее вопрос остается о константе. Константа зависит от аппаратной реализации и специфики языка. Ниже вы пишите:
Это объясняется тем, что Insertion Sort выполняет значительно больше операций записи в память (~n²/4 против ~n у Selection Sort)
Вы тут ошиблиcь. Selection Sort делает ~3n^2/4 операций записи: там записывается переменная min_idx, а так же j. А insertion Sort выполняет ~n^2/2 операций записи: переменная j и массив.
Так вот, Insertion Sort выполняет меньше операций и записи и сравнения, чем Selection Sort. Но работает медленнее, потому что ее работа не дружественна работе современных процессоров. В частности - к кэшу. В Selection Sort запись идет в локальную переменную и чтение неизменяемого (внутри вложенного цикла) массива, да еще и чтение идет подряд. Данные в массиве оказываются в кэше и чтение происходит легко и быстро. В Insertion Sort идет переписывание данных из массива в него же задом наперед, что вытесняет данные из кэша, даже если они там оказались. Поэтому там очень много обращений к памяти, что гораздо медленнее чтения из кэша.
Удивительно что вы за 20 лет в IT этого не заметили.
Вот это - как раз то, что Senior-разработчик должен иметь в голове.
Асимптотика на практике: Сравнение алгоритма сортировки вставками и выбором