Увеличение размера стека

@Diplomate · Регистрация: 10.11.2013

Студворк — интернет-сервис помощи студентам

Нет ли какой-либо команды, которая бы "приказала" программе расширить стек, чтобы она не вылетала с ошибкой? Просто я решаю одну задачу и не представляю как сделать её без рекурсии.

@castaway · 14.11.2015, 20:00

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

@Diplomate · 14.11.2015, 20:16 **[ТС]**

Сообщение от castaway

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

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

@Kastaneda · 14.11.2015, 20:17

Только в compile-time, если решение вылетает по stack overflow значит нужно менять решение.

@castaway · 14.11.2015, 20:19

Сообщение от Diplomate

Можно ли как-то сделать это в тексте программы?

Думаю что можно.

@Diplomate · 14.11.2015, 20:35 **[ТС]**

Сообщение от Kastaneda

Только в compile-time, если решение вылетает по stack overflow значит нужно менять решение.

По-моему граф обойти в глубину можно только с помощью рекурсии или её имитации.

Сообщение от castaway

Думаю что можно.

Вот было бы неплохо узнать, как...

@castaway · 14.11.2015, 20:47

Сообщение от Diplomate

Вот было бы неплохо узнать, как...

Да. Было бы неплохо...

@Diplomate · 14.11.2015, 21:54 **[ТС]**

А что делает функция malloc? Подскажите пожалуйста, как её применить для моей задачи?

@DrOffset · 14.11.2015, 22:03

Не по теме:

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

@bizba · 14.11.2015, 22:10

Сообщение от Diplomate

А что делает функция malloc? Подскажите пожалуйста, как её применить для моей задачи?

Вот malloc как раз и поможет. С помощью malloc вы можете выделять память из кучи для своих нужд, а не из стека. Например для хранения 100 интов в куче определяем такой указатель:

C++

1	int* p = (int)malloc(100sizeof(int));

Velesthau · 14.11.2015, 22:12

https://gcc.gnu.org/wiki/SplitStacks

@Diplomate · 14.11.2015, 22:30 **[ТС]**

Сообщение от DrOffset

Не по теме:
Diplomate, выше тебе намекнули, что неплохо бы показать код, который сейчас не работает. Тогда, возможно, тебе подскажут как его переделать, чтобы ошибка переполнения стека пропала.
Без кода здесь не будет конструктива.

Я могу показать код, но смысла будет мало. Сама задача взята из региональной олимпиады 2013-2014 годов, вот её решение(самая последняя). По сути мне нужно два списка смежности(какому человеку кто подчинён) превратить в отрезки(какие "рядовые" прямо или косвенно подчиняются данному человеку, а так как они идут подряд, нам надо хранить только первого рядового и последнего). Для этого я запускаю из корневого узла функцию построения отрезка, которая в процессе работы для каждого подчинённого, имеющего своих подчинённых, запускает функцию уже для него. То есть я просто осуществляю поиск в глубину с немного расширенным функционалом. Без понятия, как можно без этого получить отрезки.
Код, кстати говоря, вроде бы рабочий, но на больших тестах программа выдаёт ошибку из-за слишком большой глубины рекурсии.

Сообщение от bizba

Вот malloc как раз и поможет. С помощью malloc вы можете выделять память из кучи для своих нужд, а не из стека. Например для хранения 100 интов в куче определяем такой указатель:
C++Выделить код
1
int* p = (int*)malloc(100*sizeof(int));

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

Добавлено через 2 минуты

Сообщение от Velesthau

https://gcc.gnu.org/wiki/SplitStacks

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

@castaway · 14.11.2015, 22:35

Сообщение от Diplomate

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

Я открою маленький секрет. Пустая болтовня тебе тоже не поможет.

@bizba · 14.11.2015, 22:59

Сообщение от Diplomate

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

Как понять для функции, для переменных функции может быть?

@castaway · 14.11.2015, 23:01

Сообщение от bizba

Как понять для функции, для переменных функции может быть?

Подразумевается стек. Память под локальные переменные.

@bizba · 14.11.2015, 23:06

Сообщение от castaway

Подразумевается стек. Память под локальные переменные.

То есть надо использовать только стековую память?

@castaway · 14.11.2015, 23:18

Сообщение от bizba

То есть надо использовать только стековую память?

Я не знаю что ему надо. А гадать не хочу.

@Diplomate · 14.11.2015, 23:56 **[ТС]**

Сообщение от castaway

Я открою маленький секрет. Пустая болтовня тебе тоже не поможет.

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

Кликните здесь для просмотра всего текста

C++

