lwh1992   4년 전

저는

9번째 줄에 if (b % 2 == 0) return (go(a, b / 2, c)%c * go(a, b / 2, c)) % c;을 할때 앞뒤에 go함수가 같기때문에 시간초과가 발생할 거라고 생각했는데 통과가 되서 여쭤보려 합니다.

memoization을 안해도 되는건지 알려주시면 감사하겠습니다.

djm03178   4년 전

컴파일러가 go 함수를 똑같은 인자로 호출하는 것이 똑같은 결과를 반환할 것을 알고 자체적으로 최적화를 한 거라고 생각됩니다.

1207koo   4년 전

컴파일러가 최적화를 한다고 해도 실행을 하지 않는 것은 의도하지 않은 결과가 나올 수 있기 때문에 그 정도의 최적화는 불가능하다고 생각합니다.

실제로 코드를 돌려보면 go 함수가 b값에 비례한 횟수로 실행되는데, 그냥 채점이 빠른 것이라고 생각됩니다.(또는 b가 큰 데이터가 없거나)

b가 만약 10^18이면 안 돌아갈 듯 하네요.

djm03178   4년 전

코드를 어디에서 올려보셨는지 모르겠지만 최적화 기법은 컴파일러마다 다르기 때문에 어느 한 곳에서 최적화가 이루어지지 않았다고 해서 다른 곳에서도 되지 말라는 법은 없습니다.

정말로 b값에 비례에서 호출이 일어났다면 말씀하신 대로 10^18이면 안 돌아야겠지만, 채점 환경과 유사한 환경에서 잘 돕니다.  https://ideone.com/2RS6Gf

물론 호출이 실제로 있는데도 실행을 하지 않는 것이 일반적으로는 위험할 수 있으나, 이 함수의 경우 실행 범위가 명확하고 정적 분석을 통해 충분히 이 함수 내부를 벗어나지 않고 결정적인 연산이 이루어진다고 판단할 수 있기 때문에 최적화가 가능합니다.

djm03178   4년 전

그리고 함수가 실행된 횟수를 카운트하는 변수를 따로 만들어서 측정하신 거라면, 바로 그 변수의 값이 몇 번 증가될지를 예측할 수 없어서 최적화를 수행하지 못한 것일 수도 있습니다.

bupjae   4년 전

https://cpp.godbolt.org/z/inl6...

-O2 옵션에서 함수 호출을 한 번으로 줄이는 최적화가 이루어졌음을 확인했습니다.

"순수 함수" (함수 외부에 영향을 미치지 않는 함수) 라는 것을 파악할 수 있으면 이런 종류의 최적화는 가능하다고 생각합니다.

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