알고리즘에 따른 속도차이

요즘 객체지향 프로그래밍을 공부를 하고 있는데 문득 “같은 목적의 프로그램이지만 라인과 코딩숫자가 다를 경우의 속도차이는 어떠할까?”라는 궁금 점이 들더군요.
그래서 최근 배우고 있는 Java를 이용해서 홀수 마방진 프로그램을 만들었습니다.

첫 번째 알고리즘은 보통 사람들이 많이 구현하고, 제가 고등학교 때 구현했던 알고리즘입니다.


그림에서 보시다시피 맨 처음 시작은 상단의 정 중앙에서 시작합니다. 그 뒤 우측 위쪽으로 1칸씩 이동을 하며 만약 공간을 벗어났을 경우 벗어난 곳의 반대쪽에 지정을 합니다. 그리고 지정한 곳에 숫자가 있으면 이전 곳의 아래를 지정하는 순으로 만들어지게 됩니다.

소스

두 번째 알고리즘은 첫 번째 알고리즘의 기초가 되는 알고리즘인데 제가 오늘 안 돌아가는 머리 굴려가며 구현한 알고리즘입니다.


지정된 공간에서 벗어난 지점을 포함해서 대각선으로 숫자를 넣은 뒤 벗어난 지역의 숫자를 반대편으로 넣는 방식으로 만들어집니다.

소스

두 알고리즘의 결과는 약간 다르지만 두 개 모두 같은 목적을 가진 알고리즘입니다.

각 알고리즘별 출력 결과


이제 이 두 개의 알고리즘을 놓고 속도, 컴파일 시 용량을 측정해 보겠습니다.

속도 측정은 999 * 999짜리 마방진을 100번 만들어내는 속도로 측정을 했습니다.

첫 번째 결과

두 번째 결과


두 결과 모두 0.5초, 0.8초 차이로 두 번째 알고리즘의 승리입니다.

그럼 컴파일 시 용량이 어떻게 되는지 알아보겠습니다.


18바이트 차이로 두 번째 알고리즘의 승리군요.

알고리즘 선택에 따라 이렇게 미묘한 차이가 있을 수 있다는 것을 이번 실험에서 알아낼 수 있었습니다. 하지만 이 미묘한 차이가 쌓이고 쌓이면 엄청나한 차이가 있을 수 있다는 사실을 잊어서는 안될 것 같습니다.

여기서 보너스~

두 번째 알고리즘을 구현하기 위해 머리를 싸맸던 흔적을 공개하겠습니다 >.<

단 한줄 때문에 이런 삽질을...

신고
Trackback 0 Comment 4
  1. Favicon of http://www.signpen.pe.kr BlogIcon 싸인펜 2006.04.10 03:24 신고 address edit & del reply

    자바로 마방진을 구현하는 것에 대해선 생각해 본적이 없었는데, 글을 보고 관심이 생겨버려 흥미 있게 봤습니다^^
    글 중에서 속도를 측정했던 부분은 마방진 프로그램 내부에 코드를 추가 하신 건가요, 아니면 따로 측정하는 프로그램이 있는 건가요??

    • Favicon of http://www.myhyuny.net BlogIcon 화현 2006.04.10 07:48 신고 address edit & del

      제가 간단한 코딩으로 넣은것입니다.
      방법은 "실행 후 시간 - 실행 전 시간"으로 단위는 1/1000초입니다.
      예전에 C로 게임짰을때 많이 써먹은 방법입니다 ^^;

  2. Favicon of http://rukxer.net/root/ BlogIcon Rukxer 2006.04.11 22:19 신고 address edit & del reply

    씨부럴 우리는 객체랍시고 C++하는데 이것도 조낸 머리에 쥐난다

    • Favicon of http://www.myhyuny.net BlogIcon 화현 2006.04.12 01:03 신고 address edit & del

      C++ 최강이죠 ㅠ.ㅠ
      포인터에 객체지향까지
      사람 골머리 썩히는것의 집합체 ㅠ.ㅠ



티스토리 툴바