Вы применяли вычислительную теорию сложности в реальной жизни?
, если вы просто хотите избежать недостатков Java-кодирования в JSP, вы можете сделать это даже с помощью скриптов. Просто следуйте некоторой дисциплине, чтобы иметь минимальную Java в JSP и почти нет вычислений и логики на странице JSP.
<%@ page contentType="text/html;charset=UTF-8" language="java" %>
<%//instantiate a JSP controller
MyController clr = new MyController(request, response);
//process action if any
clr.process(request);
//process page forwaring if necessary
//do all variable assignment here
String showMe = clr.getShowMe();%>
<html>
<head>
</head>
<body>
<form name="frm1">
<p><%= showMe %>
<p><% for(String str : clr.listOfStrings()) { %>
<p><%= str %><% } %>
// and so on
</form>
</body>
</html>
14 ответов
O (1): Простой код без циклов. Просто потоки через. Поиски в таблице поиска являются O (1), также.
O (журнал (n)): эффективно оптимизированные алгоритмы. Пример: алгоритмы двоичного дерева и двоичный поиск. Обычно не причиняет боль. Вы удачливы, если у Вас есть такой алгоритм под рукой.
O (n): единственный цикл по данным. Вред для очень большого n.
O (n*log (n)): алгоритм, который делает своего рода деление и завоевывать стратегию. Вред для большого n. Типичный пример: сортировка слиянием
O (n*n): какой-то вложенный цикл. Вред даже с маленьким n. Распространенный с наивными матричными вычислениями. Вы хотите избежать этого вида алгоритма, если Вы можете.
O (n^x для x> 2): злая конструкция с несколькими вложенными циклами. Вред для очень маленького n.
O (x^n, n! и хуже): причудливый (и часто рекурсивный) алгоритмы, которые Вы не хотите иметь в производственном коде кроме очень управляемых случаев для очень маленького n и если действительно нет никакой лучшей альтернативы. Время вычисления может взорваться с n=n+1.
Спущение Вашего алгоритма от более высокого класса сложности может заставить Ваш алгоритм полететь. Думайте о Fourier преобразовании, которое имеет O (n*n) алгоритм, который был неприменим с аппаратными средствами 1960-х кроме редких случаев. Тогда Cooley и Tukey уже сделали некоторые умные сокращения сложности путем многократного использования вычисленных значений. Ведомый к широко распространенному введению FFT в обработку сигналов. И в конце это также, почему Steve Jobs нажил состояние с iPod.
Простой пример: Наивные программисты C пишут этот вид цикла:
for (int cnt=0; cnt < strlen(s) ; cnt++) {
/* some code */
}
Это - O (n*n) алгоритм из-за реализации strlen (). Вложенные циклы приводят к умножению сложностей в большом-O. O (n) в O (n) дает O (n*n). O (n^3) в O (n) дает O (n^4). В примере, предварительно вычисляя длину строки сразу превратит цикл в O (n). Joel также записал об этом.
все же класс сложности не все. Необходимо следить за размером n. При переделке O (n*log (n)) алгоритм к O (n) не поможет, если количество (теперь линейный) инструкции вырастет в широком масштабе из-за переделки. И если n будет маленьким так или иначе, оптимизация не даст много удара, также.
В то время как это верно, что можно стать действительно далеким в разработке программного обеспечения без малейшего понимания алгоритмической сложности. Я нахожу, что использую свое знание сложности все время; хотя, в этой точке это часто, не понимая его. Двумя вещами, которые приобретение знаний о сложности дает Вам как разработчика программного обеспечения, является способ сравнить неподобные алгоритмы, которые делают то же самое (сортирующий алгоритмы, классический пример, но большинство людей на самом деле не пишет свои собственные виды). Более полезной вещью, которую это дает Вам, является способ быстро описать алгоритм.
, Например, рассмотрите SQL. SQL используется каждый день очень большим количеством программистов. Если необходимо было видеть следующий запрос, понимание запроса очень отличается при изучении сложности.
SELECT User.*, COUNT(Order.*) OrderCount FROM User Join Order ON User.UserId = Order.UserId
при изучении сложности, тогда Вы поняли бы, сказал ли кто-то, что это был O (n^2) для определенного DBMS. Без теории сложности человек должен был бы объяснить о сканированиях таблицы и таком. Если мы добавляем индекс к таблице
CREATE INDEX ORDER_USERID ON Order(UserId)
Order Тогда, вышеупомянутый запрос мог бы быть O (n, регистрируют n), который имел бы огромное значение для большого DB, но для маленького, это - ничто вообще.
можно было бы утверждать, что теория сложности не нужна, чтобы понять, как работают базы данных, и они были бы корректны, но теория сложности дает язык для размышления об и разговора об алгоритмах, работающих над данными.
Поскольку большинство типов программирования работают часть теория, и доказательства не могут быть полезными в себе, но что они делают, попытка дать Вам интуицию способности сразу сказать, что "этот алгоритм является O (n^2), таким образом, мы не можем выполнить его на этом одном миллионе точек данных". Даже в самой элементарной обработке больших объемов данных Вы будете сталкиваться с этим.
Взгляды быстро теория сложности была важна для меня в обработке бизнес-данных, GIS, программирующая графика и понимание алгоритмов в целом. Это - один из самых полезных уроков, которые можно получить от исследований CS по сравнению с тем, что Вы обычно были бы самостоятельное обучение иначе.
Компьютеры не умны, они сделают то, что Вы даете им команду делать. Компиляторы могут оптимизировать, кодируют немного для Вас, но они не могут оптимизировать алгоритмы. Человеческий мозг работает по-другому, и именно поэтому необходимо понять Большой O. Рассмотрите вычисление Чисел Фибоначчи. Все мы знаем F (n) = F (n-1) + F (n-2), и запускающийся с 1,1 можно легко вычислить следующие числа без особых усилий в линейное время. Но если бы Вы говорите компьютеру вычислять его с той формулой (рекурсивно), это не было бы линейно (по крайней мере, на императивных языках). Так или иначе наш мозг оптимизировал алгоритм, но компилятор не может сделать этого. Так, Вы имеете к работа на алгоритм для создания его лучше.
И затем, Вам нужно обучение, для определения мозговой оптимизации, которая выглядит настолько очевидной, для наблюдения, когда код мог бы быть неэффективным, для знания шаблонов для плохих и хороших алгоритмов (с точки зрения вычислительной сложности) и так далее. В основном те курсы служат нескольким вещам:
- понимают executional шаблоны и структуры данных и какой эффект они имеют на время, которое должна закончить Ваша программа;
- тренируют Ваши мозги для определения потенциальных проблем в алгоритме, когда это могло быть неэффективно на больших наборах данных. Или поймите результаты профилирования;
- изучают известные способы улучшить алгоритмы путем сокращения их вычислительной сложности;
- готовятся для передачи интервью в классной компании:)
Это чрезвычайно важно. Если Вы не поймете, как оценить и выяснить, сколько времени Ваши алгоритмы возьмут для выполнения, то Вы закончите тем, что писали некоторый довольно медленный код. Я думаю о compuational сложности все время при записи алгоритмов. Это - что-то, что должно всегда быть на Вашем уме при программировании.
Это особенно верно во многих случаях, потому что, в то время как Ваше приложение может хорошо работать на Вашем настольном компьютере с маленьким набором данных тестирования, важно понять, как быстро Ваше приложение ответит, как только Вы идете живые с ним, и существуют сотни тысяч людей, использующих его.
Да, я часто использую Нотацию "большого О", или скорее я использую мыслительные процессы позади нее, не саму нотацию. В основном, потому что так мало разработчиков в организации (организациях), которую я часто посещаю, понимает его. Я не означаю быть непочтительным к тем людям, но по моему опыту, знание этого материала является одной из тех вещей что "виды мужчины от мальчиков".
интересно, является ли это одним из тех вопросов, которые могут только получить "да" ответы? Это ударяет меня, что группа людей, которые понимают вычислительную сложность, примерно эквивалентна группе людей, которые думают, что это важно. Так, любой, который мог бы ответить не, возможно, не понимает вопроса и поэтому пропустил бы по следующему вопросу, а не паузе для ответа. Просто мысль;-)
Существуют моменты времени при направлении с проблемами, которые требуют взглядов о них. Существует много проблем реального мира, которые требуют управления большим набором данных...
Примеры:
- приложение Карт... как Google Maps - как Вы обработали бы дорожные данные строки во всем мире и потянули бы их? и необходимо потянуть их быстро!
- приложение Логистики... думает, перемещаясь человек продаж на стероидах
- Анализ данных..., все крупные предприятия требуют один, как Вы произвели бы интеллектуальный анализ баз данных, содержащий 100 таблиц и 10 м + строки, и придумали бы полезные результаты, прежде чем тенденции станут устаревшими?
Взятие курса в вычислительной сложности поможет Вам в анализе и выборе/создании алгоритмов, которые эффективны для таких сценариев.
Верят мне, что-то столь же простое как сокращение коэффициента, говорят от T (3n) вниз к T (2n), может иметь Огромные значения, когда "n" измеряется в днях если не месяцы.
Существует большой хороший совет здесь, и я уверен, что большинство программистов использовало свое знание сложности время от времени.
Однако я должен сказать понимание, что вычислительная сложность имеет экстремальное значение в области Игр! Да Вы слышали его, на котором "бесполезный" материал является видом игровых жизней программирования материала.
я держал пари, что очень немного профессионалов, вероятно, заботятся о Большом-O так же как игровые программисты.
Я регулярно использую вычисления сложности, в основном потому что я работаю в геопространственном домене с очень большими наборами данных, например, процессах, включающих миллионы и иногда миллиарды декартовых координат. Как только Вы начинаете поражать многомерные проблемы, сложность может быть реальной проблемой, поскольку жадные алгоритмы, которые были бы O (n) в одном размере внезапно, скачкообразно двигаются к O (n^3) в трех измерениях, и не требуется большого количества данных для создания серьезного узкого места. Как я упомянул в подобное сообщение , Вы также видите, что большая нотация O становится громоздкой, когда Вы начинаете иметь дело с группами сложных объектов переменного размера. Порядок сложности может также быть очень информационно-зависим с типичными случаями, работающими намного лучше, чем общие случаи для хорошо разработанного специальный алгоритмы.
также стоит протестировать Ваши алгоритмы при профилировщике, чтобы видеть, является ли то, что Вы разработали, тем, чего Вы достигли. Я нахожу, что большинство узких мест разрешено намного лучше с тонкой настройкой алгоритма, чем улучшенная скорость процессора по всем очевидным причинам.
Для большего количества чтения на общих алгоритмах и их сложностях я нашел работа Sedgewicks и информативный и доступный. Для пространственных алгоритмов O'Rourkes книга по вычислительной геометрии превосходна.
В Вашей нормальной жизни не около компьютера необходимо применить понятие сложности и параллельной обработки. Это позволит Вам быть более эффективными. Когерентность кэш-памяти. Такая вещь.
Да, мое знание сортировки алгоритмов пригодилось однажды, когда я должен был отсортировать стопку студенческих экзаменов. Я использовал сортировку слиянием (но не quicksort или пирамидальная сортировка). При программировании я просто использую любую программу сортировки предложения библиотеки. (еще не должны были сортировать действительно большой объем данных.)
я действительно использую теорию сложности в программировании все время, главным образом в решении, в каких структурах данных использовать, но также и при решении, ли или когда отсортировать вещи, и для многих других решений.
' да ' и' никакой '
да ), я часто использую большая O-нотация при разработке и реализации алгоритмов. Например, когда необходимо обработать 10^3, объекты и сложность первого алгоритма являются O (n журнал (n)) и второго O (n^3), просто можно сказать, что первый алгоритм является почти реальным временем, в то время как вторые требуют значительных вычислений.
Иногда знания [приблизительно 111] классы сложностей непера могут быть полезными. Это может помочь Вам понять, что можно прекратить думать об изобретении эффективного алгоритма, когда некоторая полная NP проблема может быть уменьшена до проблемы, Вы думаете о.
никакой ), Что я описал выше, небольшая часть теории сложностей. В результате трудно сказать, что я использую его, я использую незначительно-незначительную часть его.
я должен признать, что существуют многие проект разработки программного обеспечения, которые не касаются разработки алгоритмов или использования их сложным способом. В таких случаях теория сложности бесполезна. Обычные пользователи алгоритмов часто управляют словами использования 'быстро' и 'медленный', 'x секунды' и т.д.
@Martin: можно ли уточнить мыслительные процессы позади него?
это не могло бы быть столь же явно как присаживание и разработка Нотация "большого О" для решения, но это создает осведомленность о проблеме - и это регулирует Вас к поиску более эффективного ответа, и далеко от проблем в подходах Вы могли бы взять. например, O (n*n) по сравнению с чем-то быстрее, например, поиском слов сохранил в списке по сравнению с сохраненным в trie (изобретенный пример)
, я нахожу, что это имеет значение с тем, какие структуры данных я приму решение использовать, и как я буду работать над большими количествами записей.
Хороший пример мог быть, когда Ваш босс говорит Вам делать некоторую программу, и можно продемонстрировать при помощи вычислительной теории сложности, что, что спрашивает босс, Вы, чтобы сделать не возможны.