Скорость на Питоне

Если речь идет про Питон, обычно можно забивать на эффективность использования ресурсов — памяти и процессорного времени. Если нужна эффективность в плане ресурсов, пишите на C или C++. Однако есть несколько оговорок.

Во-первых, считается нормой, если условная оптимальная версия программы использует во несколько раз меньше ресурсов, и это отношение является постоянным для любого размера входных данных. То есть, если надо упорядочить тысячу или миллион чисел, а "оптимальная" программа выигрывает в обоих случаях в 10 раз у обычной программы, это норма. Можно просто подождать или использовать более мощный компьютер.

Иными словами, если какая-то программа требует 100×n байт памяти, а другая 20×n байт памяти, где n — это количество чисел или длина строки на входе, это нормально. Но вот если одна программа требует 20×n, а другая — 20×n², то разница на больших объемах становится такой, что второй программе не хватит никаких разумных объемов оперативной памяти.

При этом числовой коэффициент зависит не только от самой программы, но и от языка программирования, от оборудования. А вот оставшаяся часть n или n² зависит только от алгоритма. Поэтому, когда оценивают скорость работы или используемую память, не указывают числовой коэффициент. Пишут, что программа работает O(n²) или O(n×log(n)). Обратите внимание, что у логарифма нет основания, так два логарифма с разными основаниями отличаются на постоянный коэффициент при любом значении аргумента.

Во-вторых, когда программа обрабатывает большие объемы или очень часто запускается, то может быть экономически выгодно написать ее более эффективно. Может быть, на другом языке.

В-третьих, иногда бывает так, что оптимально написанный алгоритм оказывается проще для человеческого понимания, чем неэффективно написанный.