Применяли ли вы теорию вычислительной сложности в реальной жизни?

Question

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

Я могу ошибаться, но если вы уже пошли по этому пути, не могли бы вы привести пример того, как теория сложности помогла вам в вашей работе? Тонны благодарности.

Answer 1

O (1): простой код без петель. Просто течет. Поисковые запросы в справочной таблице тоже O (1).

O (log (n)): эффективно оптимизированные алгоритмы. Пример: алгоритмы двоичного дерева и бинарный поиск. Обычно не болит. Вам повезло, если у вас есть такой алгоритм под рукой.

O (n): один цикл данных. Больно за очень большой п.

O (n * log (n)): алгоритм, который выполняет стратегию «разделяй и властвуй». Больно за большой н. Типичный пример: сортировка слиянием

O (n * n): некоторый вложенный цикл. Больно даже при маленьком п. Общее с наивными матричными вычислениями. Вы хотите избежать такого алгоритма, если можете.

O (n ^ x для x> 2): злая конструкция с несколькими вложенными циклами. Больно для очень маленьких п.

O (x ^ n, n! И хуже): причудливые (и часто рекурсивные) алгоритмы, которые вы не хотите использовать в производственном коде, за исключением очень контролируемых случаев, для очень маленьких n и, если действительно нет лучшей альтернативы , Время вычислений может взорваться при n = n + 1.

Перемещение вашего алгоритма из класса более высокой сложности может заставить ваш алгоритм работать. Подумайте о преобразовании Фурье, которое имеет алгоритм O (n * n), который был непригоден для аппаратных средств 1960-х, за исключением редких случаев. Затем Кули и Тьюки сделали некоторые умные сокращения сложности, повторно используя уже рассчитанные значения. Это привело к широкому внедрению БПФ в обработке сигналов. И в конце концов, именно поэтому Стив Джобс разбогател на iPod.

Простой пример: программисты наивного C пишут такой цикл:

for (int cnt=0; cnt < strlen(s) ; cnt++) {
  /* some code */
}

Это алгоритм O (n * n) из-за реализации strlen (). Вложенность циклов приводит к умножению сложностей внутри Big-O. O (n) внутри O (n) дает O (n * n). O (n ^ 3) внутри O (n) дает O (n ^ 4). В этом примере предварительный расчет длины строки немедленно превратит цикл в O (n). Джоэл также написал об этом.

Но класс сложности - это еще не все. Вы должны следить за размером п. Переработка алгоритма O (n * log (n)) в O (n) не поможет, если количество (теперь линейных) инструкций значительно возрастет из-за переделки. И если n все равно мало, оптимизация тоже не даст большого эффекта.

Answer 2

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

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

SELECT User.*, COUNT(Order.*) OrderCount FROM User Join Order ON User.UserId = Order.UserId

Если бы вы изучали сложность, то вы бы поняли, если бы кто-то сказал, что это было O (n ^ 2) для определенной СУБД. Без теории сложности, человек должен был бы объяснить сканы таблицы и тому подобное. Если мы добавим индекс в таблицу заказов

CREATE INDEX ORDER_USERID ON Order(UserId)

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

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

Answer 3

Для большинства типов программных работ теоретическая часть и доказательства могут быть бесполезны сами по себе, но они пытаются дать вам интуитивную возможность сразу сказать: «этот алгоритм - O (n ^ 2) мы не можем запустить его на этих миллионах точек данных ". Даже при самой элементарной обработке больших объемов данных вы столкнетесь с этим.

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

Answer 4

Компьютеры не умны, они будут делать все, что вы им скажете. Компиляторы могут немного оптимизировать код для вас, но они не могут оптимизировать алгоритмы. Человеческий мозг работает по-разному, и поэтому вам нужно понять Большой О. Рассмотрим расчет чисел Фибоначчи. Мы все знаем F (n) = F (n-1) + F (n-2), и, начиная с 1,1, вы можете легко вычислить следующие числа без особых усилий в линейном времени. Но если вы скажете компьютеру вычислить его по этой формуле (рекурсивно), она не будет линейной (по крайней мере, в императивных языках). Почему-то наш мозг оптимизировал алгоритм, но компилятор не может этого сделать. Таким образом, вы должны работать по алгоритму , чтобы сделать его лучше.

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

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

Answer 5

Да, я часто использую нотацию Big-O, точнее, я использую мыслительные процессы, лежащие в основе этого, а не саму нотацию. Во многом потому, что в организации (ах) так мало разработчиков, я часто это понимаю. Я не хочу быть неуважительным к этим людям, но, по моему опыту, знание этого материала является одной из тех вещей, которые «сортируют мужчин из мальчиков».

Интересно, это один из тех вопросов, на которые можно получить только "да" ответы? Меня поражает, что набор людей, понимающих вычислительную сложность, примерно эквивалентен множеству людей, которые считают это важным. Таким образом, любой, кто может ответить «нет», возможно, не понимает вопрос и, следовательно, перейдет к следующему вопросу, а не сделает паузу, чтобы ответить. Просто мысль; -)

Answer 6

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

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

Answer 7

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

Answer 8

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

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

Для получения дополнительной информации об общих алгоритмах и их сложностях я нашел Седжвикса работа и информативным и доступным. Для пространственных алгоритмов превосходна книга O'Rourkes по вычислительной геометрии.

Answer 9

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

Однако я должен сказать, что понимание вычислительной сложности чрезвычайно важно в области игр! Да, вы слышали, что «бесполезные» вещи - это то, на чем основано игровое программирование.

Могу поспорить, что очень мало профессионалов, вероятно, заботятся о Big-O так же, как программисты игр.

Answer 10

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

Примеры:

• Приложение Карт ... как Google Карты - как бы вы обрабатывали данные дорожной линии по всему миру и рисовали их? и вам нужно быстро их нарисовать!
• Приложение для логистики ... думаю, что путешествующий продавец на стероидах
• Интеллектуальный анализ данных ... всем крупным предприятиям нужен один, как бы вы добыли базу данных, содержащую 100 таблиц и более 10 миллионов строк, и получили бы полезные результаты до того, как тенденции устареют?

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

Поверьте, что такое простое, как уменьшение коэффициента, скажем, от T (3n) до T (2n), может привести к ОГРОМНЫМ различиям, когда "n" измеряется в днях, если не месяцах.