Популярно об ИИ
Сегодня мы поговорим о стеке, очереди и рекурсии. Тема достаточно интересна и очень обширна, потому как рекурсия используется практически везде, иногда неоправданно, а иногда и не самым лучшим образом. Итак, в любом учебнике по информатике вы можете прочитать следующие определения: . Стек (Stack) — структура данных, содержащая совокупность элементов разного типа (heterogeneous data) в непрерывной области памяти (contiguous block). В ее рамках налагаются ограничения на порядок доступа к данным — "первым пришел, последним ушел", обозначается как FCLS (First Come, Last Served) либо LIFO (Last In – First Out). Как «альтернатива» стеку есть очередь (Queue), порядок доступа данным в которой организован по правилу — «первым пришел, первым ушел», обозначается как FCFS (First come, first served) или же FIFO (First In – First Out). Наиболее яркий пример работы со стеком — рекурсия, с очередью — цикл.
. Рекурсия — вызов подпрограммой (функцией) самой себя.
Что касается стека и очереди, то в System.Collections для .NET Framework есть отдельные классы Stack и Queue, в которых все подробно описано. Заполнение стека проще объяснить ситуацией, когда внутри одной функции вызывается другая. И получается ситуация, когда первая ждет результатов выполнения второй. То есть понятие стека лежит в основе всех программ.
Каждая функция имеет свое определение. Но при этом следует сказать о понятии активации функции — особый объект данных, возникающий при вызове функции на базе ее определения. Другими словами, определение может быть только одно, а активаций сколько угодно (в зависимости от ограничений и т.п.). Простейший пример рекурсии, когда функция вызывает саму себя — вычисление факториала (пишем на С#):
int factorial(int n) {
if (n == 0) { return 1;
} else {
return n * factorial(n - 1);
}
}
После мы вызываем эту функцию, например, набрав factorial(5) (находим факториал 5-ти). Факториал — это произведение всех целых чисел до указанного, также стоит отметить, что факториал 0, т.е. 0!=1.
Итак, при пяти вызывается эта же функция, но уже вычисляющая факториал 4 (строка return n * factorial(n - 1)), но при четырех опять же вызывается функция, но уже вычисляющая факториал 3 и так далее, пока не дойдет до нуля, где известен результат — 1. Потом происходит так называемое разматывание стека. То есть мы знаем, что 0!=1, после получаем 1!=1*1, 2!=1*2, 3!=2*3, 4!=6*4, 5!=24*5. Получаем результат. Как видите, данные помещаются в стек, и все работает по принципу: последним пришел — первым ушел.
***
По существу, рекурсивный вариант с вычислением факториала, так же, как, например, и возведение числа в степень в рамках рекурсии, которые классически представляются в книгах, действительно невыгодны. То есть в нашем случае в памяти хранится 5 активаций. А если мы все это вычислим обычным циклом:
int factorial(int n) {
int k=1;
for (int i=1; i<n+1;)
{ k *= i++; }
return k;
}
То это займет меньше памяти (формируется очередь), а при достаточно объемных вычислениях выигрыш обычных методов в данном случае очевиден. При этом мы можем улучшить наш вариант с циклом, например, если мы знаем, что нужно вычислять факториалы только четных чисел (допустим, будет такое задание). Тогда уместнее написать так:
int factorial(int n) {
int k=1;
for (int i=1; i<n+1;)
{ k *= i++;
k *= i++; }
return k;
}
То есть внутри цикла мы два раза повторили строку k *= i++, уменьшив тем самым количество проделываемых операций (происходит в два раза меньшее количество сравнений i<n+1). На практике очень часто возникают схожие ситуации, то есть оптимизация кода идет в зависимости от задачи. Есть ключевое правило — любая задача, которая может быть решена с помощью рекурсии, может быть решена и без нее. Рекурсия «в книгах» очень часто оправдана просто минимизацией кода, потому как при расчете количества проделываемых операций мы получаем незавидные результаты, но есть варианты необходимости, о которых мы расскажем чуть позже, а сейчас...
Например, игра пятнашки, в которой нам нужно в случайном режиме изначально расставить 15 кнопок с цифрами, ни одна из которых не должна повторяться. Решается как рекурсивно, так и нет. Но самый большой камень преткновения — это модуль сравнения сгенерированного случайного значения в диапазоне от 1 до 16 таким образом, чтобы оно не пересекалось с уже установленными. Рекурсивно это все решать сложно, но… чтобы понять суть рекурсии как таковой и как она работает, очень рекомендую вам самостоятельно написать такой модуль, то есть случайного подбора чисел от 1 до 16 без пересечений. Вы сразу же увидите все сильные и слабые стороны рекурсивных методов. Причем после этого вы посмотрите на многие листинги в известных книгах совершенно другими глазами.
Хотя и с циклами (решение достаточно простое) можно наворотить:). Когда я дал это задание (просто его решить, а вернее, написать пятнашки на ActionScript для Flash) в одном из изданий, один читатель только случайному подбору первоначальной расстановки уделил несколько тысяч строк (практически ассемблер). Правда, ему 12 лет всего отроду, поэтому пять за трудолюбие:).
В общем, оптимизация рекурсии на небольшом уровне — это правильная ее замена на циклы. При малом количестве вычислений она почти никогда не оправдывает себя, хотя мы сделаем рекурсивное вычисление факториала выгодным через несколько абзацев.
Ситуация в корне меняется, когда необходимо производить более сложные расчеты. Например, «дендрохирургия», то есть обрезание ветвей и узлов в деревьях, реализация поиска, сортировка больших массивов, методы которой мы рассмотрели в прошлой части. Причем тогда многие могли отметить, что простые методы базируются на циклах, сложные — на рекурсии. При больших масштабах также правомерна операция, которую мы показали на уровне циклов, но…
***
Давайте попробуем оптимизировать нашу функцию с факториалом таким образом, чтобы уменьшить количество рекурсивных вызовов, например, вдвое. int factorial(int n) {
if (n <= 1) { return 1;
} else {
return n*(n-1)*factorial(n - 2);
}
}
То есть получается в два раза меньшее количество вызовов, опять же но… применительно к условиям конкретной задачи. То есть, тут мы получаем оптимизацию, воспользовавшись той лазейкой, что 0! и 1! равны единице, также мы можем уменьшить количество рекурсивных обращений втрое, хотя внутри функции добавится еще одна операция сравнения:
int factorial(int n) {
if (n <= 1) { return 1;
} else if (n == 2) { return 2;
} else {
return n * (n-1) * (n-2)*factorial(n - 3);
}
}
Механизм вы поняли. Именно так часто оптимизируется рекурсия. Например, в старом флеше с ActionScript 2.0 размер стека был ограничен 256-ю элементами, поэтому факториал 257 классическим способом (самый первый листинг) вычислить с помощью рекурсии вы уже не могли. Оптимизация помогает.
С другой, более реальной ситуацией я столкнулся недавно, когда мне позвонили разработчики ИИ одной из компьютерных игр и сказали что дадут любые деньги:), если я разберусь со стеком в их программе. Он переполнялся, приложение работало очень медленно. Я целый день изучал их алгоритм, после чего просто оптимизировал рекурсию, а результат вообще получился восхитительным — работа ИИ стала происходить незаметно на общем фоне. До этого они даже предусмотрели «крутящиеся часики» вместо курсора, когда «компьютер думает».
Да, есть теория алгоритмов, ее никто не отменяет, и изучают все, но есть и практика алгоритмов. Об этом не стоит забывать.
Когда вы занимаетесь оптимизацией рекурсии, обязательно ставьте счетчик, который будет отображать количество рекурсивных вызовов. Потом его, конечно, нужно отключить.
Есть и еще одно негласное правило: хорошие алгоритмы всегда просты. С этим я сталкивался не раз. Например, когда начинается «взмыливание кода», начинается внедрение каких-то заплаток для исключительных случаев, появляются «кривые» коэффициенты, гиперсложные логические связи, тогда… понятно, что все нужно переделывать.
В завершение
Программирование — это очень интересно. Хотя я недавно открыл школьные учебники и задачники по информатике моей дочери и ужаснулся: как это можно — объяснять тривиальные вещи так сложно. Кто это все написал?! Я вспоминаю, как, будучи студентом и уже выполняя заказы по программированию баз данных под Windows, с удивлением обнаружил, что у нас появился предмет… MS-DOS. Началось все так… открываем конспекты и… чертим там Norton Commander. Полный привет. Конечно, реальное программирование и реальная алгоритмизация немного другие.
Кристофер christopher@tut.by
. Рекурсия — вызов подпрограммой (функцией) самой себя.
Что касается стека и очереди, то в System.Collections для .NET Framework есть отдельные классы Stack и Queue, в которых все подробно описано. Заполнение стека проще объяснить ситуацией, когда внутри одной функции вызывается другая. И получается ситуация, когда первая ждет результатов выполнения второй. То есть понятие стека лежит в основе всех программ.
Каждая функция имеет свое определение. Но при этом следует сказать о понятии активации функции — особый объект данных, возникающий при вызове функции на базе ее определения. Другими словами, определение может быть только одно, а активаций сколько угодно (в зависимости от ограничений и т.п.). Простейший пример рекурсии, когда функция вызывает саму себя — вычисление факториала (пишем на С#):
int factorial(int n) {
if (n == 0) { return 1;
} else {
return n * factorial(n - 1);
}
}
После мы вызываем эту функцию, например, набрав factorial(5) (находим факториал 5-ти). Факториал — это произведение всех целых чисел до указанного, также стоит отметить, что факториал 0, т.е. 0!=1.
Итак, при пяти вызывается эта же функция, но уже вычисляющая факториал 4 (строка return n * factorial(n - 1)), но при четырех опять же вызывается функция, но уже вычисляющая факториал 3 и так далее, пока не дойдет до нуля, где известен результат — 1. Потом происходит так называемое разматывание стека. То есть мы знаем, что 0!=1, после получаем 1!=1*1, 2!=1*2, 3!=2*3, 4!=6*4, 5!=24*5. Получаем результат. Как видите, данные помещаются в стек, и все работает по принципу: последним пришел — первым ушел.
***
По существу, рекурсивный вариант с вычислением факториала, так же, как, например, и возведение числа в степень в рамках рекурсии, которые классически представляются в книгах, действительно невыгодны. То есть в нашем случае в памяти хранится 5 активаций. А если мы все это вычислим обычным циклом:
int factorial(int n) {
int k=1;
for (int i=1; i<n+1;)
{ k *= i++; }
return k;
}
То это займет меньше памяти (формируется очередь), а при достаточно объемных вычислениях выигрыш обычных методов в данном случае очевиден. При этом мы можем улучшить наш вариант с циклом, например, если мы знаем, что нужно вычислять факториалы только четных чисел (допустим, будет такое задание). Тогда уместнее написать так:
int factorial(int n) {
int k=1;
for (int i=1; i<n+1;)
{ k *= i++;
k *= i++; }
return k;
}
То есть внутри цикла мы два раза повторили строку k *= i++, уменьшив тем самым количество проделываемых операций (происходит в два раза меньшее количество сравнений i<n+1). На практике очень часто возникают схожие ситуации, то есть оптимизация кода идет в зависимости от задачи. Есть ключевое правило — любая задача, которая может быть решена с помощью рекурсии, может быть решена и без нее. Рекурсия «в книгах» очень часто оправдана просто минимизацией кода, потому как при расчете количества проделываемых операций мы получаем незавидные результаты, но есть варианты необходимости, о которых мы расскажем чуть позже, а сейчас...
Например, игра пятнашки, в которой нам нужно в случайном режиме изначально расставить 15 кнопок с цифрами, ни одна из которых не должна повторяться. Решается как рекурсивно, так и нет. Но самый большой камень преткновения — это модуль сравнения сгенерированного случайного значения в диапазоне от 1 до 16 таким образом, чтобы оно не пересекалось с уже установленными. Рекурсивно это все решать сложно, но… чтобы понять суть рекурсии как таковой и как она работает, очень рекомендую вам самостоятельно написать такой модуль, то есть случайного подбора чисел от 1 до 16 без пересечений. Вы сразу же увидите все сильные и слабые стороны рекурсивных методов. Причем после этого вы посмотрите на многие листинги в известных книгах совершенно другими глазами.
Хотя и с циклами (решение достаточно простое) можно наворотить:). Когда я дал это задание (просто его решить, а вернее, написать пятнашки на ActionScript для Flash) в одном из изданий, один читатель только случайному подбору первоначальной расстановки уделил несколько тысяч строк (практически ассемблер). Правда, ему 12 лет всего отроду, поэтому пять за трудолюбие:).
В общем, оптимизация рекурсии на небольшом уровне — это правильная ее замена на циклы. При малом количестве вычислений она почти никогда не оправдывает себя, хотя мы сделаем рекурсивное вычисление факториала выгодным через несколько абзацев.
Ситуация в корне меняется, когда необходимо производить более сложные расчеты. Например, «дендрохирургия», то есть обрезание ветвей и узлов в деревьях, реализация поиска, сортировка больших массивов, методы которой мы рассмотрели в прошлой части. Причем тогда многие могли отметить, что простые методы базируются на циклах, сложные — на рекурсии. При больших масштабах также правомерна операция, которую мы показали на уровне циклов, но…
***
Давайте попробуем оптимизировать нашу функцию с факториалом таким образом, чтобы уменьшить количество рекурсивных вызовов, например, вдвое. int factorial(int n) {
if (n <= 1) { return 1;
} else {
return n*(n-1)*factorial(n - 2);
}
}
То есть получается в два раза меньшее количество вызовов, опять же но… применительно к условиям конкретной задачи. То есть, тут мы получаем оптимизацию, воспользовавшись той лазейкой, что 0! и 1! равны единице, также мы можем уменьшить количество рекурсивных обращений втрое, хотя внутри функции добавится еще одна операция сравнения:
int factorial(int n) {
if (n <= 1) { return 1;
} else if (n == 2) { return 2;
} else {
return n * (n-1) * (n-2)*factorial(n - 3);
}
}
Механизм вы поняли. Именно так часто оптимизируется рекурсия. Например, в старом флеше с ActionScript 2.0 размер стека был ограничен 256-ю элементами, поэтому факториал 257 классическим способом (самый первый листинг) вычислить с помощью рекурсии вы уже не могли. Оптимизация помогает.
С другой, более реальной ситуацией я столкнулся недавно, когда мне позвонили разработчики ИИ одной из компьютерных игр и сказали что дадут любые деньги:), если я разберусь со стеком в их программе. Он переполнялся, приложение работало очень медленно. Я целый день изучал их алгоритм, после чего просто оптимизировал рекурсию, а результат вообще получился восхитительным — работа ИИ стала происходить незаметно на общем фоне. До этого они даже предусмотрели «крутящиеся часики» вместо курсора, когда «компьютер думает».
Да, есть теория алгоритмов, ее никто не отменяет, и изучают все, но есть и практика алгоритмов. Об этом не стоит забывать.
Когда вы занимаетесь оптимизацией рекурсии, обязательно ставьте счетчик, который будет отображать количество рекурсивных вызовов. Потом его, конечно, нужно отключить.
Есть и еще одно негласное правило: хорошие алгоритмы всегда просты. С этим я сталкивался не раз. Например, когда начинается «взмыливание кода», начинается внедрение каких-то заплаток для исключительных случаев, появляются «кривые» коэффициенты, гиперсложные логические связи, тогда… понятно, что все нужно переделывать.
В завершение
Программирование — это очень интересно. Хотя я недавно открыл школьные учебники и задачники по информатике моей дочери и ужаснулся: как это можно — объяснять тривиальные вещи так сложно. Кто это все написал?! Я вспоминаю, как, будучи студентом и уже выполняя заказы по программированию баз данных под Windows, с удивлением обнаружил, что у нас появился предмет… MS-DOS. Началось все так… открываем конспекты и… чертим там Norton Commander. Полный привет. Конечно, реальное программирование и реальная алгоритмизация немного другие.
Кристофер christopher@tut.by
Компьютерная газета. Статья была опубликована в номере 23 за 2009 год в рубрике технологии
