비슷한 코드의 프로그램인데 C++가 자바보다 느립니다

c-clef의 이미지

제가 스도쿠 푸는 프로그램을 자바로 만들었는데요. 일요일에 C++ 책을 사서 C++을 공부하면서 이 프로그램의 핵심인 SudokuSolver 클래스만 C++로 옮겨서 콘솔에서 사용자 입력을 받아 작동하도록 만들어 보았습니다. 그런데 예상과는 달리 C++로 옮긴 프로그램이 더 느립니다. 이건 제가 C++에 익숙하지 않아서 프로그램을 제대로 옮기지 못 했기 때문인가요(C/C++은 거의 처음입니다)? 아무리 코드를 살펴봐도 특별히 더 느려질 만한 곳은 보이지 않는데... C++가 자바보다 느릴 수도 있나요?

자바 버전의 프로그램과 소스 코드는 이곳에서 받으실 수 있고, C++ 버전의 소스 코드는 첨부 파일로 올렸습니다.

File attachments: 
첨부파일 크기
Plain text icon warming-up.cpp_.txt8.84 KB
나그네나그네의 이미지

makeNeighborLists()에서 for문 안에 있는
int* list = new int[N * 3 - n * 2 - 1];
이걸 밖으로 빼낼 수 없는가요?
----------------
agidari.wordpress.com

c-clef의 이미지

그렇게 하면 neighborLists의 모든 int*가 같은 값을 가리키게 됩니다. 그리고 makeNeighborLists() 함수는 한 번만 실행되니 속도에는 별 영향을 못 줄 것 같습니다.

klara의 이미지

updateCandidateLists 는 어떤가요?

bool updateCandidateLists(int cellIndex, int candidateIndex)
{	
	game[cellIndex] = candidateLists[cellIndex][candidateIndex];
	candidateLists[cellIndex].clear();
 
	for (int i = 0; i < N * 3 - n * 2 - 1; i++) {
		int neighbor = neighborLists[cellIndex][i];
 
        if (game[neighbor] == '.') {
			vector<char>::iterator iter = candidateLists[neighbor].begin();
			vector<char>::iterator end = candidateLists[neighbor].end();
			iter = find(iter, end, game[cellIndex]);
			if (iter != end) {
				candidateLists[neighbor].erase(iter);
			}
 
			if (candidateLists[neighbor].empty()) {
                return false;
            }
        }
    }
    return true;
}

여기서 for문 속의 candidateLists[neighbor].erase(iter);가 걸리는데요..
그냥 둘러본 바론 어떤 조건에서 실행될지 모르겠어서 자주 불릴진 모르겠는데, 이게 자주 실행된다면 심각하게 느려집니다.
std::vector는 (제가 알기론 Java의 Vector도 마찬가지로) 중간에 삽입하고 삭제하는데에는 시간이 오래 걸리니까요..
std::list가 적합할진 모르겠지만, 저 부분이 자주 불린다면 적어도 vector가 아닌 다른 자료구조를 이용하시는게 좋을 것 같습니다.

마지막으로 아직 작성중이라 그런진 모르겠지만,동적할당 한 부분에 delete가 하나도 없네요-_-; 그리고 자세히보면 어떨지 모르겠지만, 얼핏 보기엔 그냥 바로 배열로 선언해도 될것을 불필요하게 동적할당한거처럼 보이는 것도 있네요..

c-clef의 이미지

평범한 9 by 9 스도쿠로 설명을 드리면,

어떤 빈 셀의 candidateList는 그 셀에 대입할 수 있는 가능한 후보 문자들의 집합을 나타냅니다. 이 집합의 크기는 최소 0부터 최대 9까지입니다.

updateCandidateLists(int, int)는 특정한 셀의 특정한 후보 문자를 그 셀에 대입하고, 이 셀이 새로운 값을 가지는 것에 영향을 받는 모든 셀들(neighborLists[cellIndex]에 속하는 인덱스를 가진)의 candidateList를 갱신하는 함수입니다.

자바에서는 candidateList를 ArrayList로 구현했습니다. C++에서는 vector로 했구요. ArrayList도 vector처럼 중간의 삭입/삭제는 느릴 텐데... 일단 candidateList에 대한 임의 접근이 필요하지 않도록 바꾸고 list를 써보겠습니다.

참고로 이 프로그램에서 가장 많이 호출되는 함수는 아마 updateCandidateLists(int, int)와 recoverCandidateLists()일 겁니다.

kaeri17의 이미지

동적할당과 vector가 주된 원인인듯 합니다. C++에서 동적할당은 JAVA의 동적할당보다 결코 빠르다고 할수는 없죠.
그리고 vector의 자바와 C++의 차이는 자바는 vector긴 한데 넣는것은 레퍼런스일 뿐이고 C++의 vector는 객체 자체를 넣기 때문에 중간에 삽입하는 연산의 소요시간 자체는 c++의 vector가 느립니다. 뒤에 있는걸을 한칸씩 밀어야 하는데 객체 크기가 크면 시간이 것잡을수 없게 늘어나죠.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.