Является ли big-O действительно актуальным при работе в промышленности?

В каждом интервью, в котором я принимал участие, меня опрашивали по математическому анализу сложности, включая нотацию big-O.

Насколько актуален анализ big-O для развития в промышленности? Как часто вы действительно используете его, и насколько необходимо иметь отточенное мышление для этой проблемы?

Мой вопрос: насколько актуален этот тест для развития в промышленности?

Точное понимание теории вычислительной сложности (например, большой O-нотации) необходимо для разработки масштабируемых алгоритмов, приложений и систем. Так как масштабируемость очень важна для вычислений в промышленности, большие обозначения O тоже.

Как часто вы действительно используете его, и насколько необходимо иметь отточенное мышление для этой проблемы?

Зависит от того, что вы подразумеваете под «реальным использованием». С одной стороны, я никогда не делаю формальных доказательств сложности вычислений для программного обеспечения, которое я пишу. С другой стороны, в большинстве случаев мне приходится иметь дело с приложениями, где масштабируемость является потенциальной проблемой, а проектные решения включают в себя выбор (например) соответствующих типов коллекций на основе их характеристик сложности.

(Я не знаю, возможно ли последовательно реализовать масштабируемые системы без четкого понимания теории сложности. Я склонен думать, что это не так.)

Причина этого в том, что это указывает на масштабируемость .

Процесс, который является O (n ^ 2), будет масштабироваться хуже, чем процесс, который является O (n log n), но лучше, чем процесс в O (n ^ 3) или даже O (n!).

Если вы не знаете различий и когда они применяются, вы менее подходите для выбора правильных реализаций функциональности, а также для экстраполяции производительности тестирования в производительность производства.

РЕДАКТИРОВАТЬ: сравнение 48n с n ^ 3 из http://www.codinghorror.com/blog/2007/09/everything-is-fast-for-small-n.html (который в свою очередь из программирования жемчужины)

Это зависит от того, что вы делаете.

Для веб-разработчиков (таких как я) это обычно имеет большое значение. Вы хотите, чтобы веб-приложения масштабировались. Если у вашего приложения есть узкое место, которое масштабируется с помощью O (n ^ 2), и вы думаете, что это просто замечательно, поскольку ваш сервер может обрабатывать 1000 одновременных пользователей, кажется, вам это не нужно. Дело в том, что для обработки всего в два раза больше (что вполне вероятно может случиться за ночь) вам понадобится в 4 раза больше вычислительной мощности. В идеале вы хотите, чтобы веб-приложения масштабировались в O (n), потому что оборудование дешевое при разумном постоянном соотношении пользователь / сервер.

Обычно в приложениях, где у вас есть 100000 объектов, большой O придет и съест вас. Вы чрезвычайно уязвимы для пиков. Например, в настоящее время я работаю над трехмерной игрой, которая представляет собой приложение, которое обрабатывает множество данных. Помимо рендеринга, у вас есть проверка столкновений, навигация и т. Д. Вы не можете позволить себе просто идти очевидным путем. Вам нужны эффективные алгоритмы, вам нужно много кеширования, чтобы амортизировать менее эффективные. И так далее.

Конечно, если то, что вы делаете, это что-то вроде создания мобильного приложения путем объединения GUI в конструкторе интерфейсов, соединения этого с некоторыми веб-сервисами и все, у вас никогда не возникнет проблем со сложностью. Потому что веб-сервисы, которые вы вызываете, уже позаботятся об этом.

Я никогда не применял формально правила в моей трудовой жизни.

Однако вы должны быть знакомы с этой концепцией и применять ее интуитивно понятным образом каждый раз, когда разрабатываете алгоритм.

Правило таково:

Вы должны быть достаточно знакомы с нотацией O, чтобы иметь возможность определить, для какой задачи, требуется ли ее формально рассчитать, или достаточно просто оценить ее интуитивно, или вы можете просто пропустить ее полностью. Как и многие другие основные математические понятия.

