Редактирование: Парадигмы программирования, 02 лекция (от 01 октября)

Материал из eSyr's wiki.

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

<pre>
void hello(int n)
{
if(n<1)return;
printf("Hello world\n");
hello(n-1);
}
</pre>
Будет ли менее эффективно чем цикл?
Цикл такой не развернется скорее всего.
Если оптимизатор развернет хвостовую рекурсию, то будет парочка присваиваний при занятий стекового фрейма.
Есть сомнения. Есть подозрения, что эффективность будет примерно одинаковая.
Пока есть вывод, вы точно не увидите разницы в эффективности, принтф жрет намного больше.

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

Это был пример простой рекурсии. Простая рекурсия --- функция вызвает сама себя в явном виде один раз.
Здесь р еще и хвостовая, то есть р вызов последний в функции. Ее можно реализовать не тратя стек.

Другой пример, еопирование строки.
Начинающий программист.
<pre>
void strcpy(char* dest, const char* src)
{
int i;
i = 0;
while(src[i]!='\0')
{
	dest[i] = src[i];
	i++;
}
dest[i]='\0';
}
<pre>
Потом придет опытный сишник, и скажет "Гагага, у нас же есть арифметика указателей!" В си массивов как таковых практически нет, есть арифм указателей.
Хардкорный сишник напишет
while((*dest++=*src++)){};//(())to make the stupid compiler happy
Нет индекса.
Суперпозиции операций, пришедшие из ассемблера. Творцы си привыкли программировать на автокоде. Значение которое присваивают, остается в акумуляторе. Насколько особенность машины фон неймана влияет на япы и на мышление. Когда керниган томпсон и ричи придумывали язык си, они явно делали с прицелом на это. На пентиуме strcpy обычно реализуется как ассемблерная вставка. 
cinst char * src -- указываем на немодифицируюмую строку
char * const src -- немодифируем сам указатель

Теперь следующий момент. Придет человек который давно писал на си, а потом его посадили на лисп и догло долго не отпускали. что может совершенно случайно написать человек, кторый пишет на лиспе
<pre>
if((*dest=*src))
strcpy(dest+1, src+1);
</pre>
возможно, но выглядит искуственно.
Функция strdup дублирует строку. Класс реализация 2 прохода --- считаем длину, потом пробегаем-копируем. Два прохода, нехорошо.
<pre>
char* strdup(const char* str)
{
	return do_strdup(str, 0);
}
//static функции недоступны вне модуля, используется для вспомогательных функций
static char* do_strdup(const char* str, int l)
{
	char* res;
	if(*str)
		res = do_strdup(str+1, l+1); //оставили заказ на память, на обратном ходе ей воспользуемся
	else
		res = malloc(l+1);
	res[l] = *str;
	return res; 
}
</pre>
Чем оно может быть лучше? Да ничем. Но, это может быть удобно, если у нас поток ввода, а не строка. Там надо работать в один проход. Можем минимизировать вызовы функции маллок.

Есть функция gets(char* buffer) все знают, что ее нельзя использовать? Она читает до конца строки, и пишет буффер, но буффер ограничен. Естественно, хацкер поддсунет буффер оверфлоу. 
Способы разные бывают.
Второкурсники делают список букв. 8 байт на одну букву с учетом выравнивания. А с учетом кванта маллока, который 32 байта..
Следующий уровень --- динам. массив. Иногда бывает даже новый маллок на каждую букву. Про реаллок не все знают, а в с++ ео и нет.
Бывает стратеги удвоения выделяемой памяти. 
Но если сделать рекурсивные вызовы вглубь и так пока мы не найдем строки, сделать в конце маллок, потом распихать. Получится маллок ровно один. Сколько памяти тратится? В фрейме лок переменная, указатель, адрес фозврата, ebp. 16 байт на каждый вызов. Вроде бы как то многовато. Но стек то штука временная, освобождение легкое, в отличие от маллкоков. Если в стек не поместимся, можем нарваться на выделение новой страницы, но это не так страшно.
В ткаой ситуации это может дать выигрыш в производительности, запросто.
Упражнение
Рекурсивная функция,заменяющая группы пробелов на один пробел. Рекурсивная реализация. На машине, а не на бумажке.

