Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: 1 [2]  Все   Вниз
  Печать  
Автор Тема: Задачка  (Прочитано 35461 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Anonymous
Гость
« Ответ #30 : 18-11-2003 15:39 » 

а, дошло!  Отлично

______
1153
Записан
grozny
Гость
« Ответ #31 : 19-11-2003 04:56 » 

Цитата

Был уверен, что это не так, но захотелось убедиться воочию. в предыдущую программку ввел "слово" размером 50. Проскочила.
Длиннее было лень буквы считать, тем более что наверняка этот предел уж куда больше.


да не настаиваю, что для данной задачи рекурсивное решение - непригодное с практической точки зрения. Всё зависит от граничных условий. 50 буковок - мало, конечно, 1 Мб стэк не вычерпать. И разницы в скорости не ощутить.

А чё, я разве утверждал, что реверсия 50 буковок исчерпает стэк? Если так, то неясно выразился. По-моему, я приводил пример из разбиения отрезков в несколько тыщ отрезков на интерацию и 6-7 итераций на отбой...

Вот фразы на немецком, например, знаш какие длинные бывают - на 200 символов. Я шокирован!

А вот попробуй, реверсировать текст "Войны и Мир", например. Всего-то пара мегабайт.

Другой момент - скорость. Исходя из общих соображений, рекурсия (вызов ф-ции) всегда медленнее, чем итерация цикла.

Если не лень, то сравни время обработки набора из, ну скажем, 100000 случайных слов твоего любимого размера (50? Отлично) рекурсивным и развёрнутым алгоритмом.

Мне - лень, 8)  поэтому нагло утверждаю, что рекурсия будет медленнее раза эдак в 3 минимум.
Записан
Alf
Гость
« Ответ #32 : 19-11-2003 08:05 » 

Цитата: grozny

А чё, я разве утверждал, что реверсия 50 буковок исчерпает стэк? Если так, то неясно выразился.

Скорее всего, действительно неясно. Ибо фраза "Глубина рекурсии в MSVC 6.0 реально то ли 6, то ли 8, но всяко меньше 10" действительно может быть понята по-разному. Я воспринял это как глубину вызова, а что имел в виду ты?
Цитата: grozny
Вот фразы на немецком, например, знаш какие длинные бывают - на 200 символов. Я шокирован!

Именно это, кстати, мне и пришло в голову, когда писал об ограничениях программы. Ну что ж, если на перевернутые тексты создастся повышенный спрос, выпустим специальную версию для Германии с увеличенным стеком  Отлично
А если серьезно, то на один вызов уходит немного меньше 100 байт. Думаю, и 20-килобайтный стек современный комп выделить сумеет.
Цитата: grozny
А вот попробуй, реверсировать текст "Войны и Мир", например. Всего-то пара мегабайт.

А вот запросто. Если посмотришь внимательнее, то увидишь, что на самом деле рекурсивна только функция реверса слова. Уткнулись в пробел - пошла обратная раскрутка стека (собственно, этим-то я и воспользовался для извлечения литер в обратном порядке). Так что максимальная глубина рекурсии равна длине самого длинного слова в тексте.
Вот кабы переворачивать весь текст - другое дело. Но там бы я и не рискнул на рекурсию. Во-первых, и впрямь памяти не напасешься, во-вторых, искать начало и конец цепочки не нужно - она одна, и итерация будет столь же краткой и выразительной, а то и получше.
Цитата: grozny
Другой момент - скорость. Исходя из общих соображений, рекурсия (вызов ф-ции) всегда медленнее, чем итерация цикла.

Кто же спорит. Если нужна жесткая оптимизация по времени выполнения, то однозначный выбор в пользу итерации. Хотя наперед тут я бы не зарекался. Во всех представленных итерационных алгоритмах присутствуют либо вызовы библиотечных функций для определения длины цепочки, либо собственные заменители, а они тоже не мгновенны.
Цитата: grozny
Если не лень, то сравни время обработки набора из, ну скажем, 100000 случайных слов твоего любимого размера (50? Отлично) рекурсивным и развёрнутым алгоритмом.

