[ /b/ /u/ /rf/ /dt/ /vg/ /r/ /cr/ /lor/ /mu/ /oe/ /s/ /w/ /hr/ ] [ /a/ /ma/ /sw/ /hau/ /azu/ ] [ /tv/ /cp/ /gf/ /bo/ /di/ /vn/ /ve/ /wh/ /fur/ /to/ /bg/ /wn/ /slow/ /mad/ ] [ /d/ /news/ ] [ Главная | Настройки | Закладки | Плеер ]

Ответ в тред 47631. [Назад]
 [ Скрыть форму ]
Имя
Не поднимать тред 
Тема
Сообщение
Капча Капча
Пароль
Файл
Вернуться к
  • Публикация сообщения означает согласие с условиями предоставления сервиса
  • В сообщениях можно использовать разметку wakabamark
  • На данной доске отображаются исходные имена файлов!
  • Разрешенные типы файлов: pdf, code, flash, video, text, archive, image, vector, music
  • Тред перестает подниматься после 500 сообщений.
  • Треды с числом ответов более 100 не могут быть удалены.
  • Старые треды перемещаются в архив после 40 страницы.

No.47631 Ответ
Файл: Microsoft-VBA-Large[1].png
Png, 49.28 KB, 850×255 - Нажмите на картинку для увеличения
edit Find source with google Find source with iqdb
Microsoft-VBA-Large[1].png
Раз нет такого треда, то он будет здесь.
Написал быструю сортировку (с рекурсией) на VBA в excel (x32). При достаточно большом размере массива появляется ошибка переполнения стека. Переписал сортировку без рекурсии (сделал динамический массив-имитатор стека, в который записывались номера двух граничных элементов для следующих шагов рекурсии). Алгоритм не только стал работать быстрее, но и переполнения стека уже не возникает.
А теперь вопросы. Почему стек ограничен и при его переполнении он не расширяется на свободную память, которая, как свидетельствует работающий нерекурсивный алгоритм, имеется. Если такое ограничение стека есть не только в VBA, но и много где ещё, почему всё же люди используют рекурсию, а не её имитацию, хотя бы в том же виде, как сделал я?
>> No.47634 Ответ
Файл: Dichotomous_Exponentiation.png
Png, 70.50 KB, 722×656 - Нажмите на картинку для увеличения
edit Find source with google Find source with iqdb
Dichotomous_Exponentiation.png
Технических ограничений на современных операционных системах нет. Стек расширяется автоматически, пока не упрётся в ограничение сверху, что породит исключительную ситуацию, которую можно по-умному обработать, поскольку срыв не приводит к порче других данных. Ограничение размера — это своего рода способ отлова явных или неявных бесконечных рекурсий, к тому же при явно заданном ограничении появляется возможность гарантированного выделения памяти, что предотвращает ситуацию, когда куча сожрала всю память и стеку некуда расти.
Люди используют рекурсию потому, что её используют математики, помимо прочего доказывающие корректность предложенного решения. На практике это означает «Просто перепиши формулу из учебника — её автором уже доказана её корректность.» Корректность итеративного алгоритма придётся доказывать самостоятельно, не все это могут. Далее, итеративные алгоритмы сложнее в реализации. Я года три-четыре назад читал бложег начинающего питониста, там были восторги от рекурсий и фраза, мол, последовательность операций — это слишком сложно. С трудом представляю, как он ссать ходит — там же последовательность операций надо выполнить: ширинку расстегнуть, хер достать.... Т.е. кому-то даже это сложно. Далее, не все понимают, как работает компьютер... ну, знаешь, как медведь в цирке на велосипеде ездит? У него нет понимания, что он делает и зачем.
>> No.47637 Ответ
>>47631
> почему всё же люди используют рекурсию
Дерево каталогов удобнее обходить с помощью рекурсии.
А быструю сортировку — пиши как хочешь, самая первая версия (которую Хоар придумал) была без.


Пароль:

[ /b/ /u/ /rf/ /dt/ /vg/ /r/ /cr/ /lor/ /mu/ /oe/ /s/ /w/ /hr/ ] [ /a/ /ma/ /sw/ /hau/ /azu/ ] [ /tv/ /cp/ /gf/ /bo/ /di/ /vn/ /ve/ /wh/ /fur/ /to/ /bg/ /wn/ /slow/ /mad/ ] [ /d/ /news/ ] [ Главная | Настройки | Закладки | Плеер ]