Бобр строит каскад плотин и уютную хатку в русле неширокой реки
Насколько большим может быть выигрыш в экономии объема кода за счет (мета)технических подходов/хорошо формализованных практик в виде паттернов, в сравнении с выигрышем, которого можно добиться за счет эээ хорошего ума (очень условно, высокого IQ), с помощью которого под конкретную реализацию придумывается хороший оригинальный алгоритм?
Объективно, в прикладных проектах, где сроки сильно сжаты, за счет известных техник вряд ли возможно добиться выигрыша более пары порядков. Хороший пример, это LLVM (ex-Low Level Virtual Machine, a compiler infrastructure written in C++; it is designed for compile-time, link-time, run-time, and "idle-time" optimization of programs written in arbitrary programming languages).
http://llvm.org/
Association for Computing Machinery вручила ее авторам ACM Software System Award за 2012 год. В частности, последняя версия Delphi переносится на компиляторы LLVM, сейчас уже поддерживает iOS, а скоро (этой осенью) и Андроид.
...the size and complexity of the Free Pascal compiler, which for over 15 years of development and contributions of 55 active developers, today has more than 210,000 lines of code, which makes it unfeasible to study and very difficult to understand even for experienced programmers. The purpose of LLVM-Pascal is to have a similar functionality with up to 4000 lines of code (52 times smaller).
http://code.google.com/p/llvm-pascal/
Исследования в этой области ведутся очень активные, вот очередная позитивная весть:
Research at MIT has resulted in the implementation of a system that can take a description of a task in standard English and churn out the code to do the job. Is this the end of programming?
...examples harvested from the Web to train a computer system to convert natural-language descriptions into regular expressions.
This is a big first step toward allowing everyday users to program their computers without requiring any knowledge of programming language. The techniques they have developed should definitely generalize to other related programming tasks...
A natural language specification of something that is governed by a regular grammar can be converted into a formal language governed by a regular grammar...
http://i-programmer.info/news/98-languages/6090-mit-who-needs-programming-languages.html
A finite state machine is described by a regular grammar and isn't Turing complete
На этом фоне интересно посмотреть, как решаются задачки на Олимпиадах по программированию, для которых характерны жесткие ограничения по времени решения задачи, по объему памяти, по неиспользованию отладчиков (только компиляторы командной строки). Обычно на такую задачу дается 4-5 часов.
Вот например:
Ограничения по времени: 1 секунда на тест
Ограничения по памяти: 64 Мб
Бобр собирается построить каскад плотин и уютную хатку в русле неширокой реки. Так получилось, что река протекает по идеально прямой траектории, и ширина реки настолько мала, что в рамках данной задачи мы можем ею пренебречь. На берегах реки стоят деревья, которые бобр может использовать для строительства. Ученые решили выяснить, насколько оптимально бобр выбирает места для строительства плотин и хатки с точки зрения минимального суммарного расстояния, на которое необходимо переносить деревья.
Напишите программу, которая по заданным координатам деревьев относительно начала прямого участка реки, если считать ось сонаправленной течению определяет координаты объектов, соответствующие минимальному суммарному расстоянию, на которое необходимо переносить деревья.
В первой строке входных данных содержится единственное целое положительное число 1<=T<=10 - количество тестовых блоков, идущих друг за другом. В первой строке каждого тестового блока содержится два целых положительных числа 1<=N<=1000, 0<=М<=10, 0<=L<=100 - соответственно количество деревьев, растущих на берегах реки, количество деревьев, необходимое для возведения одного объекта и количество объектов, которые необходимо возвести. В каждой из следующих N строчек записано единственное положительное вещественное число - расстояние в метрах от начала прямого участка реки (самого высокого по течению) до места, где растет соответствующее дерево...
Тут еще разбор задачек с последнего Чемпионата мира:
http://habrahabr.ru/company/yandex/blog/186316/
Если решать "не думая", без математики, то в случае, когда N=1000, а L=100, перебором в лоб в секунду никак не уложиться. На даже если это и допустить, объем программы составит несколько сотен строк кода. Я бы стал ее решать классическим инженерным методом "проб и находок": написал базовую схему ввода-вывода, затем хоть как-то работающий код (выдающий, допустим, 10% от идеального решения), и потом начал экспериментировать/оптимизировать. Скорее всего за 5 часов удалось бы найти какой-то рациональный вариант (например, 70% от оптимального), но точное решение наверняка заняло бы часов десять, а может и больше. Тем более что без отладчика.
А вот математическое решение (на олимпиадах раньше вообще очень любили ДП) займет скорее всего десятки строк. Это правда тоже не думание, а скорее знание математических паттернов, но тот кто знает, сделает за пару часов.
На практике конечно чистой математики бывает не так много, однако тренировка чистого алгоритмического мышления, которое и не programming in small, и не programming in large, может тоже дать свой порядок выигрыша. Там, где даже самый хороший прикладной программист выдает длинный работающий код задачи, даже не подозревая о существовании либо аппарата ее компактного решения, либо мета-принципов алгоритмического решения классов таких задач.
Объективно, в прикладных проектах, где сроки сильно сжаты, за счет известных техник вряд ли возможно добиться выигрыша более пары порядков. Хороший пример, это LLVM (ex-Low Level Virtual Machine, a compiler infrastructure written in C++; it is designed for compile-time, link-time, run-time, and "idle-time" optimization of programs written in arbitrary programming languages).
http://llvm.org/
Association for Computing Machinery вручила ее авторам ACM Software System Award за 2012 год. В частности, последняя версия Delphi переносится на компиляторы LLVM, сейчас уже поддерживает iOS, а скоро (этой осенью) и Андроид.
...the size and complexity of the Free Pascal compiler, which for over 15 years of development and contributions of 55 active developers, today has more than 210,000 lines of code, which makes it unfeasible to study and very difficult to understand even for experienced programmers. The purpose of LLVM-Pascal is to have a similar functionality with up to 4000 lines of code (52 times smaller).
http://code.google.com/p/llvm-pascal/
Исследования в этой области ведутся очень активные, вот очередная позитивная весть:
Research at MIT has resulted in the implementation of a system that can take a description of a task in standard English and churn out the code to do the job. Is this the end of programming?
...examples harvested from the Web to train a computer system to convert natural-language descriptions into regular expressions.
This is a big first step toward allowing everyday users to program their computers without requiring any knowledge of programming language. The techniques they have developed should definitely generalize to other related programming tasks...
A natural language specification of something that is governed by a regular grammar can be converted into a formal language governed by a regular grammar...
http://i-programmer.info/news/98-languages/6090-mit-who-needs-programming-languages.html
A finite state machine is described by a regular grammar and isn't Turing complete
На этом фоне интересно посмотреть, как решаются задачки на Олимпиадах по программированию, для которых характерны жесткие ограничения по времени решения задачи, по объему памяти, по неиспользованию отладчиков (только компиляторы командной строки). Обычно на такую задачу дается 4-5 часов.
Вот например:
Ограничения по времени: 1 секунда на тест
Ограничения по памяти: 64 Мб
Бобр собирается построить каскад плотин и уютную хатку в русле неширокой реки. Так получилось, что река протекает по идеально прямой траектории, и ширина реки настолько мала, что в рамках данной задачи мы можем ею пренебречь. На берегах реки стоят деревья, которые бобр может использовать для строительства. Ученые решили выяснить, насколько оптимально бобр выбирает места для строительства плотин и хатки с точки зрения минимального суммарного расстояния, на которое необходимо переносить деревья.
Напишите программу, которая по заданным координатам деревьев относительно начала прямого участка реки, если считать ось сонаправленной течению определяет координаты объектов, соответствующие минимальному суммарному расстоянию, на которое необходимо переносить деревья.
В первой строке входных данных содержится единственное целое положительное число 1<=T<=10 - количество тестовых блоков, идущих друг за другом. В первой строке каждого тестового блока содержится два целых положительных числа 1<=N<=1000, 0<=М<=10, 0<=L<=100 - соответственно количество деревьев, растущих на берегах реки, количество деревьев, необходимое для возведения одного объекта и количество объектов, которые необходимо возвести. В каждой из следующих N строчек записано единственное положительное вещественное число - расстояние в метрах от начала прямого участка реки (самого высокого по течению) до места, где растет соответствующее дерево...
Тут еще разбор задачек с последнего Чемпионата мира:
http://habrahabr.ru/company/yandex/blog/186316/
Если решать "не думая", без математики, то в случае, когда N=1000, а L=100, перебором в лоб в секунду никак не уложиться. На даже если это и допустить, объем программы составит несколько сотен строк кода. Я бы стал ее решать классическим инженерным методом "проб и находок": написал базовую схему ввода-вывода, затем хоть как-то работающий код (выдающий, допустим, 10% от идеального решения), и потом начал экспериментировать/оптимизировать. Скорее всего за 5 часов удалось бы найти какой-то рациональный вариант (например, 70% от оптимального), но точное решение наверняка заняло бы часов десять, а может и больше. Тем более что без отладчика.
А вот математическое решение (на олимпиадах раньше вообще очень любили ДП) займет скорее всего десятки строк. Это правда тоже не думание, а скорее знание математических паттернов, но тот кто знает, сделает за пару часов.
На практике конечно чистой математики бывает не так много, однако тренировка чистого алгоритмического мышления, которое и не programming in small, и не programming in large, может тоже дать свой порядок выигрыша. Там, где даже самый хороший прикладной программист выдает длинный работающий код задачи, даже не подозревая о существовании либо аппарата ее компактного решения, либо мета-принципов алгоритмического решения классов таких задач.