Давай только выберем, какой из вариантов берем за эталон итеративного подхода. Их много накидали все-таки. С рекурсией проще - выбирать не из чего.
Записан
Kuzmich
Гость
« Ответ #33 : 19-11-2003 13:03 » 

Объясните пожалуйста как это понимать:
(char* p) понятно, а что значит (char* &p)  :?:
Записан
Alf
Гость
« Ответ #34 : 19-11-2003 14:57 » 

Цитата: Kuzmich
Объясните пожалуйста как это понимать:
(char* p) понятно, а что значит (char* &p)  :?:

Я так понял, вопрос ко мне? Проглядел другие варианты, ни у кого больше не нашел эту конструкцию.
Сам по себе значок амперсанда & означает оператор поименования (получения ссылки). Если раньше не приходилось сталкиваться, то проще всего представить его себе как обратный к оператору разыменования *. Наверное, это выглядит сумбурно, поэтому поясню небольшим примером:
Код:
SomeType st; // переменная какого-то типа
SomeType *stp; // указатель на тот же тип
...
stp = &st; // присвоили stp ссылку на st
// отныне stp указывает на st,
//   т.е. *stp и st на самом деле одно и то же

В данном случае конструкция (char* &p) означает, что я передаю в функцию указатель на char по ссылке.
Дело в том, что параметры в С и С++ передаются в функцию по значению, т.е. функция получает копию значения аргумента. Таким образом функции защищают программу от побочных действий (правила хорошего тона диктуют явный возврат значения через результат функции, но не всегда так получается).
Передавая указатель на char по ссылке (фактически передается адрес указателя), я получил возможность в качестве побочного эффекта функции продвигать его на следующий символ, что в данном случае пришлось весьма кстати.
Надеюсь, не запутал еще сильнее?
Записан
grozny
Гость
« Ответ #35 : 19-11-2003 23:16 » 

Цитата: Alf
Цитата: grozny

А чё, я разве утверждал, что реверсия 50 буковок исчерпает стэк? Если так, то неясно выразился.

Скорее всего, действительно неясно. Ибо фраза "Глубина рекурсии в MSVC 6.0 реально то ли 6, то ли 8, но всяко меньше 10" действительно может быть понята по-разному. Я воспринял это как глубину вызова, а что имел в виду ты?

Да, это глубина вызова, но для моей задачи (а не для ревервирования слов), которую я реализовал под MSVC 6 (покрытие отрезков) . Перечитал свой мессадж - и вправду непонятно.  :oops:

Как было: быстренько написал "красивое" рекурсивное решение, протестировал на простеньких случаях (10-20 отрезков) - всё отлично, но на первом же боевом случае (5-6 тыщ отрезков) задачка упала в рекурсии (на глубине то ли 6, то ли 8) и пришлось разворачивать рекурсию в цикл.

Цитата: grozny
А вот попробуй, реверсировать текст "Войны и Мир", например. Всего-то пара мегабайт.


