Является ли проблемой быть программистом без знания вычислительной сложности?

30

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

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

Билли Рубина
источник
3
Уведомление модератора : пожалуйста, не используйте комментарии для расширенного обсуждения или для публикации содержательных ответов. Вы можете использовать чат для обсуждения этого вопроса; предыдущие комментарии были перемещены туда.
Жиль "ТАК - перестань быть злым"
4
Ваш титул говорит программист, но ваш вопрос говорит студент. Как правило, «программист» подразумевает «профессионального программиста» - поэтому вы спрашиваете, является ли проблемой быть профессиональным программистом без знания вычислительной сложности? Или можно ли студенту-программисту не иметь этих знаний? Это разные вопросы, даже если оказывается, что у них один и тот же ответ.
CorsiKa

Ответы:

42

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

В вашем конкретном случае ваш пример поиска связанных компонентов мог бы работать для графиков, скажем, до узлов. Однако, если вы попробуете граф с 100 000 узлов, то алгоритм вашего лектора, вероятно, справится с этим за 1 секунду, в то время как ваш алгоритм (в зависимости от степени сложности) займет 1 час, 1 день или даже 1 вечность.100100,000

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

while array not empty
    examine first element of array
    remove first element from array

Это может быть не самый красивый код, но в сложной программе что-то вроде этого может появиться без ведома программиста. Теперь, в чем проблема с этой программой?

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

while array not empty
    examine last element of array
    remove last element from array

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

В моем языке псевдокода «удаление элемента из массива» сдвигает все элементы справа от удаляемого элемента на одну позицию слева. Это делает удаление последнего элемента операцией поскольку для этого нам нужно взаимодействовать только с 1 элементом. Удаление первого элемента - это O ( n ), поскольку для удаления первого элемента нам нужно сместить все остальные n - 1 элементов на одну позицию влево.О(1)О(N)N-1

Очень базовое упражнение по сложности, чтобы доказать, что первая программа будет делать операций, в то время как вторая программа использует толькоnопераций. Если вы подключитеn=100.000,вы увидите, что одна программа значительно эффективнее другой.12N2NNзнак равно100,000

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

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

Том ван дер Занден
источник
10
"So long as you are not dealing with huge data sets you will be fine not knowing complexity"Это часто правда, но не всегда так. Например, O(n!)алгоритм не будет жизнеспособным даже для относительно небольших наборов данных. Если вы используете O(n!)алгоритм, который вы могли бы использовать, O(n^2)ваша программа будет исполняться в 36 288 раз дольше при размере данных 10 . При размере данных 20 вы просматриваете 2,4 операции квинтиллиона.
Рейраб
1
Я думаю, что пример @ reirab должен быть включен в ответ. Это более драматично и доказывает вашу точку зрения более решительно. И лично я был укушен такими алгоритмами, прежде чем я научился вычислительной сложности.
Сиюань Рен
2
Я думаю, что есть большая проблема в игре. Если вы просто не знаете, вы сами выбираете задачи, где это не нужно. Таким образом, вы можете сказать, что почти все вопросы, которые мне нужно знать, заканчиваются на X, это может быть полезно. Так что независимо от того, насколько это важно, все еще полезно знать, или это может в конечном итоге вас укусить.
joojaa
«Понимание различий между двумя программами требует некоторых базовых знаний о теории сложности» - я думаю, что для этого конкретного примера это не так. Вы можете профилировать его, наблюдать, что все время занято в «удалить элемент», знать (без понимания теории сложности), что удаление последнего элемента быстрее, чем удаление первого, внести изменения и, следовательно, ускорить программу. Преимущество понимания теории сложности заключается в том, что она позволяет свободно оценивать такие проблемы без их профилирования, поэтому вы можете «преждевременно» оптимизировать.
Стив Джессоп
... и вообще я подозреваю, что все или почти все практические примеры могут быть решены один за другим, без ссылки на теорию сложности. В этом случае, зная, что копирование большого количества данных медленнее, чем не делает, это не «теория сложности». Но, конечно, все еще полезно в программировании (и любой профессии) иметь хорошую ментальную модель принципов, которые обычно появляются, потому что вы можете анализировать, обсуждать и решать такие проблемы в принципе по принципу, а не по одному за раз специальными средствами.
Стив Джессоп
26

Это опровержение ответа Тома ван дер Зандена , в котором говорится, что это необходимо.

Дело в том, что в 50.000 раз медленнее не имеет значения (если, конечно, вы не работаете в Google).

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

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

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

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

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

