wyldecat   7달 전

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

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

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


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

ckdgus2482   7달 전

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

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

wyldecat   7달 전

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

wyldecat   7달 전

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

ckdgus2482   7달 전

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

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

wyldecat   7달 전

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

ckdgus2482   7달 전

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

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

wyldecat   7달 전

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

wyldecat   7달 전

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

ckdgus2482   7달 전

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

dfs(visited[start], start)

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


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

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

wyldecat   7달 전

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

전역변수로 배열을 아무리 미리 선언해 놓는다고 하더라도 시간이 줄지는 않습니다. 왜냐하면 전역변수의 경우 배열에 접근하는 순간에 초기화 작업을 하기 때문이지요. 딱히 for문 안에서 초기화 하는 것과는 시간차이가 별로 나지 않을 것 같습니다.

ckdgus2482   2달 전

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

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

ckdgus2482   2달 전

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

답글 확인했습니다!

  제가 알고 있는 바로는 전역변수로 배열을 잡을 시에 zero-fill-on-demand로 실제 해당 메모리 페이지를 요청시에 0으로 채운 페이지를 리턴해 주는 것으로 알고 있습니다. 따라서 전역변수로 선언하였다고 하더라도 초기화 값 없는 전역변수 -> .bss에 주소만 할당 -> 접근시 페이지 생성과정으로 같은 크기만큼 초기화 작업이 진행되기 때문에 속도 차이가 없을 것이라고 생각했는데 ckdgus2482님이 말씀하신 것처럼 이 과정이 프로그램 실행 전에 일어나 main함수 전에 수행될꺼라는 것을 보장할 수 없습니다. 순전히 OS 스케쥴링에 따라서 언제 초기화 될지는 결정되는 것이지요. 또한 프로그램 수행 시간을 측정할 때, os단에서 메모리를 초기화 시켜주는 시간을 포함하느냐 포함하지 않느냐에 따라서도 대답이 달라질 수 있을 것 같습니다.

 다만, 실제로 테스트 해보신 결과 속도 차이가 나는 결정적인 이유는 초기화 하는데 걸리는 미미한 시간보다는 for문 안에서 로컬 변수로 배열을 선언할 시에 전역 변수로 선언할 때와는 다르게 스택에서의 offset을 계산해 주어야 하기 때문에 정적인 주소에 접근하는 전역 변수보다는 느릴 수 있을 것 같습니다. [이 글](http://stackoverflow.com/questions/5210787/global-...)을 참고해 보시면 좋을 것 같습니다. 


 물론 위에서 말씀드린 내용이 160ms 정도나 차이가 날 정도로 이 차이가 유의미한 것 같지는 않아 시간이 저 정도로 많이 차이가 나는 이유는 다른 원인이 있지 않을까 생각합니다. 고수님들이 오셔서 답변해 주시면 좋겠네요 ㅠㅠ

ckdgus2482   2달 전

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

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

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

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

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

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

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

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