Быстрый язык ≠ быстрый код

Получил такой комментарий на заметку про быстрый и медленный алгоритмы:

Мне кажется, тут не совсем корректное сравнение. sorted оптимизированная и написана на С, в то время как insort — просто питоновская функция. Она гоняет питоновские структурки и при любом раскладе будет работать медленно.

Это вообще популярная точка зрения, что если что-то написано на «быстром» языке, то оно уж всяко будет быстрее, чем написанное на «медленном».

Конечно же, это не так. Алгоритмы отличаются асимптотической сложностью — в том примере было O(n logn) против O(n²). В такой ситуации O(n logn) будет всегда быстрее для достаточно большого n, даже если написать его на джаваскрипте и интерпретировать встроенной в Windows js-машиной, а O(n²) написать на самом быстром в мире C.

Другое дело, что оговорка «для достаточно большого n» может оказаться решающей. Бывает, что асимптотически более быстрый алгоритм начинает выигрывать, скажем, при n > 10 млрд — а у вас в программе всегда n < 1 млн. Именно поэтому стоит реализовать и сравнить в действии оба алгоритма, если нет 100% уверенности.

А ещё бывает, что при одинаковой асимптотической сложности один алгоритм в 5 раз быстрее другого — потому что она такие мелочи игнорирует. И тут тоже без тестирования никуда.

P.S. Модуль bisect на самом деле реализован на C. Если интересно, как выглядит «сишная» часть питона, посмотрите — это один из самых простых модулей.