claudio495h
источник
3
Если говорить более подробно, то есть случаи, когда слишком большой акцент на вычислительной сложности может сбить вас с пути. Например, могут быть ситуации, когда «лучший» алгоритм на самом деле медленнее для небольших входов. Профилировщик является основным источником правды.
Кевин Крумвиде,
2
@Kevin Krumwiede, я полностью согласен с вами, что оптимизация сортировки для тривиального набора данных является излишним. Но это также показывает, что по крайней мере понимание сложности все еще важно. Понимание - это то, что заставит вас принять решение о том, что пузырьковая сортировка подходит, а не какой-то другой, более сложный алгоритм.
Кент А.
4
Когда вы знаете, что набор данных во всех случаях мал, вы можете сойти с рук. Вы должны быть очень осторожны с избыточной сложностью в вещах, называемых внутри циклов - хотя недавно я сократил время выполнения до секунды таким образом. Я также однажды столкнулся с проблемой O (n ^ 8) (проверка данных). Много внимания было уделено 12 часам.
Лорен Печтел
7
Мне никогда не приходилось задумываться о сложности вычислений при цикле внутри цикла O (M * N), потому что операция всегда очень быстрая или M и N такие маленькие. - По иронии судьбы, аргумент, который вы приводите, показывает, что вы задумывались о сложности вычислений. Вы решили, что это не имеет отношения к тому, что вы делаете, и, возможно, это справедливо, но вы все еще знаете о существовании этой проблемы, и если она когда-либо создаст проблему, вы можете отреагировать на нее до того, как произойдут серьезные последствия для уровень пользователя.
Wrzlprmft
4
Преждевременная оптимизация - корень всего зла, но преждевременная пессимизация - корень, по крайней мере, многих раздраженных пользователей. Возможно, вам не нужно будет разрешать рекуррентное отношение, но если вы, по крайней мере, не способны определить разницу между O (1), O (N) и O (N ^ 2), особенно когда вы Вложите петли, кому-то придётся навести порядок позже. Источник: беспорядки, которые мне пришлось убирать позже. Коэффициент 50.000 настолько велик, что вам лучше знать, сможете ли вы позволить себе это позже , когда ваши вклады вырастут.
Йерун Мостерт
14

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

Независимо от того, я самоучка. Я никогда не сталкивался с обозначением O, пока не начал брать интервью несколько лет назад. Это никогда не всплывало в моей профессиональной работе за исключением интервью. Поэтому я должен был изучить основы, чтобы справиться с этим вопросом в интервью.

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

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

Удачи тебе!

Скотт Шефер
источник
2
Итак, ваш ответ "да"?
Рафаэль
6
TL; DR: "да". Тем не менее, по моему опыту, вы не будете говорить о сложности вычислений на большинстве рабочих мест после того, как вас приняли на работу. Да, знайте свои структуры данных и их производительность, но просто зная, что алгоритм - это O (n) или что-то, что не делает хороший программист. Гораздо лучше сосредоточиться на быстрой написании хорошего кода и последующей оптимизации горячих точек. Читаемость и удобство сопровождения, как правило, важнее для большинства кода, чем производительность.
Скотт Шафер,
3
Я думаю, что может случиться так, что сложность возникает в корпоративной среде, но первая реальная проблема для компаний - доставка : если она работает, она достаточно хороша, пока не будет доступного бюджета для улучшения приложения, или клиент вернется, чтобы жаловаться на плохое выступления. В ситуациях b2b для проектов adhoc это, вероятно, довольно редко. На b2c, или на высококонкурентных рынках (готовых продуктах), это, вероятно, будет появляться чаще, с прямым эффектом поднятия полосы входа для новых сотрудников.
Didierc
4
@didierc "Достаточно хорошо" - это то, что постоянно ломает вещи.
Рафаэль
1
@didierc 1) Ну, у людей с солидным опытом в CS есть (надеюсь) хорошая интуиция в отношении того, что правильно, а что нет, тогда как специальные решатели проблем могут совершать «простые» ошибки. Обеспечение того, чтобы выполнение после многократных компиляций было именно тем, что было указано, крайне нетривиально, и на самом деле нерешенная проблема. 2) Нет .
Рафаэль
9

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

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

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

Короче говоря, я думаю, что понимание сложности явно делает вас лучшим программистом.

Юхо
источник
1
Я думаю, что у вас, как правило, есть правильная идея, но «субъективный» не описывает эту проблему адекватно; «косвенное» было бы лучшим словом. Также можно написать очень медленные программы, которые не работают с большим количеством данных. Я недавно ответил на вопрос на math.se о полиномиальном представлении / хранении. Это обычно включает в себя довольно небольшое количество данных, например, ~ 1000-членные полиномы являются типичными; тем не менее, существуют огромные различия в производительности (сотни или тысячи секунд против нескольких секунд для умножения) в зависимости от реализации.
Fizz
4

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

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

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

обкрадывать
источник
3

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

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

Нубистский программист может сделать:

  • разрабатывать базы данных больших данных - ему не нужно знать, как это работает внутри, все, что он должен знать, - это правила разработки баз данных. Он знает такие вещи, как: что должно быть проиндексировано, ... где лучше делать избыточность в данных, а где нет ...
  • создавать игры - он просто должен изучить, как работает какой-то игровой движок и следовать его парадигмам, игры и компьютерная графика - довольно большие проблемы с данными. Рассмотрим 1920 * 1080 * 32 бит = около 7,9 МБ для одного кадра / кадра ... @ 60 кадров в секунду, это минимум 475 МБ / с. Учтите, что только одна ненужная копия полноэкранного изображения будет тратить около 500 МБ памяти в секунду. Но он не должен заботиться об этом, потому что он использует только двигатель!

