알고리즘에 따른 속도차이
컴퓨터/프로그래밍 2006/04/09 22:14
요즘 객체지향 프로그래밍을 공부를 하고 있는데 문득 “같은 목적의 프로그램이지만 라인과 코딩숫자가 다를 경우의 속도차이는 어떠할까?”라는 궁금 점이 들더군요.
그래서 최근 배우고 있는 Java를 이용해서 홀수 마방진 프로그램을 만들었습니다.
첫 번째 알고리즘은 보통 사람들이 많이 구현하고, 제가 고등학교 때 구현했던 알고리즘입니다.
그림에서 보시다시피 맨 처음 시작은 상단의 정 중앙에서 시작합니다. 그 뒤 우측 위쪽으로 1칸씩 이동을 하며 만약 공간을 벗어났을 경우 벗어난 곳의 반대쪽에 지정을 합니다. 그리고 지정한 곳에 숫자가 있으면 이전 곳의 아래를 지정하는 순으로 만들어지게 됩니다.
소스
두 번째 알고리즘은 첫 번째 알고리즘의 기초가 되는 알고리즘인데 제가 오늘 안 돌아가는 머리 굴려가며 구현한 알고리즘입니다.
지정된 공간에서 벗어난 지점을 포함해서 대각선으로 숫자를 넣은 뒤 벗어난 지역의 숫자를 반대편으로 넣는 방식으로 만들어집니다.
소스
두 알고리즘의 결과는 약간 다르지만 두 개 모두 같은 목적을 가진 알고리즘입니다.
각 알고리즘별 출력 결과
이제 이 두 개의 알고리즘을 놓고 속도, 컴파일 시 용량을 측정해 보겠습니다.
속도 측정은 999 * 999짜리 마방진을 100번 만들어내는 속도로 측정을 했습니다.
첫 번째 결과
두 번째 결과
두 결과 모두 0.5초, 0.8초 차이로 두 번째 알고리즘의 승리입니다.
그럼 컴파일 시 용량이 어떻게 되는지 알아보겠습니다.
18바이트 차이로 두 번째 알고리즘의 승리군요.
알고리즘 선택에 따라 이렇게 미묘한 차이가 있을 수 있다는 것을 이번 실험에서 알아낼 수 있었습니다. 하지만 이 미묘한 차이가 쌓이고 쌓이면 엄청나한 차이가 있을 수 있다는 사실을 잊어서는 안될 것 같습니다.
여기서 보너스~
두 번째 알고리즘을 구현하기 위해 머리를 싸맸던 흔적을 공개하겠습니다 >.<
단 한줄 때문에 이런 삽질을...
'컴퓨터 > 프로그래밍' 카테고리의 다른 글
| [문제] 초등학생도 풀만한 기초 문제 – 2 : 삼각형 변형 1 (4) | 2007/01/16 |
|---|---|
| [강좌] 초등학생도 풀만한 기초 문제 – 1 : 삼각형 기본 [해설] (2) | 2007/01/15 |
| [강좌] 초등학생도 풀만한 기초 문제 – 1 : 삼각형 기본 [문제] (2) | 2007/01/13 |
| 간단한 강좌 기획 중~~ (2) | 2007/01/12 |
| 스레드를 이용한 병렬처리 프로그래밍 (3) | 2006/05/12 |
| 알고리즘에 따른 속도차이 (5) | 2006/04/09 |
