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

Создать отдельный стек для функции - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.79
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
29.11.2011, 22:26     Создать отдельный стек для функции #1
необходимо. Мне надо вызывать рекурсивную функцию; при этом происходит переполнение стека, мне бы хотелось бы это контролировать.
g++ не поддерживает обработку SEH- исключений, отловить переполнение стека, как, впрочем и другие я не могу. Программа падает просто и всё.
вызов рекурсивной функции в отдельном потоке с созданным и, как следствие, контролируемым стеком (билиотека pthread) рассамтриваю только в качестве ПОСЛЕДНЕГО варианта.

Спасибо, кто откликнется

Добавлено через 48 минут
Только что в отладчике OllyDbg исполоьзовал такой приём: выделял объём памяти и вручную менял регистр ESP, чтобы он указывал на эту память и всё получалось, эта память работала как стек.
Попробую такую идею замутить с аммесблерными вставками, они нужны будут для изменения ESP, если чё, отпишусь.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.11.2011, 22:26     Создать отдельный стек для функции
Посмотрите здесь:

Создать стек. выручайте!!!!! C++
C++ при работе рекурсивной функции заканчивается стек и программа соответственно; как сделать так, чтобы она писала "стек закончился"?
C++ Создать стек для символов. Максимальный размер стека вводится с экрана. Создать функции для ввода и вывода элементов стека. Ввести эталонный символ.
C++ C++, создать стек
C++ создать стек для с++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
30.11.2011, 17:32  [ТС]     Создать отдельный стек для функции #21
Цитата Сообщение от Nameless One Посмотреть сообщение
он делает именно то, что у тебя по ссылке описано в теореме 3.
Он спотыкается на данных c_n_k(40, 19)

Цитата Сообщение от Nameless One Посмотреть сообщение
Кстати, это прекрасно видно из самого кода
просто у меня недостаточно высокая квалификация, чтобы не спросить об этом.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
30.11.2011, 18:04     Создать отдельный стек для функции #22
Цитата Сообщение от kravam Посмотреть сообщение
Он спотыкается на данных c_n_k(40, 19)
это связано с неточностью представления чисел с плавающей точкой и погрешностями при делении. Сам алгоритм правилен. Если хочешь, создай тип данных "рациональная дробь" и используй его при делении (опционально, используй длинные числа, если хочешь работать с большими значениями), и будет тебе *абсолютная* точность. Ну или просто используй тот язык, в котором все это есть

Цитата Сообщение от kravam Посмотреть сообщение
просто у меня недостаточно высокая квалификация, чтобы не спросить об этом.
попробуй расписать сам цикл на бумажке, я думаю, все прояснится

Добавлено через 17 минут
Цитата Сообщение от Nameless One Посмотреть сообщение
Ну или просто используй тот язык, в котором все это есть
дабы не быть голословным, вот реализация именно этого алгоритма на хацкеле:
Код
import Data.Ratio ((%))

c :: Integral a => a -> a -> Integer
c n k = round $ product $ map (\i -> (n - k + i) % i) [1..k]
вычисление http://www.cyberforum.ru/cgi-bin/latex.cgi?C^{19}_{40}:
Код
> c 40 19
131282408400
ответ можно проверить на любом онлайн-калькуляторе, например, здесь: http://integraloff.net/TepBep/cnk.php
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
30.11.2011, 18:33  [ТС]     Создать отдельный стек для функции #23
Цитата Сообщение от Nameless One Посмотреть сообщение
это связано с неточностью представления чисел с плавающей точкой и погрешностями при делении.
Именно это мне и не нравится и я знаю чё надо делать и я уже так делаю. Я использую класс VERYLONG

Но даже если бы у меня не было такого класса, я бы не стал писать такой код. Я понимаю, мои соображения никому не интересны, но всё же: да, базара нет, придираться к тому, что результат получается очень большим и как следствие, некорректным, это значит быть ниже пояса. Но надпись-то какую-никакую предупреждающую можно было вывести? Не знаю, чё автор хотел этим алгоритмом сказать. Мне кажется, это тот случай, когда этот простой, в общем-то алгорим нуждается в непростой и некрасивой обёртке. В частности, убрать КУДА ПОДАЛЬШЕ тип double и обеспечить абсолютную точность.

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

+++++++++++++++++++++++++++++++++++++++++++++++++

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

C++
1
2
3
4
5
6
7
8
9
10
0   1   2
0   1   3
0   1   4
0   2   3
0   2   4
0   3   4
1   2   3
1   2   4
1   3   4
2   3   4
таки дела
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
30.11.2011, 19:14     Создать отдельный стек для функции #24
Цитата Сообщение от kravam Посмотреть сообщение
Он спотыкается на данных c_n_k(40, 19)
double возвращается правильный
во всяком случае на программу

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
static int round_value(double value)
{
   double val = floor (value + 0.5); 
   printf ("%f\n", val);
   return int(val);
}
 
