ITCS - Популярно об ИИ. Программирование. Стек, очередь и рекурсия - ПОПУЛЯРНО ОБ ИИ
Сегодня: Четверг, 08.12.2016, 01:11 (МСК)| Здравствуйте, Гость| Мой профиль | Регистрация | Вход | RSS

Домашние системы
3D-видения

Роботы и экзоскелеты

Устройства с беспроводным питанием

Новинки в области цифровых камер

Adobe Audition 3. Лучшая в 2010-м
Главная » ПОПУЛЯРНО ОБ ИИ

Популярно об ИИ. Программирование. Стек, очередь и рекурсия

26.07.2010
Сегодня мы поговорим о стеке, очереди и рекурсии. Тема достаточно интересна и очень обширна, потому как рекурсия используется практически везде, иногда не оправданно, а иногда и не самым лучшим образом. Итак, в любом учебнике по информатике вы можете прочитать следующие определения:
  • Стек (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. Пипец. Конечно, реальное программирование и реальная алгоритмизация немного другие. 


Кристофер

Перепечатка материалов или их фрагментов возможна только с согласия автора.





Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Ассоциация боевых роботов
Рекомендуем...
Новости

Разделы

Опросы

Какой язык программирования вы считаете наиболее актуальным сегодня?
Всего ответов: 308

Друзья

3D-кино






Найти на сайте:








Об авторе       Контакты      Вопрос-ответ        Хостинг от uCoz