Используете ли вы оценку сложности Big-O в «реальном мире»?

Question

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

Мне было интересно, действительно ли люди обсуждают "Big-O" своего кода в реальном слове?

Answer 1

Это не столько использование, сколько понимание того, что вы понимаете.

Есть программисты, которые не осознают последствия использования алгоритма сортировки O (N ^ 2).

Я сомневаюсь, что многие, кроме тех, кто работает в академических кругах, будут использовать анализ сложности Big-O в повседневной жизни.

Answer 2

Нет ненужных n-квадратов

По моему опыту, вы не много обсуждаете это, потому что это не нуждается в обсуждении. На практике, по моему опыту, все, что когда-либо происходит, это то, что вы обнаруживаете, что что-то медленно, и видите, что это O (n ^ 2), хотя на самом деле это может быть O (n log n) или O (n), а затем вы идете и Измени это. Там нет обсуждения, кроме "это п-квадрат, иди исправить это".

Так что, по моему опыту, вы используете его довольно часто, но только в самом простом смысле «уменьшить порядок многочлена», а не в каком-то тщательно настроенном анализе «да», но если мы переключимся на этот сумасшедший Алгоритм, мы увеличим с logN до обратной функции Аккермана "или что-то в этом роде. Все, что меньше полинома, и теория выходит за рамки, и вы переключаетесь на профилирование (например, даже для выбора между O (n) и O (n log n), измерения реальных данных).

Answer 3

Обозначение Big-O довольно теоретическое, в то время как на практике вас больше интересуют фактические результаты профилирования, которые дают вам четкое представление о том, какова ваша производительность.

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

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

Answer 4

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

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

Другой типичный пример - запросы в коде (плохо!). Люди ищут таблицу, затем выполняют запрос для каждой строки ... это поднимает порядок до N ^ 2. Обычно вы можете изменить код для правильного использования SQL и получать порядки N или NlogN.

Итак, по моему опыту, профилирование полезно ТОЛЬКО ПОСЛЕ того, как используется правильный класс алгоритмов. Я использую профилирование, чтобы уловить плохое поведение, например, понять, почему приложение с «небольшим числом» не работает.

Answer 5

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

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

.

Answer 6

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

Я никогда не рассчитывал Big-O алгоритма вне академических кругов. Если у меня есть два способа решения определенной проблемы, если мое внутреннее чувство говорит, что один из них будет иметь больший O-уровень, чем другой, я, вероятно, инстинктивно выберу меньший без дальнейшего анализа.

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

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

Answer 7

Да, я использую это. И нет, это не часто «обсуждается», так же как мы не часто обсуждаем, является ли «orderCount» или «xyz» лучшим именем переменной.

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

Обычно я думаю, что мне нужно выполнить много операций со списком. Я делаю какие-то ненужные вещи O(n^2) сложности, которые могли бы быть сделаны за линейное время? Сколько проходов я делаю по списку? Это не то, что вам нужно для формального анализа, но без знания нотации big-O сделать это намного сложнее.

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

Люди часто отвергают нотацию big-O как «теоретическую», «бесполезную» или «менее важную, чем профилирование». Что просто указывает на то, что они не понимают, что такое сложность big-O для . Это решает другую проблему, чем профилировщик. Оба необходимы при написании программного обеспечения с хорошей производительностью. Но в конечном итоге профилирование - это реактивный инструмент. Он говорит вам, где ваша проблема, как только проблема существует .

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

Answer 8

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

Answer 9

Нет. Я не использую сложность Big-O в ситуациях «реального мира».

Мое мнение по этому вопросу таково (возможно, неправильно .., но это только мой взгляд).

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

Если вы знаете этот материал Big-O и умеете правильно его использовать, хорошо, хорошо.

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

Если вы тоже не знаете, это плохо.

Answer 10

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

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