unsigned c_n_k (unsigned n, unsigned k)
{
   double val = 1.;
   unsigned i;
 
   for (i=1;i<=k;++i)
   {
      val *= 1. * (n - k + i) / i;
   }
   printf ("%f\n", val); 
 
   return (unsigned)round_value (val);
}
 
int main()
{
   unsigned n = 40, k = 19;
   printf ("(%u, %u) = %u", n, k, c_n_k(n, k));
   return 0;
}
Bash
1
2
3
131282408400.000000
131282408400.000000
(40, 19) = 2147483648
131282408400 совпадает с тем, что дает
http://joemath.com/math124/Calculator/factorial.htm
http://www.calculatorpro.com/combination-calculator/

просто для int'a мантисса переполняется
а погрешности с double вообще практически нету
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
01.12.2011, 03:59     Создать отдельный стек для функции #25
Цитата Сообщение от kravam Посмотреть сообщение
а в выводе сочетаний, например из пяти по 3 без возвращения и без учёта порядка
а раньше об этом сказать нельзя было?
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
01.12.2011, 11:15  [ТС]     Создать отдельный стек для функции #26
Конечно, если бы я сказал об этом раньше это было бы хорошо. Но:
Цитата Сообщение от alex_x_x Посмотреть сообщение
я ж понимаю вот это нужно
и код

НУ если человек понимает... Ну вот, тут-то и хорошо было бы его поправить, но я не мог не оставить без внимания код. Если бы я сделал и то, и другое, разговор распараллелился бы. Ну его. Надо быть последовательным. Сперва одно, потом другое.
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
01.12.2011, 11:37     Создать отдельный стек для функции #27
kravam, я вам сильно сочуствую, но все же вам нужен был отдельных стек для этого?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <algorithm>
 
int main () {
  int values[] = {1,2,3,4,5,6};
  const size_t size = sizeof(values) / sizeof(values[0]);
 
  do 
  {
     for (size_t i=0;i<size;++i)
     {
        std::cout << values[i] << ' ';
     }
     std::cout << std::endl;
  } 
  while (std::next_permutation(values,values+size));
 
  return 0;
}
http://codepad.org/8ScVK23h
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
01.12.2011, 13:00  [ТС]     Создать отдельный стек для функции #28
Нет стек мне нужен был не для этого.
И знаете, я написал для чего нужен стек:
"Рекурсия у меня применяется не в нахождении суммы, а в выводе сочетаний, например из пяти по 3 без возвращения и без учёта порядка."
Мы же видим просто количество перестановок.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Такое впечатление, что своё гоняет просто. Второй раз за тему.

Добавлено через 1 минуту
Nameless One, у меня тут не полигон для демонстрации кодов.
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
01.12.2011, 13:43     Создать отдельный стек для функции #29
Цитата Сообщение от kravam Посмотреть сообщение
И знаете, я написал для чего нужен стек:
да не нужен для этого "отдельный стек"! Вот держи:
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
41
42
43
44
45
46
47
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
 
bool next_combination (std::vector<int>& a, int k)
{
    int n = (int)a.size();
    for (int i=k-1; i>=0; --i)
    {
    if (a[i] < n-k+i)
    {
        ++a[i];
        for (int j=i+1; j<k; ++j)
        a[j] = a[j-1]+1;
        return true;
    }
    }
    
    return false;
}
 