void build1(int i){ //i-номер расматриваемого человека
    int c,num2; 
    int num = j; //num-текущий отрезкок
    int min = 999999999, max = 0;
    for (c = 0; c < (int)a[i].size(); c++){ 
        if (a[a[i][c]].size() != 0){ //в каждом a[i] хранится список подчинённых данного человека
            j++;
            num2 = j;
            build1(a[i][c]);  //строим отрезок для подчинённого, у которого есть свои подчинённые
            if (min>t1[num2].first) min = t1[num2].first;
            if (max<t1[num2].second) max = t1[num2].second;
        } 
        else{
            if (min>a[i][c]) min = a[i][c];
            if (max<a[i][c]) max = a[i][c];
        }
    }
    t1[num].first = min; //t1-вектор пар, в которых хранятся концы отрезков
    t1[num].second = max;
}

Сообщение от bizba

Как понять для функции, для переменных функции может быть?

В этом деле я полный неуч, признаю. У меня вылетает программа из-за слишком глубокой рекурсии, насколько я понял. Но в функции у меня никаких массивов не объявляется, так что я не очень понимаю, что надо делать с помощью malloc. Буду очень благодарен за помощь.

@bizba · 15.11.2015, 00:10

Diplomate, а на какой строке падает программа?отладчиком не отлавливали? И можно ещё код класса для объекта a привести здесь?

@castaway · 15.11.2015, 08:34

Из расчёта: int == sizeof( void * ) == 4
Получаем:
Твой пример: 6 * 4 = 24 байта на функцию.
Мой пример: 2 * 4 = 8 байт на функцию.
Экономия 60% или 16 байт.

C++

struct build_struct {
    int c, num, num2;
    int min, max;
    build_struct( int j ) : num( j ), min( 999999999 ), max( 0 ) {}
};
 
void build1( int i ) {  // i-номер расматриваемого человека
    build_struct * p_bs = new build_struct( j );
 
    for ( p_bs->c = 0; p_bs->c < (int)a[i].size(); p_bs->c++ ) {
        if ( a[a[i][p_bs->c]].size() != 0 ) {   // в каждом a[i] хранится список подчинённых данного человека
            j++;
            p_bs->num2 = j;
            build1( a[i][p_bs->c] );    // строим отрезок для подчинённого, у которого есть свои подчинённые
            if ( p_bs->min > t1[p_bs->num2].first  ) p_bs->min = t1[p_bs->num2].first;
            if ( p_bs->max < t1[p_bs->num2].second ) p_bs->max = t1[p_bs->num2].second;
        } else {
            if ( p_bs->min > a[i][p_bs->c] ) p_bs->min = a[i][p_bs->c];
            if ( p_bs->max < a[i][p_bs->c] ) p_bs->max = a[i][p_bs->c];
        }
    }
    t1[p_bs->num].first = p_bs->min;    // t1-вектор пар, в которых хранятся концы отрезков
    t1[p_bs->num].second = p_bs->max;
 
    delete p_bs;
}

@Diplomate 1 / 1 / 0 Регистрация: 10.11.2013 Сообщений: 84
		1
	Увеличение размера стека 14.11.2015, 19:42. Показов 21865. Ответов 41 Метки нет (Все метки) Нет ли какой-либо команды, которая бы "приказала" программе расширить стек, чтобы она не вылетала с ошибкой? Просто я решаю одну задачу и не представляю как сделать её без рекурсии. 0

@castaway 4984 / 3091 / 456 Регистрация: 10.11.2010 Сообщений: 11,169 Записей в блоге: 10
	14.11.2015, 20:00	2
	Насколько мне известно, можно при компиляции задать размер стека. А вообще, в рекурсии можно обойтись минимальным размером стека. Наверняка твою программу можно улучшить. 1

@Diplomate 1 / 1 / 0 Регистрация: 10.11.2013 Сообщений: 84
	14.11.2015, 20:16 [ТС]	3
	Сообщение от castaway Насколько мне известно, можно при компиляции задать размер стека. А вообще, в рекурсии можно обойтись минимальным размером стека. Наверняка твою программу можно улучшить. Можно ли как-то сделать это в тексте программы? Я просто должен сдать код решения. Может быть как-то можно вообще без рекурсии, но улучшить мою рекурсию вряд ли можно. Все объекты(вершины графа) просматриваются только один раз. 0

@Kastaneda 5231 / 3204 / 362 Регистрация: 12.12.2009 Сообщений: 8,112 Записей в блоге: 2
	14.11.2015, 20:17	4
	Только в compile-time, если решение вылетает по stack overflow значит нужно менять решение. 2

@castaway 4984 / 3091 / 456 Регистрация: 10.11.2010 Сообщений: 11,169 Записей в блоге: 10
	14.11.2015, 20:19	5
	Сообщение от Diplomate Можно ли как-то сделать это в тексте программы? Думаю что можно. 1

@Diplomate 1 / 1 / 0 Регистрация: 10.11.2013 Сообщений: 84
	14.11.2015, 20:35 [ТС]	6
	Сообщение от Kastaneda Только в compile-time, если решение вылетает по stack overflow значит нужно менять решение. По-моему граф обойти в глубину можно только с помощью рекурсии или её имитации. Сообщение от castaway Думаю что можно. Вот было бы неплохо узнать, как... 0

