비슷한 코드의 프로그램인데 C++가 자바보다 느립니다
글쓴이: c-clef / 작성시간: 수, 2008/02/06 - 1:43오전
제가 스도쿠 푸는 프로그램을 자바로 만들었는데요. 일요일에 C++ 책을 사서 C++을 공부하면서 이 프로그램의 핵심인 SudokuSolver 클래스만 C++로 옮겨서 콘솔에서 사용자 입력을 받아 작동하도록 만들어 보았습니다. 그런데 예상과는 달리 C++로 옮긴 프로그램이 더 느립니다. 이건 제가 C++에 익숙하지 않아서 프로그램을 제대로 옮기지 못 했기 때문인가요(C/C++은 거의 처음입니다)? 아무리 코드를 살펴봐도 특별히 더 느려질 만한 곳은 보이지 않는데... C++가 자바보다 느릴 수도 있나요?
자바 버전의 프로그램과 소스 코드는 이곳에서 받으실 수 있고, C++ 버전의 소스 코드는 첨부 파일로 올렸습니다.
File attachments:
첨부 | 파일 크기 |
---|---|
![]() | 8.84 KB |
Forums:
....
makeNeighborLists()에서 for문 안에 있는
int* list = new int[N * 3 - n * 2 - 1];
이걸 밖으로 빼낼 수 없는가요?
----------------
agidari.wordpress.com
....
그렇게 하면 neighborLists의 모든 int*가 같은 값을 가리키게 됩니다. 그리고 makeNeighborLists() 함수는 한 번만 실행되니 속도에는 별 영향을 못 줄 것 같습니다.
updateCandidateLists 는
updateCandidateLists 는 어떤가요?
여기서 for문 속의 candidateLists[neighbor].erase(iter);가 걸리는데요..
그냥 둘러본 바론 어떤 조건에서 실행될지 모르겠어서 자주 불릴진 모르겠는데, 이게 자주 실행된다면 심각하게 느려집니다.
std::vector는 (제가 알기론 Java의 Vector도 마찬가지로) 중간에 삽입하고 삭제하는데에는 시간이 오래 걸리니까요..
std::list가 적합할진 모르겠지만, 저 부분이 자주 불린다면 적어도 vector가 아닌 다른 자료구조를 이용하시는게 좋을 것 같습니다.
마지막으로 아직 작성중이라 그런진 모르겠지만,동적할당 한 부분에 delete가 하나도 없네요-_-; 그리고 자세히보면 어떨지 모르겠지만, 얼핏 보기엔 그냥 바로 배열로 선언해도 될것을 불필요하게 동적할당한거처럼 보이는 것도 있네요..
평범한 9 by 9
평범한 9 by 9 스도쿠로 설명을 드리면,
어떤 빈 셀의 candidateList는 그 셀에 대입할 수 있는 가능한 후보 문자들의 집합을 나타냅니다. 이 집합의 크기는 최소 0부터 최대 9까지입니다.
updateCandidateLists(int, int)는 특정한 셀의 특정한 후보 문자를 그 셀에 대입하고, 이 셀이 새로운 값을 가지는 것에 영향을 받는 모든 셀들(neighborLists[cellIndex]에 속하는 인덱스를 가진)의 candidateList를 갱신하는 함수입니다.
자바에서는 candidateList를 ArrayList로 구현했습니다. C++에서는 vector로 했구요. ArrayList도 vector처럼 중간의 삭입/삭제는 느릴 텐데... 일단 candidateList에 대한 임의 접근이 필요하지 않도록 바꾸고 list를 써보겠습니다.
참고로 이 프로그램에서 가장 많이 호출되는 함수는 아마 updateCandidateLists(int, int)와 recoverCandidateLists()일 겁니다.
소스를 다 보지 않았지만
동적할당과 vector가 주된 원인인듯 합니다. C++에서 동적할당은 JAVA의 동적할당보다 결코 빠르다고 할수는 없죠.
그리고 vector의 자바와 C++의 차이는 자바는 vector긴 한데 넣는것은 레퍼런스일 뿐이고 C++의 vector는 객체 자체를 넣기 때문에 중간에 삽입하는 연산의 소요시간 자체는 c++의 vector가 느립니다. 뒤에 있는걸을 한칸씩 밀어야 하는데 객체 크기가 크면 시간이 것잡을수 없게 늘어나죠.
댓글 달기