tobey2j0   1년 전

제가 이 문제를 푸는데 이상한 점이 있어서 질문 올립니다.

제출번호 99708330 는 sys.setrecursionlimit(200,000)으로 설정했고, 그 결과 시간초과를 받았습니다.

제출번호 99708377 는 위와 같은 코드지만 sys.setrecursionlimit만 200,001로 재설정했고, 그 결과 AC를 받았습니다.(944ms)

이게 도저히 이해가 안되는게, 첫번째 코드에서 재귀 한도가 부족해서 AC를 못 받은 것이라면 런타임에러를 받았어야 했을 것 같은데 시간초과를 받았다는 것입니다.

혹시 재귀 한도가 점점 커질수록 걸리는 시간이 적어지나 해서 테스트를 해봤는데, 다음과 같은 결과가 나왔습니다.

아래는 테스트한 코드입니다.

python 3

제출번호 99708762: sys.setrecursionlimit(100,000)으로 설정, 런타임에러.

제출번호 99708481: sys.setrecursionlimit(199,999)으로 설정, 시간초과.

제출번호 99708330: sys.setrecursionlimit(200,000)으로 설정, 시간초과.

제출번호 99708377: sys.setrecursionlimit(200,001)으로 설정, 944ms 로 AC 받음.

제출번호 99708371: sys.setrecursionlimit(250,000)으로 설정, 904ms 로 AC 받음.

제출번호 99708343: sys.setrecursionlimit(1,000,000)으로 설정, 864ms 로 AC 받음.

제출번호 99708602: sys.setrecursionlimit(5,000,000)으로 설정, 896ms 로 AC 받음.

pypy3

제출번호 99708646: sys.setrecursionlimit(199,999)으로 설정, 684ms로 AC 받음.

제출번호 99708660: sys.setrecursionlimit(200,000)으로 설정, 684ms로 AC 받음.

제출번호 99708668: sys.setrecursionlimit(200,001)으로 설정, 700ms로 AC 받음.

제출번호 99708734: sys.setrecursionlimit(300,000)으로 설정, 696ms로 AC 받음.

제출번호 99708725: sys.setrecursionlimit(500,000)으로 설정, 688ms로 AC 받음.

도데체가 뭔 기준인지 모르겠네요.

혹시 이에 대해 아시는 분 있으면 답장해주시면 감사하겠습니다.

bupjae   1년 전

아래에 설명할 내용은 100% 확실하지 않은 추정의 이야기입니다만, 이것이 원인일 가능성이 매우 높습니다.

.

제 로컬 컴퓨터에서 python3 환경에서 sys.setrecursionlimit(1000) 와 sys.setrecursionlimit(100000) 을 지정한 후 일부러 RecursionError 가 발생할 만큼 재귀호출을 실행한 결과

sys.setrecursionlimit(100000) 이후에 발생한 RecursionError 의 Traceback 출력에 걸리는 시간이 훨씬 길었습니다.

(출력하는 줄 수 자체는 비슷했지만, 내부적으로 "비슷한 stacktrace" 를 판단하는 과정, 그러니까 [Previous line repeated 99996 more times] 같은 메세지로 생략할 부분을 판단하는 과정에서 시간이 많이 소모된 것으로 추정됩니다.)

.

sys.setrecursionlimit(199999) 와 sys.setrecursionlimit(200000) 의 경우, RecursionError 가 발생했으나, 그것을 stderr 에 출력하려고 하는 과정에서 시간초과 가 발생한 것으로 추정됩니다.

.

pypy3 의 sys.setrecursionlimit 의 의미는 python3 과 전혀 다르기 때문에 직접적인 비교를 할 수 없습니다.

댓글을 작성하려면 로그인해야 합니다.