Накопительный параметр.
Счетчик у нас уже был, а интересней когда параметр накапливает что нибудь серьезное. Как вариант --- переставить элементы списка в обратном порядке.
Проще это делать не деструктивно, сделать новый сисок, хотя техника позволяет все сделать без единого маллока и без единого фри.
<pre>
struct item
{
	int data;
	struct item* next;
};
</pre>
Если применить лобовой способ. Первый вариант с двумя указателями. Если без них, то сосвесм плохо, потому что добавление в конец списка штука очень неприятная. 
<pre>
struct item* reverselist(struct item*list)
{
	return do_reverse_list(list, NULL);
}
static struct item* do_reverse_list(struct item* list, struct item* result)
{
if(!list)
	return result;
struct item* tmp = struct item*malloc(sizeof(struct item));//поьзуйтесь тайпдефом, не делайте как я
tmp = list->data;
tmp->next = result;
return do_reverse_list(list->next, tmp);
}
</pre>
Опять хвостовая рекурсия. 
Это все были примеры простой рекурсии.

Параллельная рекурсия.
<pre>f()
{
g(..f(), ..f());
}</pre>
канонический пример --- обход дерева с, например, суммированием.

Взаимная рекурсия
<pre>f(...){...g()};
g(...){...f()};</pre>

Рекурсия высших порядков.
<pre>f(..){..f(..f(...))};</pre>
Простейший пример функция Аккремана. Если без головы делать, то вычисляем некоторые значения по многу раз, поэтому похорошему вводится кэширование уже вычисленного. 
Рекурсия высоких порядков встречается крайне редко. В реальной жизни однажды надо было стаскивать с трех серверов  данные, и там была криптография с открытыми ключами, и все друг от друга зависело. Появилась комбинация взаимной и выского порядка.

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

Хрестоматийная задача. 
Сопоставление строки с образцом. * произвольная подстрока, втч пустая, ? -- лююой один символ.
Было решение на сотню строк на джаве в жж, все было подсвечено, красиво, но совершенно непонятно. 
Имеет и рекурсивное простое решение, и циклическое несложное. Но решение на циклах как правило знают только те, кто умеет пользоваться рекурсией. Задача по сути своей рекурсивная. Циклическое решение слово в слово повторяет решение рекурсивное, только с явным запоминанием тех данных, которые при рекурсии остаются на стеке.

Итак, чисто рекурсивное решение. Сначала я это написал на лиспе. Сишное решение слово в слово повторяет то, что получилось на лиспе.

<pre>
int match(const char* word, const char* pattern);
int starmatch(const char*word, const char* pattern)
{
	if(match(word, pattern)) return 1;
	if(!word) return 0;
	return starmatch(word+1, pattern); 
}
</pre>

<pre>
int match(const char* word, const char* pattern)
{
	switch(*pattern)
	{
		case '\0': return (*word == '\0');
		case '?': return (!*word)?0:match(word+1, pattern+1);
		case '*': return starmatch(word, pattern+1);
		default: return (*word != *pattern)?0:match(word+1, pattern+1);
	}
}
</pre>

Некоторые программисты боятся рекурсии. Чтобы не боятся... Ну, язык си рекурсию не стимулирует ни разу, но он ее поддерживает. Если мы будем писать на си, использовать рекурсию мы не научимся. нужен более интересный язык, который будет стимулировать, поощрять использование рекурсии. Даже если лисп никогда не будете использовать на практике, его стоит изучить, чтобы уметь использовать рекурсию. 
С регекспом сопоставится так на халяву не получится, там потяжелее будет, хотя принцип абсолютно тот же.

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Получено с http://esyr.us/wiki/%D0%9F%D0%B0%D1%80%D0%B0%D0%B4%D0%B8%D0%B3%D0%BC%D1%8B_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F%2C_02_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_01_%D0%BE%D0%BA%D1%82%D1%8F%D0%B1%D1%80%D1%8F%29

