1325번 - 효율적인 해킹
직전 재채점에서 시간이 다소 늘어났으나 시간 초과를 받지 않은 https://www.acmicpc.net/source... 등의 일부 Java 코드들을 저격합니다.
이전에 있었던 https://www.acmicpc.net/board/... 와 비슷한 형태의 데이터지만 정점 번호를 셔플해서 캐시 히트의 차이인지 압도적으로 느린 모습이 확인됩니다.
또한 최근의 관찰에 의하면 Java는 깊은 재귀에 대해 심히 비효율적인 모습을 보이는데 그 때문인지 https://www.acmicpc.net/source... 등의 대부분의 DFS도 평균 최대 탐색 깊이를 최대화한 데이터들에 대해 감당하지 못하는 것 같습니다.
Java가 시간 제한에 가까운 코드가 많아 Java를 주로 저격하기는 했지만 다른 언어들도 비슷한 원리로 어느 정도 시간이 증가하는 효과를 볼 수 있을 것 같습니다.
data2.zip
재채점했습니다.
Java 계열 코드의 80% 이상이 터진 것 같네요.
:blobthumbsup:
댓글을 작성하려면 로그인해야 합니다.
djm03178 3년 전
직전 재채점에서 시간이 다소 늘어났으나 시간 초과를 받지 않은 https://www.acmicpc.net/source... 등의 일부 Java 코드들을 저격합니다.
이전에 있었던 https://www.acmicpc.net/board/... 와 비슷한 형태의 데이터지만 정점 번호를 셔플해서 캐시 히트의 차이인지 압도적으로 느린 모습이 확인됩니다.
또한 최근의 관찰에 의하면 Java는 깊은 재귀에 대해 심히 비효율적인 모습을 보이는데 그 때문인지 https://www.acmicpc.net/source... 등의 대부분의 DFS도 평균 최대 탐색 깊이를 최대화한 데이터들에 대해 감당하지 못하는 것 같습니다.
Java가 시간 제한에 가까운 코드가 많아 Java를 주로 저격하기는 했지만 다른 언어들도 비슷한 원리로 어느 정도 시간이 증가하는 효과를 볼 수 있을 것 같습니다.
data2.zip