@castaway 4984 / 3091 / 456 Регистрация: 10.11.2010 Сообщений: 11,169 Записей в блоге: 10
	14.11.2015, 20:47	7
	Сообщение от Diplomate Вот было бы неплохо узнать, как... Да. Было бы неплохо... 0

@Diplomate 1 / 1 / 0 Регистрация: 10.11.2013 Сообщений: 84
	14.11.2015, 21:54 [ТС]	8
	А что делает функция malloc? Подскажите пожалуйста, как её применить для моей задачи? 0

@DrOffset
	14.11.2015, 22:03 #9
	Не по теме: Diplomate, выше тебе намекнули, что неплохо бы показать код, который сейчас не работает. Тогда, возможно, тебе подскажут как его переделать, чтобы ошибка переполнения стека пропала. Без кода здесь не будет конструктива. 0

Velesthau 528 / 431 / 159 Регистрация: 25.11.2014 Сообщений: 1,662
	14.11.2015, 22:12	11
	https://gcc.gnu.org/wiki/SplitStacks 0

	15.11.2015, 08:34

@Diplomate 1 / 1 / 0 Регистрация: 10.11.2013 Сообщений: 84
	14.11.2015, 22:30 [ТС]	12
	Сообщение от DrOffset Не по теме: Diplomate, выше тебе намекнули, что неплохо бы показать код, который сейчас не работает. Тогда, возможно, тебе подскажут как его переделать, чтобы ошибка переполнения стека пропала. Без кода здесь не будет конструктива. Я могу показать код, но смысла будет мало. Сама задача взята из региональной олимпиады 2013-2014 годов, вот её решение(самая последняя). По сути мне нужно два списка смежности(какому человеку кто подчинён) превратить в отрезки(какие "рядовые" прямо или косвенно подчиняются данному человеку, а так как они идут подряд, нам надо хранить только первого рядового и последнего). Для этого я запускаю из корневого узла функцию построения отрезка, которая в процессе работы для каждого подчинённого, имеющего своих подчинённых, запускает функцию уже для него. То есть я просто осуществляю поиск в глубину с немного расширенным функционалом. Без понятия, как можно без этого получить отрезки. Код, кстати говоря, вроде бы рабочий, но на больших тестах программа выдаёт ошибку из-за слишком большой глубины рекурсии. Сообщение от bizba Вот malloc как раз и поможет. С помощью malloc вы можете выделять память из кучи для своих нужд, а не из стека. Например для хранения 100 интов в куче определяем такой указатель: C++Выделить код 1 int* p = (int)malloc(100sizeof(int)); А если мне надо память для функции выделить, что делать? Не совсем понимаю этот момент... Добавлено через 2 минуты Сообщение от Velesthau https://gcc.gnu.org/wiki/SplitStacks Проблема в том, что я сдаю код программы, а не экзешник, так что манипуляции с компилятором мне не помогут. 0

@castaway 4984 / 3091 / 456 Регистрация: 10.11.2010 Сообщений: 11,169 Записей в блоге: 10
	14.11.2015, 22:35	13
	Сообщение от Diplomate Проблема в том, что я сдаю код программы, а не экзешник, так что манипуляции с компилятором мне не помогут. Я открою маленький секрет. Пустая болтовня тебе тоже не поможет. 1

@bizba 6 / 6 / 4 Регистрация: 29.10.2015 Сообщений: 45
	14.11.2015, 22:59	14
	Сообщение от Diplomate А если мне надо память для функции выделить, что делать? Не совсем понимаю этот момент... Как понять для функции, для переменных функции может быть? 0

@castaway 4984 / 3091 / 456 Регистрация: 10.11.2010 Сообщений: 11,169 Записей в блоге: 10
	14.11.2015, 23:01	15
	Сообщение от bizba Как понять для функции, для переменных функции может быть? Подразумевается стек. Память под локальные переменные. 0

@bizba 6 / 6 / 4 Регистрация: 29.10.2015 Сообщений: 45
	14.11.2015, 23:06	16
	Сообщение от castaway Подразумевается стек. Память под локальные переменные. То есть надо использовать только стековую память? 0

@castaway 4984 / 3091 / 456 Регистрация: 10.11.2010 Сообщений: 11,169 Записей в блоге: 10
	14.11.2015, 23:18	17
	Сообщение от bizba То есть надо использовать только стековую память? Я не знаю что ему надо. А гадать не хочу. 0

@bizba 6 / 6 / 4 Регистрация: 29.10.2015 Сообщений: 45
	15.11.2015, 00:10	19
	Diplomate, а на какой строке падает программа?отладчиком не отлавливали? И можно ещё код класса для объекта a привести здесь? 0