Редактирование: Парадигмы программирования, 02 лекция (от 01 октября)

Материал из eSyr's wiki.

Просмотры

Личные инструменты

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты

@@ Строка 1: / Строка 1: @@
-* Аудиозапись: http://esyr.org/lections/audio/paradigms_2009_winter/pp02.ogg
 <pre>
 void hello(int n)
@@ Строка 9: / Строка 7: @@
 }
 </pre>
-Будет ли менее эффективно, чем цикл?
+Будет ли менее эффективно чем цикл?
-Цикл такой не развернется, скорее всего.
+Цикл такой не развернется скорее всего.
 Если оптимизатор развернет хвостовую рекурсию, то будет парочка присваиваний при занятий стекового фрейма.
-Есть подозрения, что эффективность будет примерно одинаковая.
+Есть сомнения. Есть подозрения, что эффективность будет примерно одинаковая.
-Пока есть вывод, вы точно не увидите разницы в эффективности, printf() жрет намного больше.
+Пока есть вывод, вы точно не увидите разницы в эффективности, принтф жрет намного больше.
-Таким образом, заявления о том, что рекурсия неэффективна, не всегда оправданы.
+Таким образом, заявления о том, что рекурсия неэффективна не всегда оправданы.
-Это был пример простой рекурсии. Простая рекурсия --- функция вызывает сама себя в явном виде один раз.
+Это был пример простой рекурсии. Простая рекурсия --- функция вызвает сама себя в явном виде один раз.
-Здесь рекурсия еще и хвостовая, то есть рекурсивный вызов последний в функции. Ее можно реализовать не тратя стек.
+Здесь р еще и хвостовая, то есть р вызов последний в функции. Ее можно реализовать не тратя стек.
 Другой пример, еопирование строки.
-Начинающий программист:
+Начинающий программист.
 <pre>
 void strcpy(char* dest, const char* src)
@@ Строка 34: / Строка 32: @@
 dest[i]='\0';
 }
-</pre>
+<pre>
-Потом придет опытный сишник, и скажет "Гагага, у нас же есть арифметика указателей!" В си массивов, как таковых, практически нет, есть арифмитические  указатели.
+Потом придет опытный сишник, и скажет "Гагага, у нас же есть арифметика указателей!" В си массивов как таковых практически нет, есть арифм указателей.
 Хардкорный сишник напишет
 while((*dest++=*src++)){};//(())to make the stupid compiler happy
 Нет индекса.
-Суперпозиции операций, пришедшие из ассемблера. Творцы си привыкли программировать на автокоде. Значение которое присваивают, остается в аккумуляторе. Насколько особенность машины фон неймана влияет на языки программирования и на мышление. Когда керниган томпсон и ричи придумывали язык си, они явно делали с прицелом на это. На пентиуме strcpy обычно реализуется как ассемблерная вставка.
+Суперпозиции операций, пришедшие из ассемблера. Творцы си привыкли программировать на автокоде. Значение которое присваивают, остается в акумуляторе. Насколько особенность машины фон неймана влияет на япы и на мышление. Когда керниган томпсон и ричи придумывали язык си, они явно делали с прицелом на это. На пентиуме strcpy обычно реализуется как ассемблерная вставка.
 cinst char * src -- указываем на немодифицируюмую строку
 char * const src -- немодифируем сам указатель
-Теперь следующий момент. Придет человек который давно писал на си, а потом его посадили на лисп и долго не отпускали. Что может совершенно случайно написать человек, который пишет на лиспе:
+Теперь следующий момент. Придет человек который давно писал на си, а потом его посадили на лисп и догло долго не отпускали. что может совершенно случайно написать человек, кторый пишет на лиспе
 <pre>
 if((*dest=*src))
 strcpy(dest+1, src+1);
 </pre>
