wyldecat   2년 전

평범하게 이분매칭 돌려서했어요..! 

https://www.acmicpc.net/source/1085607

이분건 저랑 거의 비슷한데.. 속도가 7배 정도 빠르네요!!! 


다른 분들거는 봐도 잘 모르겠구요.. ㅠㅠ

ckdgus2482   2년 전

39번 라인에서 성능저하가 발생할 수 있을것 같습니다.

벡터 객체의 생성을 N번이나 수행하네요. 거기다가 N개의 데이터로 초기화까지 진행하니 오버헤드가 상당합니다.

wyldecat   2년 전

오오..!!!!!!!! 그렇군요.. memset을 사용해서 다시 테스트해봐야겠어요ㅎㅎ

wyldecat   2년 전

큽.. for문으로 대체를 해도 똑같은 시간이 뜨네요... 댓글 감사합니다 (_ _)

ckdgus2482   2년 전

우선 37라인~41라인의 for문 돌때마다 새로운 벡터 객체를 생성하는것 자체가 오버헤드가 발생하구요. 초기화도 생성자를 통해서 하든 memeset이나 for문을 이용해서 수행하든 오버헤드가 발생할 수 밖에 없습니다.

그럴게 아니라 N최대값*N최대값 사이즈의 전역변수 배열로 바꿔서 해보세요. 0으로 초기화하는 것이므로 전역변수로 선언만하면 러닝타임중 별다른 초기화과정을 수행할 필요가 없겠죠.

wyldecat   2년 전

ㅎㅎ 댓글감사합니다..!! 아예 벡터를 안쓰고 배열을 정적으로 할당해서 해봐도 똑같네요 ㅠ-ㅠ

ckdgus2482   2년 전

아뇨... 37라인에서 배열 초기화하고 계시잖아요. 제 말은 bool visited[N최대값][N최대값]; 이렇게 선언하라는 얘기였어요.

배열을 재활용하려면 배열 초기화를 N번 진행해야하지만 애초에 배열 자체를 N개 만들어놓으면 초기화를 전혀 할 필요가 없잖아요.

wyldecat   2년 전

앗!!! 그렇군요 ㅎㅎ 막줄을 제대로 안읽었네요 ㅠㅠ

wyldecat   2년 전

ㅠㅠ 계속 귀찮게해드려 죄송해유.. 이렇게했더니 시간이 오히려 늘었네용..

ckdgus2482   2년 전

dfs정의에서 bool*를 인자로 받게 하고 38라인에서 아래와같이 호출하면 조금 더 빨라집니다.

dfs(visited[start], start)

물론 16, 17라인은 다시 1차원배열로 바꾸시구요.


근데 이렇게해도 맨처음 비교하신분만큼 속도는 안나오네요... 코드수준의 최적화 문제는 아닌것 같습니다.

아무래도 DFS부분을 좀더 면밀히 비교해볼 필요가 있을것 같습니다.

wyldecat   2년 전

넵 ㅎㅎ 신경써주셔서 감사합니다 (_ _)

ckdgus2482   1년 전

전역변수는 프로그램이 메모리에 로드되는 시점에서 모두 초기화 되는 것입니다.

main에 진입하기 전에 이미 다 초기화가 된 상태죠.

ckdgus2482   1년 전

그리고 이 문제에서 실제로 비교해본 결과 160ms정도 차이가 났고요.

ckdgus2482   1년 전

우선 blinkingstar님 이전 댓글에서 '배열에 접근할때마다' 라고 하셔서 의도를 제대로 파악하지 못했습니다.

OS가 bss섹션 관리에 있어서 zero-fill-on-demand 정책을 사용한다는 것은 알고 있습니다.

다만 그건 페이지 폴트가 발생했을때라는 조건이 있죠.

이 프로그램 규모가 굉장히 작은 편이라서 프리페이징 과정에서 프로세스 전체가 메모리에 로드될 가능성이 굉장히 높습니다.

만약 그렇지 않다면 채점머신의 램을 증설해야겠죠.

굳이 초기화가 아니더라도 프로그램 실행 중 페이지폴트가 발생하면 오버헤드가 꽤 발생할 것입니다.

그러면 같은 소스라도 채점머신의 상태에 따라 시간이 상이해질 수 있다는 것인데 그러면 공정한 채점이라고 할 수 없겠죠.

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