Форум программистов, компьютерный форум CyberForum.ru

Можно ли на С++ как-то свернуть стек для выхода из рекурсии, а не последовательно выходить из нее? - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 01:14     Можно ли на С++ как-то свернуть стек для выхода из рекурсии, а не последовательно выходить из нее? #1
Вот такой пример кода:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
QuickSort::QuickSort(void)
{
    deeps = 0;
    needsShuffl = false;
}
 
QuickSort::~QuickSort(void)
{
}
 
#define MAX_DEEPS 500
 
QuickSort::sort(int left, int right)
{
    deeps++;
    if(right - left <= 3)
    {
        //sort 3 elements
        deeps--;
        return;
    }
    
    if(deeps >= MAX_DEEPS)  //stack overflow
    {
        needsShuffl = true;
        return;
    }
 
    //...перестановки
    //опред. новые граници l1, l2, r2
    sort(l1, l2 - 1);
    if(needsShuffl) //!!! Хотелось бы избеать лишних проверок!
        return;
 
    sort(l2, r2);
    if(needsShuffl) //!!! Хотелось бы избеать лишних проверок!
        return;
 
    deeps--;
}
После установки needsShuffl в нужно закончить сортировку вернуться наверх.
Но как то жаба давит ради редчайшей ситуации (max_deeps == 500) такой проверкой деоптимизировать свой код.
Есть 2 хитрожопых варианта:
1. Сделать вставку на asm и запомнить смещение вначале. А потом если что с помощью второй вставки вернуться. Но помоему это ДИКО опасно.
2. Сделать delete this (о чем то таком писала Алена++) и как то передать управление другому классу контролеру. ..Хз как такое извращение сделать.
Что посоветуете?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.11.2010, 01:14     Можно ли на С++ как-то свернуть стек для выхода из рекурсии, а не последовательно выходить из нее?
Посмотрите здесь:

C++ Составить программу для подсчета набольшего количества одинаковых элементов, размещенных последовательно, в массиве для каждого одномерного массива...
C++ Класс реалз стек, для отыскания выхода из лабиринта
Как найти максимум который выходить за предел всех типов данных? C++
C++ Можно ли создать простое окно с кнопкой и свернуть его в трей?
составить программу с исп. рекурсии и без нее C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
05.11.2010, 01:42     Можно ли на С++ как-то свернуть стек для выхода из рекурсии, а не последовательно выходить из нее? #2
Ну разве что исключение кинуть. Но это не очень круто, потому что исключения, если по-хорошему, не должны управлять логикой программы.
Лучше дай стеку спокойно свернуться самостоятельно. Пятьсот проверок — это "ноль".

Кстати, даже не нужно ничего делать дополнительно. Просто условие
C++
1
if(deeps < MAX_DEEPS)
поставь в начало функции. Если оно выполняется, то можно делать сортировку, а если нет, то функция просто не выполняется.
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 01:57  [ТС]     Можно ли на С++ как-то свернуть стек для выхода из рекурсии, а не последовательно выходить из нее? #3
Наименьшее количество таких проверок (на оптимальном массиве) :

N = 2*[Сумма от i = 0 по k-1] (k - i), где k = log2(L), где L - количество элементом массива.

Добавлено через 2 минуты
Кстати, даже не нужно ничего делать дополнительно. Просто условие
C++
1
if(deeps < MAX_DEEPS)
поставь в начало функции. Если оно выполняется, то можно делать сортировку, а если нет, то функция просто не выполняется.
В том то и дело что таких проверок будет (см. придыдущий пост)
Например на массив 1024 элемента в идеале будет 110 шт.
KpeHDeJIb
 Аватар для KpeHDeJIb
56 / 56 / 3
Регистрация: 31.10.2010
Сообщений: 103
05.11.2010, 02:16     Можно ли на С++ как-то свернуть стек для выхода из рекурсии, а не последовательно выходить из нее? #4
Цитата Сообщение от Zilon Посмотреть сообщение
Но как то жаба давит ради редчайшей ситуации (max_deeps == 500) такой проверкой деоптимизировать свой код.
Да, он будет выполняться на 1 нс дольше. Чем раньше ты начнешь понимать что преждевременные оптимизации зло - тем легче тебе будет жить. Вот когда у тебя действительно будет проседать производительность вот тогда и начинай думать. И вообще надо оптимизировать не инструкции, а алгоритм, для начала выкинуть рекурсию.
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 02:35  [ТС]     Можно ли на С++ как-то свернуть стек для выхода из рекурсии, а не последовательно выходить из нее? #5
Да, он будет выполняться на 1 нс дольше.
Не на 1 н.с. а на 2*[Сумма от i = 0 по k-1] (k - i)

n*k / 2*[Сумма от i = 0 по k-1] (k - i), где k = log2(n);
Процента на 2 думаю.
И правда, не много...