Ну, может, небольшая история просветит вас, почему она ОПРЕДЕЛЕННО необходима:

В проекте, над которым я работал, была программа, отвечающая за печать всех видов документов (этикетки, списки комплектов и т. Д.). Эта программа состояла из двух частей: одна считывала все необходимые данные из базы данных и записывала их в Файл в стиле .ini и другая часть, которая читает эти файлы и заполняет их в шаблоны. Это работало достаточно хорошо для ярлыков и небольших списков (всего с несколькими полями), но работало почти 10 минут, когда пришлось печатать «большой» список из ~ 20 страниц. Поскольку доступ к этим ini-файлам приводил к O (n²) времени доступа, n - количество полей для печати.

Если бы первоначальные программисты этой программы понимали O-нотацию, они бы никогда не сделали это так. Замена этой глупости хеш-таблицей сделала ее намного быстрее.

Производительность Big-O важна, но она в значительной степени интернализована.

Производительность Big-O сортировки и поиска не имеет значения, потому что люди обычно используют поставляемые системой, и они будут настолько хороши, насколько это возможно (учитывая, что они должны быть в целом полезны). Существуют структуры данных, которые более эффективны для разных целей, но обычно их можно выбирать на общих принципах (и, как правило, они встроены в современные языки). Есть некоторый смысл алгоритмов, которые делают или не масштабируют.

В результате формальные проблемы редко возникают на практике, но практика строится на тех же принципах.

ИМХО, многие программы по информатике заставляют многих студентов бродить там среди сорняков. Эти программы никогда не раскрывают общую картину того, что такое наука о вычислениях. Студенты вступают в индустрию, пытаясь понять, как применять полученные ими концепции, и мало понимают, как они связаны с реальным миром.

Я бы сказал, что сердце науки о вычислениях - это способность рассуждать о вычислениях. И вы изучаете различные методы и приемы для этого и применяете их к абстрактным задачам, которые являются прототипами примитивов, встречающихся во многих реальных задачах. Хитрость заключается в том, чтобы обнаружить эти прототипные примитивы в реальном мире, а затем рассуждать о таких вещах, как правильность, сложность, время и т. Д., Которые, как вы можете согласиться, являются реальными проблемами, о которых вам нужно беспокоиться. Понимание того, как ведут себя части, часто дает представление о том, как ведет себя целое. И те же самые общие методы и приемы могут также применяться ко всему, но не с той строгостью, которая присуща более мелким, хорошо абстрагированным, четко определенным частям. Но в конце концов, наука вычислений, жертвует вам возможность сделать разумный решения о том, как организовать ваши вычисления, с реальным пониманием того, как они будут вести себя в различных условиях.

Памятка себе!

Я и многие другие регулярно задаем себе этот вопрос.

Я думаю, что настоящая причина, по которой мы спрашиваем это, заключается в том, что мы стали ленивыми.

Эти знания никогда не устаревают и не устаревают. Вы не можете применять его непосредственно на повседневной основе, но вы будете использовать его подсознательно, и это окажет положительное влияние на ваши дизайнерские решения. Однажды это может сэкономить вам или другим часам и дням кодирования.

Поскольку все больше проблем заключено в сторонних библиотеках и инструментах и ​​доступно для все большего числа разработчиков, вам необходимо знать эти знания, чтобы отличаться от других и помогать решать новые проблемы.

На самом деле, нет. В принципе, единственный раз, когда я думаю об этом, - это доступ к базе данных. Я обычно смотрю на код и говорю: «Это делает n + 1 запросов, вы должны изменить его, чтобы сделать только 1 или 2»

Поскольку все мои данные считываются из базы данных и показываются пользователю, я стараюсь свести к минимуму объем данных, с которыми я работаю, до такой степени, что разница между линейным и O (n ^ 2) алгоритмом довольно велика незначителен.

Если есть проблема, мы профилируем и исправим ее позже.

Три вопроса, которые вы задали, и я думаю, что краткие ответы могут помочь более длинным аргументам, приведенным до сих пор