void dump(const std::vector<int>& v, size_t k)
{
    std::copy(v.begin(), v.begin() + k, std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
}
 
int main()
{
    std::vector<int> ivec = {0, 1, 2, 3, 4};
 
    size_t k = 3;
 
    size_t cnt = 0;
 
    do
    {
    dump(ivec, k);
    ++cnt;
    }
    while(next_combination(ivec, k));
    
    std::cout << std::endl << "Count = " << cnt << std::endl;
    
    return 0;
}
Результат работы:
Код
0 1 2 
0 1 3 
0 1 4 
0 2 3 
0 2 4 
0 3 4 
1 2 3 
1 2 4 
1 3 4 
2 3 4 

Count = 10
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
01.12.2011, 13:47     Создать отдельный стек для функции #30
Nameless One, не рушь его иллюзии
стек нужен, с ассемблерными вставками
Nameless One
01.12.2011, 13:58
  #31

Не по теме:

Цитата Сообщение от alex_x_x Посмотреть сообщение
с ассемблерными вставками
чем бы дитя не тешилось, лишь бы не пыталось делать такое

kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
01.12.2011, 15:44  [ТС]     Создать отдельный стек для функции #32
Цитата Сообщение от Nameless One Посмотреть сообщение
да не нужен для этого "отдельный стек"! Вот держи:

Так и мне не нужен! Вы читайте внимателльно, вы же не читаете тему. И код мне ваш без надобности, чай у меня свой есть и мой покомпактнее будет.
C++
1
Другое дело, что глубина рекурсии невысока, поэтому вряд ли стек переполнится.
Вы даже не спросили, какая глубина рекурсии. Потому, что вам всё равно, вам просто надо код выложить сюда. Вам чё, коды негде демонстрировать свои?

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Так вот, докладываю, если я вывожу сочетавния из m по n, у меня глубина рекурсии n. Считаем: каждая функция принимает пять параметров, плюс адрес возврата плюс ещё какая-нибудь херь, максимум ячеек 10, каждая занимает 4 байта, итого 40 ячеек. На одну функцию.
Переполнится стек. если я буду применять рекурсию? А прикинем

Предположим, ввыводим сочетания из 30 по 15 (ибо 30/2== 15, наибольшее количество вариантов). Так вот, по моим подсчётам, это займёт три года. Примерно, конечно. Я выводил эти значения на экран и перикидывал в меньшую (то есть невыгодну для меня сторону) как часто меняется одно из полей... Проверяйте, в общем

Если будем брать ещё большие значения,например из 32 по 16, то это уже 30 лет

Так, а глубина рекурсии составит всего 16*40= 640 байт при том, что стандартный стек 22E000 байт.

То есть стандарнтый стек windows, он не то, что не переполнится. Он в ПРИНЦИПЕ не переполнется.
Плюс код такой аккуратный. Ну это ладно, каждый кулик своё болото хвалит

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Вопрос: а на фига тогда мне сдался этот отдельный стек?
Ответ: компактный безопасный я не умею писать сразу, так вот в процессе тык скыть написания кода у меня частенько переполняется стек. Вот отдельный стек мне нужен для процесса тык скыть написания программ. Это основное. Понимаете, для отладки. А для готового кода мне отдельный стек без надобности.
Я, конечно, мог это написать в первом сообщении но смысл? Тем более, челу и так всё понятно чё мне надо.

Вы меня можете спросить, а чем тебя стандартный-то стек не устраивает, ведь вновь созданный точно также переполнится (хоть в процессе отладки, хоть как)?
Отвечаю: переполниться-то он переполнгится, но я хочу сделать так, чтобы вывести предупреждающее сообщение. А так как у меня компилятор g++, он напрось не ловит системные исключения, то есть абсолютно. И переполнение вновь созданного стека я хотел отслеживать вручную

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
01.12.2011, 18:28     Создать отдельный стек для функции #33
Цитата Сообщение от kravam Посмотреть сообщение
Потому, что вам всё равно, вам просто надо код выложить сюда. Вам чё, коды негде демонстрировать свои?
ну не ты ли говорил, что твою функцию нельзя заменить на рекурсивную? А мы просто опровергали твое утверждение. А лучшим аргументом, естественно, является работающий код
Цитата Сообщение от kravam Посмотреть сообщение
Вы меня можете спросить, а чем тебя стандартный-то стек не устраивает, ведь вновь созданный точно также переполнится (хоть в процессе отладки, хоть как)?
Отвечаю: переполниться-то он переполнгится, но я хочу сделать так, чтобы вывести предупреждающее сообщение. А так как у меня компилятор g++, он напрось не ловит системные исключения, то есть абсолютно. И переполнение вновь созданного стека я хотел отслеживать вручную
система какая? Если *nix, то valgrind вроде бы умеет ловить переполнение стека. В принципе, его (переполнение) можно и в отладчике увидеть, если внимательно посмотреть на бэктрейс.
Также посмотри в сторону ключей -fstack-check и -fstack-protector, может что полезного нагуглишь.
А твое решение с собственным стеком (ИМХО) выглядит слишком костыльно.
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
01.12.2011, 23:12  [ТС]     Создать отдельный стек для функции #34
Цитата Сообщение от Nameless One Посмотреть сообщение
ну не ты ли говорил, что твою функцию нельзя заменить на рекурсивную? А мы просто опровергали твое утверждение. А лучшим аргументом, естественно, является работающий код
а ну тогда прошу прощения.

Добавлено через 3 часа 36 минут
Nameless One, а вообще извольте прояснить ситуацию с этим кодом:
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <stdio.h>
using namespace std;
 
 
bool next_combination (std::vector<int>& a, int k)
{
    int n = (int)a.size();
    for (int i=k-1; i>=0; --i)
    {
        if (a[i] < n-k+i)
        {
            ++a[i];
            for (int j=i+1; j<k; ++j)
                a[j] = a[j-1]+1;
            return true;
        }
    }
    
    return false;
}
 
void dump(const std::vector<int>& v, size_t k)
{
    std::copy(v.begin(), v.begin() + k, std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
}
 
int main()
{
    std::vector<int> ivec;
    ivec.push_back (0);
    ivec.push_back (1);
    ivec.push_back (3);
    ivec.push_back (4);
    ivec.push_back (5);
    ivec.push_back (6);
    ivec.push_back (7);
 
    size_t k = 3;
 
    size_t cnt = 0;
 
    do
    {
        dump(ivec, k);
        ++cnt;
    }
    while(next_combination(ivec, k));
    
    std::cout << std::endl << "Count = " << cnt << std::endl;
    getchar ();
    
    return 0;
}
Это ваш код. Только я вектор по-своему заполнил. В векторе-результате появилась двойка. Прошу вас!
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
02.12.2011, 04:19     Создать отдельный стек для функции #35
kravam, ограничение данного алгоритма в том, что исходный вектор должен представлять первые n натуральных чисел (с нулем), т.е. {0, 1, 2, ..., n - 1}. Но это ограничение легко обойти, если ввести дополнительный вектор. Причем изменить нужно будет только функцию dump
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
02.12.2011, 11:36  [ТС]     Создать отдельный стек для функции #36
я бы обязательно предупредил, а вдруг бы я взялся его использовать?!
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
02.12.2011, 11:51     Создать отдельный стек для функции #37
Цитата Сообщение от kravam Посмотреть сообщение
То есть стандарнтый стек windows, он не то, что не переполнится. Он в ПРИНЦИПЕ не переполнется.
При условии, что у тебя нет бесконечной рекурсии...

Добавлено через 2 минуты
Как сделать чтоб не рухалась: Добавляешь счётчик глубины рекурсии. статическая переменная, которая увеличивается при входе и уменьшается при выходе из рекурсивной функции. Глубину рекурсии ты примерно знаешь, поэтому проверяешь значение счётчика и выкидываешь исключение при необходимости.
4 страницы галимотьи читать не стал, если это уже было написано - извиняюсь.
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
02.12.2011, 12:30  [ТС]     Создать отдельный стек для функции #38
Цитата Сообщение от Deviaphan Посмотреть сообщение
Как сделать чтоб не рухалась: Добавляешь счётчик глубины рекурсии.
Я этот способ рассматриваю и имею ввиду, но дело в том, что при отладке установить глубину рекурсии- это дорогого стоит. Это я щас по готовому продукту могу определить глубину рекурсии. А в процессе его изготовления- нет.
Хотя способ, несомненно хорош ДАЖЕ В ПРОЦЕССЕ НАПИСАНИЯ ПРОГРАММЫ, но привязываться итогда придётся к верхушке стека, к регистру ESP и размеру стека. Троудоёмко довольно.

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Но даже и в этом случае вот какая есть сложность (но ты не принимай на своё счёт, это ведь и моя идея, просто неозвученная): Дело в том, по каждому вызову функции этот счётчик должен увеличиваться на величину (кадр стека?), равную тому, что занимают локальные даные рекурсивной функции. Допустим, примерно я это количество найду и накину пару тройку для надёжности байт.

Но если алгоритм построен так, что рекурсивная функция вызывает не только себя, а какую-нибудь другую функцию, нерекурсивную? А если ещё и вызывает по некоторому условию? А если и в цикле?

Так что к сожалению этот счётчик должен увеличиваться на чёрт его знает какое значение байт.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
02.12.2011, 12:38     Создать отдельный стек для функции #39
Цитата Сообщение от kravam Посмотреть сообщение
каждому вызову функции этот счётчик должен увеличиваться на величину
На единицу. ++ на входе и -- перед выходом.
Точное максимальное значение не обязательно. Примерную сложность алгоритма всегда можно оценить. Если навскидку у тебя глубина 20 вызовов, поставь счётчик на 1000. Или на 100.
Предполагать, сколько переменные займут в стеке - бесполезно. Есть выравнивание, есть "перетусовывание" компилятором. Кое что вообще в стек не попадает. В дебаге добавляется "неизвестное" количество дополнительных данных для контроля повреждений стека.
Счётчик считает глубину. Всё. +1 и -1.
Я даже на "бесконечных" циклах счётчик использую иногда.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.12.2011, 12:55     Создать отдельный стек для функции
Еще ссылки по теме:

Создать отдельный управляемый поток для бесконечного процесса C++
C++ Создать стек
C++ Функции в отдельный файл

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

Или воспользуйтесь поиском по форуму:
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
02.12.2011, 12:55  [ТС]     Создать отдельный стек для функции #40
Ну ясно всё, неубедительно. Я уже говорил у меня очень низкая квалификация для некоторых вещей. В частности, я не возьмусь определять глубину стека до определённого момента ни примерно, никак. Такой момент наступает, как правило, когда прога готова.

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

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

Жизнь вообще сложная штука.
Yandex
Объявления
02.12.2011, 12:55     Создать отдельный стек для функции
Ответ Создать тему
Опции темы

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