Big O notation и практика

Оценка сложности алгоритмов — сложная штука. В быту разработки широко используется базовый вариант 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) на салфетке нарисовать. Всяко быстрее, чем матчасть до винтика.

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.