-возможно, но выглядит искусственно.
+возможно, но выглядит искуственно.
-Функция strdup дублирует строку. Классическая реализация 2 прохода --- считаем длину, потом пробегаем-копируем. Два прохода, нехорошо.
+Функция strdup дублирует строку. Класс реализация 2 прохода --- считаем длину, потом пробегаем-копируем. Два прохода, нехорошо.
 <pre>
 char* strdup(const char* str)
@@ Строка 67: / Строка 65: @@
 }
 </pre>
-Чем оно может быть лучше? Да ничем. Но, это может быть удобно, если у нас поток ввода, а не строка. Там надо работать в один проход. Можем минимизировать вызовы функции malloc().
+Чем оно может быть лучше? Да ничем. Но, это может быть удобно, если у нас поток ввода, а не строка. Там надо работать в один проход. Можем минимизировать вызовы функции маллок.
-Есть функция gets(char* buffer), все знают, что ее нельзя использовать? Она читает до конца строки, и пишет в буфер, но буфер ограничен. Естественно, хацкер подсунет буфер оверфлоу.
+Есть функция gets(char* buffer) все знают, что ее нельзя использовать? Она читает до конца строки, и пишет буффер, но буффер ограничен. Естественно, хацкер поддсунет буффер оверфлоу.
 Способы разные бывают.
-Второкурсники делают список букв. 8 байт на одну букву с учетом выравнивания. А с учетом кванта malloc(),размер  которого 32 байта...
+Второкурсники делают список букв. 8 байт на одну букву с учетом выравнивания. А с учетом кванта маллока, который 32 байта..
-Следующий уровень --- дин. массив. Иногда бывает даже новый malloc() на каждую букву. Про realloc() не все знают, а в с++ его и нет.
+Следующий уровень --- динам. массив. Иногда бывает даже новый маллок на каждую букву. Про реаллок не все знают, а в с++ ео и нет.
-Бывают стратеги удвоения выделяемой памяти.
+Бывает стратеги удвоения выделяемой памяти.
-Но если сделать рекурсивные вызовы вглубь и так пока мы не найдем строки, сделать в конце malloc(), потом распихать. Получится malloc() ровно один. Сколько памяти тратится? В фрейме локальная переменная, указатель, адрес возврата, ebp. 16 байт на каждый вызов. Вроде бы как-то многовато. Но стек-то штука временная, освобождение легкое, в отличие от malloc()'ов. Если в стек не поместимся, можем нарваться на выделение новой страницы, но это не так страшно.
+Но если сделать рекурсивные вызовы вглубь и так пока мы не найдем строки, сделать в конце маллок, потом распихать. Получится маллок ровно один. Сколько памяти тратится? В фрейме лок переменная, указатель, адрес фозврата, ebp. 16 байт на каждый вызов. Вроде бы как то многовато. Но стек то штука временная, освобождение легкое, в отличие от маллкоков. Если в стек не поместимся, можем нарваться на выделение новой страницы, но это не так страшно.
-В такой ситуации это может дать выигрыш в производительности, запросто.
+В ткаой ситуации это может дать выигрыш в производительности, запросто.
-Упражнение:
+Упражнение
 Рекурсивная функция,заменяющая группы пробелов на один пробел. Рекурсивная реализация. На машине, а не на бумажке.
 Накопительный параметр.
 Счетчик у нас уже был, а интересней когда параметр накапливает что нибудь серьезное. Как вариант --- переставить элементы списка в обратном порядке.
-Проще это делать не деструктивно,а сделать новый список, хотя техника позволяет все сделать без единого malloc()'а и без единого free.
+Проще это делать не деструктивно, сделать новый сисок, хотя техника позволяет все сделать без единого маллока и без единого фри.
 <pre>
 struct item
@@ Строка 89: / Строка 87: @@
 };
 </pre>
-Если применить лобовой способ. Первый вариант с двумя указателями. Если без них, то совсем плохо, потому что добавление в конец списка - штука очень неприятная.
+Если применить лобовой способ. Первый вариант с двумя указателями. Если без них, то сосвесм плохо, потому что добавление в конец списка штука очень неприятная.
 <pre>
 struct item* reverselist(struct item*list)