Насколько актуален этот тест для развития в промышленности?

Зависит от отрасли.

Где бы ни возникали проблемы со скоростью кода или пространством кода, это полностью относится к соответствующей отрасли. Часто вам нужно знать, сколько времени займет процедура или сколько памяти (вкл. / Офлайн) потребуется.

Как часто вы действительно используете его?

Зависит от отрасли.

Если производительность и масштабирование не имеют большого значения для выполняемой работы, то редко, только в случае серьезного снижения производительности. Если вы инженер по критически важной системе, вероятно, каждый день.

Насколько необходимо иметь отточенное мышление для этой проблемы?

Совершенно необходимо.

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

Я бы сказал, что это очень часто. Как правило, мы не доказываем, что что-то имеет конкретный big-O, но мы усвоили эту идею и запомнили / ознакомились с гарантиями big-O для конкретных структур данных и алгоритмов, и мы выбираем самые быстрые из них для конкретного использования. Это помогает иметь библиотеку, которая полна всех опций, например, библиотека коллекций Java или C ++ STL. Вы неявно и естественно используете big-O каждый день, когда решаете использовать java.util.HashMap( O(1)поиск) вместо java.util.TreeMap( O(lg n)поиск) и, конечно же, решаете не выполнять линейный поиск по java.util.LinkedList( O(n)поиску) для чего-то, где вам не требуется сортированный доступ.

Когда кто-то выбирает неоптимальную реализацию, а кто-то, кто знает лучше, приходит и видит свой код, это часть нашего словаря, чтобы исправить их: «Ваша реализация занимает квадратичное время, но мы можем сделать это до времени n-log-n, выполнив это вместо этого "так естественно и автоматически, как мы бы использовали английский язык для заказа пиццы.

да

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

Я работал над двумя разными системами, которые казались хорошими в ранней разработке, но поставили оборудование на колени в производственном тестировании, потому что кто-то использовал алгоритм O (n ^ 2). И в обоих случаях исправление было тривиальным изменением алгоритма O (n).

Вероятно, он используется там, где они разрабатывают API для потребления. C ++ STL - один из немногих API-интерфейсов, который имеет ограничения сложности, налагаемые на его алгоритмы. Но для каждодневного работающего программиста / старшего программиста / дизайнера / архитектора это не приходит им в голову.

Я не нашел это таким важным, кроме как обмениваться идеями, и я работаю в критических областях производительности (трассировка лучей, обработка изображений и сеток, системы частиц, физические движки и т. Д.), И мне пришлось разрабатывать множество собственных алгоритмов и структур данных. при работе в НИОКР. В этих областях часто очень эффективные структуры данных и алгоритмы могут привести к появлению совершенно новых передовых продуктов, в то время как вчерашние алгоритмы делают существующие продукты устаревшими, поэтому всегда нужно стремиться делать что-то более эффективно. Однако, как предостережение, я никогда не публиковал никаких статей по разработанным мной алгоритмам. Все они были частными. Если бы я это сделал, мне понадобилась бы помощь математика, чтобы сформулировать доказательства и так далее.

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

Конечно, если вы сравниваете квадратичную сложность с линейной, это огромная разница. Но большинство людей в моей области достаточно компетентны, чтобы избегать применения алгоритма квадратичной сложности на эпических входах. Так что масштабируемость часто подразумевается, и более значимые и интересные вопросы становятся такими: «Использовали ли вы GPGPU? SIMD? Работает ли он параллельно? Как вы представляли данные? Вы реорганизовали их для моделей доступа к кешу? Как сколько памяти это займет? Может ли он надежно справиться с этим делом? Вы откладываете определенную обработку или делаете все это за один раз? "

Даже линейный алгоритм может превзойти алгоритм линейного времени, если первый обращается к памяти по более оптимальному шаблону, например, или лучше подходит для многопоточности и / или SIMD. Иногда даже линейный алгоритм может превзойти логарифмический алгоритм по этим причинам, и, естественно, алгоритмы с линейным временем превосходят логарифмические по малым входам.

