Я хочу сделать DFS в массиве 100 X 100. (Скажем, элементы массива представляют узлы графа). Таким образом, если предположить наихудший случай, то глубина рекурсивных вызовов функций может достигать 10000 при каждом вызове, принимающем до 20 байтов. Так что это возможно, есть ли возможность stackoverflow?
Каков максимальный размер стека в C/С++?
Пожалуйста, укажите для gcc для обоих
1) cygwin на Windows
2) Unix
Каковы общие ограничения?
В Visual Studio размер стека по умолчанию составляет 1 МБ, я думаю, поэтому с глубиной рекурсии 10 000 каждый кадр стека может быть не более ~ 100 байт, что должно быть достаточным для алгоритма DFS.
Большинство компиляторов, включая Visual Studio, позволяют указать размер стека. На некоторых (все?) Linux вкусах размер стека не является частью исполняемого файла, а переменной среды в ОС. Затем вы можете проверить размер стека с помощью ulimit -s и установить его на новое значение, например, ulimit -s 16384.
Здесь ссылка с размерами стека по умолчанию для gcc.
DFS без рекурсии:
std::stack<Node> dfs;
dfs.push(start);
do {
Node top = dfs.top();
if (top is what we are looking for) {
break;
}
dfs.pop();
for (outgoing nodes from top) {
dfs.push(outgoing node);
}
} while (!dfs.empty())
стеки для потоков часто меньше. Вы можете изменить значение по умолчанию во время соединения, или изменить во время выполнения. Для справки некоторые значения по умолчанию:
зависящий от платформы, зависящий от привязки, зависящий от ulimit, зависящий от параметра.... Он совсем не указан, и на него могут воздействовать многие статические и динамические свойства.
Да, существует возможность. Стандарты C и С++ не диктуют такие вещи, как глубина стека, обычно это проблема с окружающей средой.
Большинство достойных сред разработки и/или операционных систем позволят вам адаптировать размер стека к процессу либо по ссылке, либо по времени загрузки.
Вы должны указать, какую ОС и среду разработки вы используете для более целенаправленной помощи.
Например, в Ubuntu Karmic Koala по умолчанию для gcc зарезервировано 2M и 4K, но это можно изменить, когда вы связываете программу. Используйте --stack вариант ld для этого.
Я не уверен, что вы подразумеваете, делая первый поиск глубины в прямоугольном массиве, но я предполагаю, что вы знаете, что делаете.
Если предел стека является проблемой, вы должны иметь возможность преобразовать свое рекурсивное решение в итеративное решение, которое подталкивает промежуточные значения в стек, который выделяется из кучи.
У меня просто закончилась работа на стеке, это была база данных, и на ней были потоки, в основном предыдущий разработчик бросил большой массив в стек, и в любом случае стек был низким. Программное обеспечение было скомпилировано с использованием Microsoft Visual Studio 2015.
Несмотря на то, что в потоке закончилась стека, он молчал и продолжался, но только стек переполнялся, когда приходил доступ к содержимому данных в стеке.
Лучший совет, который я могу дать, - не объявлять массивы в стеке, особенно в сложных приложениях и особенно в потоках, вместо этого используйте кучу. Что это там за;)
Также имейте в виду, что это может не сработать сразу после объявления стека, но только при доступе. Я предполагаю, что компилятор объявляет стек под "оптимистично", т.е. Предположим, что стек объявлен и имеет достаточный размер до тех пор, пока он не начнет его использовать, а затем выяснит, что стек не существует.
В разных операционных системах могут быть разные политики декларации стека. Пожалуйста, оставьте комментарий, если вы знаете, что это за политика.