Нубистский программист не должен делать:

  • разрабатывать очень часто используемые сложные программы независимо от размера данных, с которыми они работают, например, небольшие данные не будут оказывать заметного влияния неправильного решения во время разработки, поскольку оно будет медленнее, чем время компиляции и т. д. Итак, 0,5 Секунда для одной простой программы не так уж много с точки зрения программиста, ну, рассмотрим серверный сервер, который запускает эту программу двадцать раз в секунду. Требуется 10 ядер, чтобы выдержать эту нагрузку!
  • разрабатывать программы для встраиваемых устройств. Встроенные устройства работают с небольшими данными, но они должны быть настолько эффективными, насколько это возможно, потому что избыточные операции делают ненужным потребление энергии

Итак, программист Noobish хорошо, когда вы хотите просто использовать технологии. Поэтому, когда речь заходит о разработке новых решений, нестандартных технологий и т. Д. Тогда лучше нанимать нубийских программистов.

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

kravemir
источник
1
Этот ответ мог бы быть улучшен, если бы он использовал более нейтральный ярлык или вообще не использовал ярлык, так же как и другой ответ, в котором использовался термин «некомпетентный программист».
Moby Disk
1
Я не уверен, что вы подразумеваете под «концептуальной сложностью». Мой опыт показывает, что люди, которые недостаточно знают о деревьях или хеш-таблицах, не могут принимать разумные решения относительно того, как индексировать (части) большой базы данных.
Fizz
3

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

Есть много уровней / степеней знаний для многих вещей в области вычислительной техники (и под этим термином я подразумеваю грубый союз информатики с информационными технологиями). Сложность вычислений, безусловно, является обширной областью (Знаете ли вы, что такое OptP? Или что говорит теорема Абитебул-Виану?), А также допускает большую глубину: большинство людей со степенью CS не могут предоставить экспертные доказательства, которые идут на исследования публикации в вычислительной сложности.

N2

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

И еще один момент заключается в том, что знание вычислительной сложности не поможет автоматически оптимизировать программы; вам нужно понимать больше вещей, связанных с архитектурой, таких как локальность кэша, [иногда] конвейерная обработка, а также параллельное / многоядерное программирование; последний имеет как собственную теорию сложности, так и практические соображения; вкус последнего из статьи SOSP 2013 года "Каждая схема блокировки имеет свои пятнадцать минут славы. Ни одна из девяти схем блокировки, которые мы рассматриваем, последовательно не превосходит любую другую на всех целевых архитектурах или рабочих нагрузках. Строго говоря, стремиться к оптимальности, Таким образом, алгоритм блокировки следует выбирать на основе аппаратной платформы и ожидаемой рабочей нагрузки ».

шипение
источник
1
В конечном счете, разработка или поиск лучшего алгоритма обычно более выгодны, чем изменение языка программирования для чувствительных к производительности битов. Я согласен с вами в том, что существует тесная связь между непониманием сложности и преждевременной оптимизацией - потому что они обычно предназначаются для менее чувствительных к производительности битов для оптимизации.
Роб
1
На практике (непреднамеренно) алгоритмы Шлемеля-Пейнтера встречаются гораздо чаще, чем O (n ^ 2) сортировка.
Питер Мортенсен
-1

Если вы не знаете, большой-O, вы должны научиться этому. Это не сложно, и это действительно полезно. Начните с поиска и сортировки.

Я заметил, что многие ответы и комментарии рекомендуют профилирование , и они почти всегда означают использование инструмента профилирования .

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

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

Но они не могут скрыться от этой техники.

Майк Данлавей
источник
Вы утверждаете, что «Big-Oh» - это полезно, но затем вы защищаете другой подход. Кроме того, я не понимаю, как изучение "Big-Oh" (математика) может "начинаться с поиска и сортировки" (алгоритмические проблемы).
Рафаэль
@Raphael: я не сторонник другого подхода - он ортогональн. Big-O - это базовые знания для понимания алгоритмов, тогда как поиск проблем с производительностью в неигровом программном обеспечении - это то, что вы делаете после написания и запуска кода, а не до. (Иногда ученые этого не знают, поэтому они продолжают преподавать gprof, принося больше вреда, чем пользы.) При этом вы можете или не можете обнаружить, что проблема заключается в использовании алгоритма O (n * n), поэтому вам следует быть в состоянии признать это. (А big-O - это математически определенное свойство алгоритмов, а не другой предмет.)
Майк Данлавей
«А big-O - это математически определенное свойство алгоритмов, а не другой предмет». - это неправильно и опасно так. «Big-Oh» определяет классы функций ; По сути, это никак не связано с алгоритмами.
Рафаэль