100 X 100 어레이에서 DFS를 수행하려고합니다. (array의 요소는 그래프 노드를 나타냅니다.) 그래서 최악의 경우를 가정하면 재귀 함수 호출의 깊이는 각 호출이 20 바이트까지 올라갈 때마다 최대 10000까지 올라갈 수 있습니다. 그래서 그것은 가능한 수단 stackoverflow의 가능성은 무엇입니까?프로그램의 C/C++ 최대 스택 크기
C/C++에서 스택의 최대 크기는 얼마입니까?
윈도우
2) 유닉스에서 모두
1) Cygwin에서 gcc에 대한 지정하십시오
일반적인 한계는 무엇인가?
Visual Studio에서 기본 스택 크기는 1MB로 생각됩니다. 따라서 재귀 깊이가 10,000 인 경우 각 스택 프레임은 최대 100 바이트까지 가능하므로 DFS 알고리즘에 충분합니다.
Visual Studio를 포함한 대부분의 컴파일러에서는 스택 크기를 지정할 수 있습니다. 일부 (모든?) 리눅스에서 스택 크기는 실행 파일의 일부가 아니라 OS의 환경 변수입니다. 그런 다음 ulimit -s을 사용하여 스택 크기를 확인한 다음이를 ulimit -s 16384과 같은 새 값으로 설정할 수 있습니다.
다음은 gcc의 기본 스택 크기가 link입니다. 재귀없이
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())
Thnk u 대단히 – avd
참조 용으로, BFS는 FIFO 스택 대신. –
예 또는 STL-lingo에서 pop_front/push_back으로 std :: deque를 사용하십시오. –
플랫폼 종속, 툴체인 종속, ulimit 종속, 매개 변수 종속 .... 이것은 모두 지정되지는 않으며 영향을 줄 수있는 정적 및 동적 속성이 많이 있습니다.
일반 한계는 무엇입니까? – avd
"일반 제한 사항"이 없습니다. Windows에서 기본 VC++ 링커 옵션과 기본 CreateThread 동작 (일반적으로 스레드 당 약 1 MiB 정도). 리눅스에서는 무제한의 사용자로 제한이 없다고 생각합니다. 스택은 거의 전체 주소 공간을 차지하기 위해 아래쪽으로 확장 될 수 있습니다. 기본적으로 묻는다면 스택을 사용해서는 안됩니다. – DrPizza
임베디드 시스템에서 4k 이하일 수 있습니다. 어떤 경우에는 스택을 사용하는 것이 합리적 일 때라도 물어봐야합니다. 그 대답은 일반적으로 갈리아 어깨 구리입니다. –
예, 스택 오버플로가 발생할 수 있습니다. C 및 C++ 표준은 스택 깊이와 같은 것을 지시하지 않으며, 일반적으로 환경 문제입니다.
대부분의 알맞은 개발 환경 및/또는 운영 체제를 사용하면 링크 또는로드 시간에 프로세스의 스택 크기를 조정할 수 있습니다.
보다 구체적인 대상 지정을 위해 사용중인 OS 및 개발 환경을 지정해야합니다.
예를 들어, Ubuntu Karmic Koala에서 gcc의 기본값은 2M이며 4K가 커밋되었지만 프로그램을 연결할 때 변경할 수 있습니다. 이를 수행하려면 ld의 --stack 옵션을 사용하십시오.
스택은 종종 작다. 링크 시간 기본값 인 을 변경하거나 런타임에 변경할 수도 있습니다. 참고로 는 일부 기본값은 다음과 같습니다 :
이 정보에 대한 참조는 무엇입니까? –
Bruno Haible의 경험에 따라 결정 http://lists.gnu.org/archive/html/bug-coreutils/2009-10/msg00262.html – pixelbeat
난 당신이 사각형 배열에 깊이 우선 탐색을 수행하여 무슨 뜻인지 잘 모르겠지만, 난 당신이 무엇을하는지 아는 가정합니다.
스택 제한이 문제가되면 재귀 솔루션을 중간 값을 힙에서 할당 된 스택으로 푸는 반복 솔루션으로 변환 할 수 있어야합니다.
방금 직장에서 스택이 부족하여 데이터베이스 였고 일부 스레드가 실행 중이 었습니다. 기본적으로 이전 개발자는 스택에 큰 배열을 던져 버렸고 스택은 어쨌든 낮았습니다. 소프트웨어는 Microsoft Visual Studio 2015를 사용하여 컴파일되었습니다.
스레드의 스택이 부족해도 자동으로 실패하고 계속해서 스택의 데이터 내용에 액세스 할 때 오버플로가 발생합니다.
내가 줄 수있는 최선의 조언은 스택에 배열을 선언하지 않는 것입니다. 특히 복잡한 응용 프로그램 및 특히 스레드에서 배열을 선언하는 대신 힙을 사용하십시오. 그게 거기있는거야)
또한 스택을 선언 할 때 즉시 액세스 할 수 있지만 액세스 할 때만 실패 할 수 있습니다. 내 추측은 컴파일러가 "낙천적으로"Windows에서 스택을 선언한다는 것입니다. 즉, 스택이 선언되어 충분히 사용할 수있을 때까지 크기가 정해져 스택이 없다는 것을 알게됩니다.
운영 체제에 따라 스택 선언 정책이 다를 수 있습니다. 이 정책이 무엇인지 아는 경우 의견을 남기십시오.
재귀없이 깊이 우선 검색을 구현할 수 있다는 것을 알고 있습니까? – Sebastian
아니요. 잘 모릅니다. 설명해주세요. – avd
나는 내 대답은 –