Оценка сложности алгоритмов — сложная штука. В быту разработки широко используется базовый вариант Big O notation — подсчёт количества элементарных операций с сокращением констант. Если на пальцевом примере, то сложность функции перебора списка от первого элемента до последнего равна O(n), где n — количество элементов списка.
Фигня в том, что при всех вариантах комплексной оценки, теорий и практик разработчики тяготеют к вышеописанному простейшему, оставляя за кадром нюансы. А оно местами здорово расходится с современной практикой.
У нас тут интерпретаторы и виртуальные машины вовсю нынче. Если посмотреть на TIOBE, совокупно Java (21.1%), C# (4.4%), Python (4.2%), PHP (2.7%), Perl (2.2%), JavaScript (2.2%) и Ruby (2%) взяли атакой холмик в почти 39%.
У C (15.6%) и C++ (6.9%), традиционно языках алгоритмически вылизанных решений, между тем, сумма в 22.5%.
И если с C/C++ (как и с [M]MIX, хехе) почти всё понятно (особенно в C), то остальное… Когда Вася Пупкин говорит, что его алгоритм укладывается в O(n), что это значит в виртуальной машинке? Знает ли Пупкин, какие элементарные операции (элементарные, ха) под капотом шевелятся сотнями при вызове чего-нибудь, что в документации имеет average O(1) и worst O(n)? Точно ли он понимает, укладывается его динамика в average или целиком влетит в worst? Более того, я сталкивался с чуваками, искренне считающими, что раз O(1) алгоритма X и O(1) алгоритма Y равны, то равны и их пространственные (память) и временные (процессор) сложности. Ну вот именно так, да. Хоть убейся.
Нет, ну иногда равны, конечно. Если у нас равные наборы инструкций процессора получились. Там 10 вызовов add и там 10 вызовов add. Давно вы считали сложность с такой детализацией, а? На asm’очитеров закроем глаза.
Простой пример из Python 2.7. Есть d = {‘1’: ‘a’} и l = [‘a’]. Для average case у dict и у list get item = O(1). Мы можем игнорировать worst, т.к. всего по одному элементу — идеальные условия. А теперь вопрос: насколько xd = d[‘1’] быстрее / медленнее xl = l[0]? Глупый вопрос? Ненужный?
Вы пишете на Python нагруженный сервис (не дикая идея, к слову; Instagram всем известен). Stack Overflow, например. 12 ноября 2013 года за 24 часа ваш сервис принял 148,084,883 HTTP requests. Мало? 9 февраля 2016 года за 24 часа 209,420,973 HTTP requests (2400 rps). Посчитаем для удобства это число планкой, после которой запрос не принимается (иные и под 100 rps лягут, будем честны).
В вашем бекенде сотни, если не тысячи использований dict, list и прочего. Достаточно одного (!) неправильного одноэлементного dict / list, чтобы вы при указанной нагрузке недоприняли ~5000 запросов в сутки. Сто таких ошибок равны 500,000 запросам. Это ~2.4% от планки. Привет.
Ещё? Пожалуйста: желающие могут посмотреть на пример реализации LRU в Python на базе OrderedDict. Он там второй. Обратите внимание на контекст: ищем простой и быстрый алгоритм. Нашли, всё клёво. Только автор прострелил себе ногу, используя KeyError вместо if key not in dict — код медленнее на ~30%.
И ведь примеры выше — они очень простые, да и то в них косячат постоянно. Спрогнозировать практическую сложность решения разработчику средней руки нынче сложно и долго. Вы дёргаете метод API. Метод API дёргает пять методов Django и десять функций Python. Методы Django дёргают… а что они дёргают, кстати? А что дёргает то, что они дёргают? Сколько там памяти туда-сюда гоняется? Сколько кода уйдёт в native code, а сколько интерпретатор прокрутит? Сколько там косячного кода? Сколько попаданий в worst case?
Проще, конечно, ещё кластер машинок поставить. Или ещё один гениальный O(1) на салфетке нарисовать. Всяко быстрее, чем матчасть до винтика.