Чем раньше ты начнешь понимать что преждевременные оптимизации зло - тем легче тебе будет жить.
Никто не говорит о преждевременной оптимизации. Она очень даже своевременна. Моя задача написать быструю сортировку, и все. Это не часть большого проекта.

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

Но а вцелом, светку стека на С++ как то можно сделать? delete this не подходит, только что прочитал. Можно еще exeption кинуть, но... Кто знает что там с накладными расходами на них. Да и некрасиво это.
Nick Alte
Эксперт С++
1590 / 982 / 115
Регистрация: 27.09.2009
Сообщений: 1,897
Завершенные тесты: 1
05.11.2010, 09:59     Можно ли на С++ как-то свернуть стек для выхода из рекурсии, а не последовательно выходить из нее? #6
Никто не говорит о преждевременной оптимизации. Она очень даже своевременна. Моя задача написать быструю сортировку, и все.
Даже так эта "оптимизация" преждевременна. Надо сначала написать алгоритм нормально, наиболее наглядным и очевидным образом, потом пройтись профилировщиком, и после этого уже лечить задержки там, где они действительно влияют на общий результат. А оптимизировать выбранные наугад места, не зная, насколько они влияют на производительность - пустая трата сил и времени.
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 12:56  [ТС]     Можно ли на С++ как-то свернуть стек для выхода из рекурсии, а не последовательно выходить из нее? #7
И да и нет. Вообщем то вы все правильно говорите. Но когда решаешь подобные (алгоритмические) задачи нужно в равной степени оперировать голыми формулами. Хотя, стремление к преждевременной оптимизации - это у меня есть особенно когда времени хватает.

На практике я уже забил на эту оптимизацию. Но про свертку стека все еще интересно узнать.
KpeHDeJIb
 Аватар для KpeHDeJIb
56 / 56 / 3
Регистрация: 31.10.2010
Сообщений: 103
05.11.2010, 16:18     Можно ли на С++ как-то свернуть стек для выхода из рекурсии, а не последовательно выходить из нее? #8
Цитата Сообщение от Zilon Посмотреть сообщение
На практике я уже забил на эту оптимизацию. Но про свертку стека все еще интересно узнать.
Короткий ответ - нет, но вообще можно сделать хак и вылететь из рекурсии, если знаешь текущий уровень вложенности - достаточно знания ассемблера
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 17:59  [ТС]     Можно ли на С++ как-то свернуть стек для выхода из рекурсии, а не последовательно выходить из нее? #9
Но этот хак не безопасен и не переносим, так?
KpeHDeJIb
 Аватар для KpeHDeJIb
56 / 56 / 3
Регистрация: 31.10.2010
Сообщений: 103
05.11.2010, 18:31     Можно ли на С++ как-то свернуть стек для выхода из рекурсии, а не последовательно выходить из нее? #10
Цитата Сообщение от Zilon Посмотреть сообщение
Но этот хак не безопасен и не переносим, так?
Как и большинство хаков да, нет никакой гарантии что он будет работать всегда и везде )
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 19:52  [ТС]     Можно ли на С++ как-то свернуть стек для выхода из рекурсии, а не последовательно выходить из нее? #11
Ок, с этим вопросом ясно.
KpeHDeJIb
 Аватар для KpeHDeJIb
56 / 56 / 3
Регистрация: 31.10.2010
Сообщений: 103
05.11.2010, 20:03     Можно ли на С++ как-то свернуть стек для выхода из рекурсии, а не последовательно выходить из нее? #12
Цитата Сообщение от Zilon Посмотреть сообщение
Ок, с этим вопросом ясно.
Ну и используя механизм исключений тоже можно размотать стек, но это тоже хак, только работать будет, потому что по стандарту. Впрочем можно это и не как хак использовать, если у тебя достигнут уровень рекурсии глубокий, то можно бросить эксепшен, что мол слишком глубокая рекурсия, это как раз в идеологию SEH укладывается, только разве для этого одного случая придется таскать с собой RTTI и SEH, что сильно увеличит размеры программы.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.11.2010, 22:20     Можно ли на С++ как-то свернуть стек для выхода из рекурсии, а не последовательно выходить из нее?
Еще ссылки по теме:

C++ можно ли потоку для чтения передать имеющуюся строку, что бы из нее выдрать числа при чтении
C++ Вычислить произведение сомножителей с применением рекурсии и без нее
Как мне можно консольное преложение в трей свернуть C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 22:20  [ТС]     Можно ли на С++ как-то свернуть стек для выхода из рекурсии, а не последовательно выходить из нее? #13
А как это повлияет на скорость работы? На вычисления в блоке трай налагаются какие то штрафы по времени? И к стати, когда сровится эксепшн, то что происходит со стеком?
Yandex
Объявления
05.11.2010, 22:20     Можно ли на С++ как-то свернуть стек для выхода из рекурсии, а не последовательно выходить из нее?
Ответ Создать тему
Опции темы

Текущее время: 08:43. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru