생각하는 프로그래밍

from 분류없음 2009/12/13 11:42
칼럼 1: 조개 껍질 깨기

1.1 대화
Q: "디스크 파일을 어떻게 정리하지?"
A: "오픈 소스 사이트에 있는 디스크 파일 정리 라이브러리를 사용해봐"

정확한 문제에 대한 요구사항 분석이 없다면 최적의 해답을 이끌어낼 수 없다.


1.2 정확한 문제 기술
대화를 통해 분석된 문제의 정보
    - 데이터의 종류: (지역 번호 3자리 +) 7자리의 전화번호 숫자
    - 지역번호가 800으로 시작하는 무료통화 번호가 데이터
    - 전화번호는 겹칠 수 없음
    - 시스템에서 해당 문제를 해결하기 위해 할당할 수 있는 메모리 공간은 1MB 남짓임

정리된 문제 정보
    입력: 최대 n개의 양의 정수를 포함하는 파일로, 각 숫자는 n보다 작고, n=107이다.
             어떤 숫자가 두 번 이상 나오는 것은 치명적 에러이다.
             정수 이외의 데이터는 없다.
    출력: 입력된 정수를 오름차순으로 정렬한 리스트
    제약조건: 메모리를 많아야 대략 1MB 정도를 사용할 수 있고,
                   디스크 공간은 충분하다.
                   실행 시간은 최대 몇 분 정도가 될 수 있고, 10초 정도 안에 작업을 끝낼 수 있으면 충분함.


1.3 프로그램 디자인
제안할 수 있는 방법
  • 디스크 기반의 머지 정렬
  • 다중 패스 정렬
    • 만약 각 숫자를 7바이트에 저장한다면,
      143,000 개 = 1MB / 1Byte * 7 자리  - 각 숫자를 따로 표현
      250,000 개 = 1MB /  32bit (4Byte)    - 전화번호 전체를 하나의 정수로 표현
    • 데이터를 40번으로 나누어 읽어서 메모리에서 Quick sort를 수행한다.
  • 메모리에 데이터를 모두 로드하여, 한번에 정렬하는 '놀라운' 방법?


1.4 구현 스케치
20 이하의 음이 아닌 정수는 20비트로 표현 가능함.
ex) {1, 2, 3, 5, 8, 13} 을 비트열로 나타내는 방법
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
0
1
1
1
0
1
0
0
1
0
0
0
0
1
0
0
0
0
0
0

이 것을 전화번호부에 적용하면 다음과 같다.
0000000
0000001
0000002
...
1352311
...
9999999
1(있음)
0(없음)
1(있음)

1(있음)

0(없음)

(주의! 위의 데이터 형식은 아직도 1MB를 초과하는 메모리를 사용함. - 약 1.25MB)

위와 같은 데이터 표현의 정렬은 해당 데이터의 특성을 이용한다.
  • 상대적으로 작은 범위 내의 입력
  • 중복된 숫자가 없음
  • 각 레코드 정수 이외의 다른 연관된 데이터가 없음.

솔루션
  1. 1단계: 비트맵을 모두 0으로 초기화
    for i = [0, n)
    bit[i] = 0
  2. 2단계: 존재하는 숫자를 비트맵에 표시
    for each i in the input file
    bit[i] = 1
  3. 3단계; 정렬된 결과를 기록
    for  i = [0, n)
    if bit[i] == 1
    write i on the output file

1.5 원리
  • 작은 문제에 대한 주의 깊은 분석으로 때로는 엄청난 실질적 이득을 얻을 수 있다.
    • 그러나, 이 프로그램의 특화된 구조는 특정 부분의 명세가 변경될 경우 수정하기 어려울 것
      (ex. 전화번호 수가 8자리로 늘어난다던지)
  • 정확한 문제 정의는 문제를 해결하는 데 있어 큰 몫을 차지한다.
  • 비트맵 데이터 구조
    • 이 데이터 구조는 원소가 중복되지 않고 원소와 관련된 다른 데이터도 없는 촘ㅊ모한 유한 집합을 표현할 수 있음.
    • 이 비트맵 데이터는 더 복잡ㅎ나 엔트리를 갖는 테이블에 대한 인덱스로 사용할 수 있음.
  • 다중 패스 알고리즘
    • 입력 파일을 여러 번 읽어 각 단계마다 조금씩 작업하는 방식에 응용할 수 있음.

  • 시간-공간의 트레이드 오프(Tradeoff)인 것과 아닌 것
    • 일반적으로 프로그래밍 분야에는 시간-공간 트레이드오프가 많음.
    • ex) 2패스 알고리즘은 실행 시간을 두 배로 늘리는 대신 사용공간을 절반으로 줄임
    • 하지만 저자 경험 상, 프로그램이 사용하는 공간을 줄이면 실행시간 역시 줄어드는 경우가 자주 있음.
      • 이유 1: 데이터가 적다는 것은 그것을 처리하는 데 걸리는 시간도 적다는 것을 의미함
      • 이유 2: 데이터를 디스크보다 메모리에 두면 디스크에 접근하는 오버헤드를 피할 수 있음.
      • 두 가지 모두를 개선할 수 있는 문제라면, 그것은 그 문제에 대한 솔루션 디자인이 최적화되지 않았다는 증거!

1.6 연습 문제
  1. 메모리가 충분하다면, 집합(set)의 표현과 정렬을 어떻게 구현하겠는가? (라이브러리 사용)
  2. 비트 벡터는 비트 연산(AND, OR, SHIFT 같은)을 이용해 어떻게 구현할 수 있는가?
  3. 문제에서 제공된 시스템이 단 0.25MB의 추가 여유공간도 없다면, 어떻게 알고리즘을 변경해야 하는가?
  4. 무료통화 지역번호가 기존 800 단일 번호에서 877, 888 등 다른 국번도 생긴다면, 이 프로그램은 어떻게 변경되어야 하는가?
  5. 유인 우주비행 개척자들은 곧 우주의 극한 환경에서도 잘 동작하는 필기도구의 필요성을 깨달았다.
    전해오는 이야기에 따르면 NASA는 이 문제를 해결하기 위해 백만 달러의 연구비를 들여 특별한 페을 개발했다고 한다.
    러시아는 같은 문제를 어떻게 해결했을까?


Creative Commons License
Creative Commons License
받은 트랙백이 없고, 댓글이 없습니다.
<< previous 1 2 3 4 5 ... 192 next >>