уточняю условие  :twisted: - вся "Война и Мир" - одно слово. Мой пойнт в том, что реализация рекурсии - всегда хрупкая и малопредсказуемая программа. Т.е. малейшие модификации граничных условий убивают твою программу (что часто бывает в реальной жизни, ага - назавтра приходит заказчик  и говорит, что слова у пигмейском языке бывают и 1000 буковок, и вообще он задумывается над реверсированием Торы в 10 книгах Улыбаюсь.

Применение рекурсии даёт неустойчивое решение к вариации граничных условий, учёно выражаясь.

И оттого для практической жизни луче приучить себя сразу разворачивать рекурсию в итерацию. Чтоб потом не переписывать.

Цитата: grozny
Другой момент - скорость. Исходя из общих соображений, рекурсия (вызов ф-ции) всегда медленнее, чем итерация цикла.


Кто же спорит. Если нужна жесткая оптимизация по времени выполнения, то однозначный выбор в пользу итерации.

Что там у нас? один вызов strlen() на слово (не глядя в код). Против рекурсивного вызова ф-ции на каждой букве. Те самые разы.

Цитата

Давай только выберем, какой из вариантов берем за эталон итеративного подхода. Их много накидали все-таки. С рекурсией проще - выбирать не из чего.


да пофигу - какой нравится. Я ж утверждаю, что они в разных скоростных категориях. Ну мой, например  Отлично
Записан
Alf
Гость
« Ответ #36 : 20-11-2003 00:23 » 

Цитата: grozny
...Т.е. малейшие модификации граничных условий убивают твою программу...
...
Применение рекурсии даёт неустойчивое решение к вариации граничных условий, учёно выражаясь.

Согласен... Мизерная такая вариация граничных условий, на каких-то жалких 6 порядков. Переход с байт в мегабайты, даже и упоминать такой пустяк неловко.
Для натурного эксперимента касательно неустойчивости граничных условий можно взять, скажем, легковой автомобиль и нагрузить его... Нет, не в миллион раз больше максимальной паспортной нагрузки, у меня и гирь столько не найдется. Думаю, хватит и 10-кратной перегрузки. Фото того, что останется, потом выложим на форум.
Цитата: grozny

И оттого для практической жизни луче приучить себя сразу разворачивать рекурсию в итерацию. Чтоб потом не переписывать.

Любые проявления экстремизма не приветствую. По мне, так куда полезнее для практической жизни владеть обоими подходами, а также обладать чувством меры, которое подскажет, когда какой уместнее.
Каюсь, грешен. Кто-то произнес заветное слово "рекурсия", после которого руки сам потянулись немного нахулиганить в этом направлении. В данном случае рекурсия притянута за уши скорее в качестве анекдота, решения наизнанку (которое тем не менее работает в пределах ограничений, установленных автором задачи. Шла бы речь об инверсии терабайтных цепочек, и мысли бы такой не возникло). Сработали застарелые Лиспо-Прологовские инстинкты.
Однако есть же задачи, рекурсивные по самой своей сути. Попробуйте-ка построить итеративный калькулятор арифметических выражений по всем правилам приоритетности операций. Или решить задачу о четырех красках (одна из классических в сборнике Уэзерелла, если кто еще помнит). Безусловно, можно. Но я бы врагу не пожелал. Это вам не реверс цепочек.
Записан
grozny
Гость
« Ответ #37 : 20-11-2003 02:03 » 

Цитата

Мизерная такая вариация граничных условий, на каких-то жалких 6 порядков

Не, неверная аналогия. Главная задача у авто - ездить, а не груз выдерживать. И вариация граничных условий - проехать километр опытному образцу или триста тыщ серийному - вполне реальна.

Возьмём берцовую кость человека - она выдерживает до 2-3 тонн, хотя в реальной жизни нагрузка не превышает пары сотен кг.

Так что сильная вариация (3-6-20 порядков) прямых входных параметров всегда имеет смысл и должна учитываться. Тем более, что альтернативный рекурсии метод масштабируется намного луче.

Тем не менее, экстремизм - вредная вещь. Рекурсия, как и goto, должна быть в арсенале любого программиста - бесспорно. Можно жить и без того и без другого, но зачем ограничивать? Важно понимать, чем ты рискуешь (стабильностью продукта) и что теряешь (масштабируемость), применяя рекурсию.

на том и порешим.  Отлично

На ЛИСПе (или Прологе) можно написать *всё* и программа для машины Тьюринга представима рекурсией *всегда*.

Да вот только маловато людей, способных написать мало-мальски сложные рекурсивные программы. Спроси хотя бы у японцев, как они на Прологе писали софт для компьютера 5-го поколения. Мозги у людей того, не рекурсивные, глубина стэка очень маленькая Отлично
Записан
Страниц: 1 [2]  Все   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines