Как проверить использование стека при расчете Аккермана - PullRequest
Новая
       50

Как проверить использование стека при расчете Аккермана

2 голосов
/ 27 сентября 2011

Я узнаю о способности моей системы вычислять алгоритм Аккермана как с двумя, так и с тремя параметрами. Для очень малых значений m и n моя система рассчитает и напечатает результаты, возвращаемые из вызовов методов A0 и A1. Однако все, что выше 3 или 4, не возвращается и замораживает терминал, которым я пользуюсь. Моя проблема в том, что я определяю, для каких значений m и n моя машина может вычислить.

Я попытался несколько вещей, чтобы поймать переполнение стека, для всех я знаю, что C ++ не имеет исключения стека переполнения, которое я могу поймать. блоки try-catch не работают. В приведенном ниже коде я использую getrlimit (), чтобы найти ограничение стека, создать местоположение адреса в основном gStackRef. Я вызываю checkStack, рекурсивно проверяя указатель локальной переменной на gStackLimit.

Есть ли лучший способ проверить использование моего стека относительно рекурсивных методов? Также я проверяю наличие ошибок сегмента? Я дам вам знать, что я работаю на терминале Unix. 

#include <cstdlib>
#include <iostream>


#define _XOPEN_SOURCE_EXTENDED 1
#include <sys/resource.h>

int getrlimit(int resource, struct rlimit *rlp);

using namespace std;

int * gStackRef;
int gStackLimit;

void checkStack(void);

int main(int argc, char *argv[])
{
        int temp = 0;
        gStackRef = &temp;
        rlimit myl;
        getrlimit(RLIMIT_STACK, &myl);
        gStackLimit = (myl.rlim_cur / 3 * 8 / 10) ;/* modified for segment fault */
        cout << gStackLimit << "\n";
        checkStack();
}

void checkStack()
{
        int temp = 0;
        int* pVariableHere = &temp;
        size_t stackUsage = gStackRef - pVariableHere;
        printf("Stack usage: %d / %d \n", stackUsage, gStackLimit);
        if(stackUsage > gStackLimit) return;
        else checkStack();
}

Ответы [ 2 ]

2 голосов
/ 27 сентября 2011

Однако все, что выше 3 или 4, не возвращается и замораживает терминал, которым я пользуюсь atm.

Это своего рода точка функции Аккермана. Растет чрезвычайно быстро. Для m >= 4 и n >= 3, если вы вычисляете A(m, n) рекурсивно, я сомневаюсь, что ваша функция вернется до вашей смерти.

Я попытался несколько вещей, чтобы поймать переполнение стека, для всех, что я знаю, C ++ не имеет исключения стека переполнения, которое я могу поймать.

Конечно нет. Процесс находится вне пространства стека. Должен быть снесен немедленно.

Есть ли лучший способ проверить использование моего стека относительно рекурсивных методов?

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

Но, в конце концов, вам все равно не следует использовать рекурсию для вычисления Аккермана.

0 голосов
/ 27 сентября 2011

Я попытался несколько вещей, чтобы поймать переполнение стека, для всего, что я знаю, C ++ не имеет исключения стека переполнения, которое я могу поймать. блоки try-catch не работают. В приведенном ниже коде я использую getrlimit (), чтобы найти ограничение стека, создать местоположение адреса в основном gStackRef. Я вызываю checkStack, рекурсивно проверяя указатель локальной переменной на gStackLimit.

POSIX не имеет "безопасного" способа обнаружения переполнения стека. Переполнение стека приводит к SIGSEGV сигналам, которые вы (как правило) не должны перехватывать, поскольку они также указывают на общие ошибки сегментации, , которые должны вызвать сбой вашей программы . Среды Windows могут безопасно справляться с переполнением стека, используя EXCEPTION_STACK_OVERFLOW - но в таких случаях Windows просто помещает защитную страницу в конец стека и уведомляет с помощью SEH. Если вы используете защитную страницу (после игнорирования исключения SEH), то ваша программа завершает свою работу (так же, как в POSIX-стране).

Есть ли лучший способ проверить использование моего стека относительно рекурсивных методов? Также я проверяю наличие ошибок сегмента? Я дам вам знать, что я работаю на Unix-терминале.

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

Если вы хотите вычислить Ackermann безопасным для стека способом, либо используйте явную структуру стека, выделенную из кучи, либо используйте динамическое программирование .

...