@@ Строка 122: / Строка 120: @@
 Рекурсия высших порядков.
 <pre>f(..){..f(..f(...))};</pre>
-Простейший пример функция Аккремана. Если без головы делать, то вычисляем некоторые значения помногу раз, поэтому по хорошему вводится кэширование уже вычисленного.
+Простейший пример функция Аккремана. Если без головы делать, то вычисляем некоторые значения по многу раз, поэтому похорошему вводится кэширование уже вычисленного.
-Рекурсия высоких порядков встречается крайне редко. Однажды надо было стаскивать с трех серверов  данные, и там была криптография с открытыми ключами, и все друг от друга зависело. Появилась комбинация взаимной рекурсии и рекурсии высокого порядка.
+Рекурсия высоких порядков встречается крайне редко. В реальной жизни однажды надо было стаскивать с трех серверов  данные, и там была криптография с открытыми ключами, и все друг от друга зависело. Появилась комбинация взаимной и выского порядка.
-Фанаты haskell утверждали, что применяли рекурсию третьего и четвертого порядка. В четвертый порядок я не верю, в третий --- с трудом, но это особенный люди. Четвертый порядок, это как "печатаю со скоростью 900 знаков в минуту, но такая фигня получается".
+Фанаты хаскеля утверждали, что применяли рекурсия третьего и четвертого порядка. В четвертый порядок я не верю, в третий --- с трудом, но это особенный люди. Четверты порядок, это как "печатая со скоростью 900 знаков в минуту, такая фигня получается".
 Хрестоматийная задача.
-Сопоставление строки с образцом. * произвольная подстрока, в том числе пустая, ? -- любой один символ.
+Сопоставление строки с образцом. * произвольная подстрока, втч пустая, ? -- лююой один символ.
-Было решение на сотню строк на java в жж, все было подсвечено, красиво, но совершенно непонятно.
+Было решение на сотню строк на джаве в жж, все было подсвечено, красиво, но совершенно непонятно.
-Имеет место быть и рекурсивное простое решение, и циклическое несложное. Но решение на циклах как правило знают только те, кто умеет пользоваться рекурсией. Задача по сути своей рекурсивная. Циклическое решение слово в слово повторяет решение рекурсивное, только с явным запоминанием тех данных, которые при рекурсии остаются на стеке.
+Имеет и рекурсивное простое решение, и циклическое несложное. Но решение на циклах как правило знают только те, кто умеет пользоваться рекурсией. Задача по сути своей рекурсивная. Циклическое решение слово в слово повторяет решение рекурсивное, только с явным запоминанием тех данных, которые при рекурсии остаются на стеке.
 Итак, чисто рекурсивное решение. Сначала я это написал на лиспе. Сишное решение слово в слово повторяет то, что получилось на лиспе.
@@ Строка 157: / Строка 155: @@
 </pre>
-Некоторые программисты боятся рекурсии. Чтобы не боятся... Ну, язык си рекурсию не стимулирует ни разу, но он ее поддерживает. Если мы будем писать на си, использовать рекурсию мы не научимся. нужен более интересный язык, который будет стимулировать, поощрять использование рекурсии. Даже если вы лисп никогда не будете использовать на практике, его стоит изучить, чтобы уметь использовать рекурсию.
+Некоторые программисты боятся рекурсии. Чтобы не боятся... Ну, язык си рекурсию не стимулирует ни разу, но он ее поддерживает. Если мы будем писать на си, использовать рекурсию мы не научимся. нужен более интересный язык, который будет стимулировать, поощрять использование рекурсии. Даже если лисп никогда не будете использовать на практике, его стоит изучить, чтобы уметь использовать рекурсию.
-С регекспом сопоставиться так на халяву не получится, там потяжелее будет, хотя принцип абсолютно тот же.
+С регекспом сопоставится так на халяву не получится, там потяжелее будет, хотя принцип абсолютно тот же.
 {{Парадигмы программирования}}
 {{Lection-stub}}