Поэтому для меня важнее то, что некоторые люди могут назвать «микрооптимизацией», такими как представления данных (макеты памяти, шаблоны доступа с разделением горячих / холодных полей и т. Д.), Многопоточность, SIMD и иногда GPGPU. В области, где каждый уже достаточно компетентен, чтобы использовать достойные и передовые алгоритмы для всего с постоянно публикуемыми новыми статьями, ваше конкурентное преимущество в победе над алгоритмическими волшебниками заключается не столько в улучшении алгоритмической сложности, сколько в более прямой вычислительная эффективность.

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

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

Еще одно преимущество, которое позволяет мне выживать в области, где доминируют люди, намного умнее меня, - это просто понимание того, как работает пользователь, поскольку я использую программное обеспечение, которое разрабатываю таким же образом. Это дает мне идеи для алгоритмов, которые действительно очень быстро соответствуют интересам пользователей. Как основной пример, большинство людей пытаются ускорить такие вещи, как обнаружение столкновений, используя пространственную индексацию. Почти пару десятилетий назад я сделал простое наблюдение за формированием карьеры для органических моделей: например, если персонаж кладет руки на лицо, структура пространственной индексации должна разделять узлы и делать дорогие обновления, если персонаж затем убрал руку с лица. Если вместо этого вы разбиваете на основе данных подключения, а не позиции вершин, вы можете получить стабильную иерархическую структуру, которая обновляется очень быстро и не нуждается в разделении или перебалансировке дерева (нужно только обновлять ограничивающие рамки в каждом кадре анимации) ... что-то вроде этого - алгоритмы, не имеющие большого математического опыта мог бы придумать, если бы они просто поняли основную концепцию, но те, которые ускользали от математиков, поскольку они не думали о вещах так близко к тому, как работают пользователи, и слишком много думали только о свойствах геометрии, а не о том, как геометрия был широко использован. Я достаточно хорошо лажу, опираясь больше на общие вычислительные и пользовательские знания, чем на алгоритмическое волшебство. Так или иначе, я действительно не нашел это настолько важным, чтобы сосредоточиться на алгоритмической сложности.

Да, сложность имеет значение в отрасли. Если вы в конечном итоге разработаете что-то, где критический путь масштабируется как N-квадрат (удвоение количества чего-либо увеличивает загрузку системы в четыре раза), вы достигнете своего узкого места масштабирования гораздо быстрее, чем если бы у вас было что-то, масштабирующееся в N.

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

Я никогда не думаю о большом О с математической точки зрения, я вообще никогда не думаю о большом О, если не спросить. Я просто вижу алгоритм в своей голове, и я могу сказать, если он плох, потому что он делает несколько циклов в памяти для каждого N, или он делит и побеждает или что-то в этом роде. При необходимости я могу перевести это в большую нотацию O за несколько секунд, но мне легче просто знать, как алгоритм / контейнер работает с памятью, чем думать о математической перспективе.

Вопросы, которые задают в интервью, есть, чтобы узнать, можете ли вы объяснить и мыслить логически . Интервьюер также пытается выяснить, можете ли вы использовать то, что знаете, для решения связанной проблемы .

Каждый, кто сделал достойное изучение программной инженерии, встретит «Big O», а также, чтобы ответить на хороший вопрос о «Big O», вы также должны иметь некоторое представление о стандартных структурах данных и алгоритмах.

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

Поэтому вопросы о «большом О» могут быть очень важны для процесса интервьюирования.

По крайней мере, каждый год в течение моего долгого времени работы программистом мне приходилось исправлять код, который был медленным из-за того, что кто-то не понимал правильную структуру данных и алгоритмы, которые нужно использовать, но вы можете решить эти проблемы, не имея детального понимания Big O. Однако люди, которые понимают Большую палатку, не избегают этих проблем в первую очередь.