PERSPECTIVE ON PERFORMANCE

Jon Bentley가 쓴 Programming Pearls 6장. PERSPECTIVE ON PERFORMANCE를 정리한 글이다.

책에서 제시한 성능 문제를 해결하는 접근 방법은 다음과 같다.


1. 문제 정의(Problem Definition)

어떤 형태의 문제든 올바르게 문제를 파악하는 것보다 중요한 것은 없다. 성능 문제도 예외일 수 없다.

2. 시스템 구조(System Structure)

모듈화. 큰 문제를 작은 문제로 잘 나누기

3. 알고리즘과 데이터 구조(Algorithm and Data Structure)

잘 쪼개진 작은 문제를 해결하는 도구

4. 코드 튜닝(Code Tuning)

코드 잘짜기. 구조가 아닌 미시적인 접근

5. 시스템 소프트웨어

돈으로 해결하기 혹은 구글링

6. 하드웨어

돈...

시스템 소프트웨어나 하드웨어도 돈만으론 개선되지 않는다. 무엇을 바꾸어야 하는지를 파악해야 돈을 올바르게 쓸 수 있기 때문이다.

그런데 다른 문제와 마찬가지로 성능 문제가 발생할 대상 자체를 제거하는 것이 최상이다.

The cheapest, fastest and most reliable components of a computer system are those that aren't there.

존재하지 않는다면 장애와 보안 헛점에서도 자유롭다.

CRACKING THE OYSTER

Jon Bentley가 쓴 Programming Pearls 1장. CRACKING THE OYSTER를 정리한 글이다.

제시된 문제는 다음과 같다.

n(최대 10,000,000 개 이하)개의 0보다 큰 정수로 이루어진 파일이 있다. 동일한 값은 존재하지 않으며, 정수 이외의 데이터는 없다.

이 파일에 있는 정수들을 어떻게 정렬할 수 있을까?

• 메모리는 최대 1 MB까지만 사용할 수 있다.
• 하드 디스크는 충분히 사용할 수 있다.
• 몇 분안에 실행이 완료되어야 한다.

디스크를 이용한 Merge Sort

Merge Sort는 다음을 참고한다. 이 문제를 해결하는데 적합한 알고리즘은 아니다.


Multipass Sort

정수를 7 바이트로 표시하면 1 MB 메모리에 약 143,000 개의 정수를 올려 놓을 수 있다.

1024 * 1024 / 7 = 약 149,796

정수를 32 비트로 표시하면 1 MB 메모리에 약 250,000 개의 정수를 올려 놓을 수 있다.

1024 * 1024 / (32 / 8) = 약 262,144

이 정보를 기초로 파일을 여러번 읽어 문제를 해결할 수 있다.

첫번째 읽을 때는 0에서 249,999 사이 정수만을 메모리에 올려 놓은 후에 정렬을 하여 결과를 파일에 쓴다. 이렇게 반복적으로 마지막에는 9,750,000에서 9,999,999 사이 정수만을 대상으로 이 작업을 수행한다.

반복적으로 40 차례 파일을 일으면 모든 정수를 정렬할 수 있다.

10,000,000 / 250,000 = 40

비트맵을 이용한 처리

정수 이외의 데이터는 없고, 중복된 값이 없다는 전제 조건을 이용하면 간단하게 비트맵으로 문제를 해결할 수 있다.

즉, 크기가 10,000,000인 비트 배열을 만들어서 특정 정수가 존재하면 다음과 같이 처리한다. 예를 들어, 13,223가 존재하면 다음과 같이 한다.

bit[13223] = 1;

* 1 MB 이상 메모리가 필요하다. 1 MB가 엄격한 제한 조건이라면 Twopass Sort와 함께 사용한다.


가상 코드는 다음과 같다.

/* phase 1: initialize set to empty */
for i = [0, n)
  bit[i] = 0
/* phase 2: insert present elements into the set */
for each i in the input file
  bit[i] = 1
/* phase 3: write sorted output */
for i = [0, n)
  if bit[i] == 1
    write i on the output file

비트맵을 이용한 해결 방법은 범용적이지는 않다. 즉 특정 문제를 해결하는데 적합하다. 그런데 특정 문제를 해결하는데는 탁월한 방법이다. 

문제를 해결하는데 가장 중요한 것은 문제를 이해하고 정의하는 것이다.

Careful analysis of a small problem can sometimes yield tremendous practical benefits.

A SAMPLE PROBLEM

Jon Bentley가 쓴 Programming Pearls 12장. SAMPLE PROBLEM을 정리한 글이다.

문제

여론 조사 기관에서는 N 명의 사람 중에서 M 명의 사람을 무작위로 추출하여 설문 조사를 한다.

M < N

N 명의 사람엔 0부터 시작하는 일련번호가 부여되어 있다. N을 5라고 가정하면 다음과 같다.

0 강백호
1 서태웅
2 채치수
3 정대만
4 송태섭

M이 2라면 이 중 동일한 확률로 2명을 추출해야 한다.

이는 0에서 N 사이에서 M 개의 숫자를 동일한 확률로 무작위로 추출하는 것에 다름아니다.

* 이 문제를 해결하는데 다음 2 함수를 사용할 수 있다.

bigrand : m 혹은 n 보다도 클 수 있는 정수를 무작위로 반환한다.
randint(i, j) : i에서 j 사이에 포함되어 있는 정수를 무작위로 반환한다.


솔루션 1

select = m
remaining = n
for i = [0, n)
  if (bigrand() % remaining) < select
    print i
    select--
  remaining--

* 추출된 숫자는 m 보다 많을 수도 m 보다 적을 수도 없다. 강조한 부분을 주의 깊게 보면 이를 파악할 수 있다.

일련번호가 0인 강백호가 선택될 확률은 2 / 5이지만 이 후에 있는 사람들이 선택될 확률은 앞 결과에 영향을 받는다. 예를 들어 강백호가 선택되면 일련번호가 1인 서태웅이 선택될 확률은 1 / 4이고, 강백호가 선택되지 않으면 서태웅이 선택될 확률은 2 / 4이다.

그러나 전체적으로는 서태웅이 추출될 확률도 2 / 5이다.

서태웅이 추출될 확률
= 강백호가 추출될 확률 (2 / 5) * 1 / 4 + 강백호가 추출되지 않을 확률 (3 / 5) * 2 / 4
= 2 / 20 + 6 / 20
= 2 / 5

이를 C++로 구현하면 다음과 같다.

void genknuth(int m, int n)
{
  for (int i = 0; i < n; i++)
    if ((bigrand() % (n - i) < m) {
      cout << i << "\n";
      m--:
    }
}

솔루션 2

set에 난수를 담는 방법도 있다.

* set에는 동일한 값이 들어 갈 수 없다.

initialize set S to empty
size = 0
while size < m do
  t = bigrand() % n
  if t is not in S
    insert t into S
    size++
print the elements of  S in sorted order

C++ STL을 이용하여 구현하면 다음과 같다.

void gensets(int m, int n)
{
  set<int> S;
  while (S.size() < m)
    S.insert(bigrand() % n);
  set<int>::iterator i;
  for (i < S.begin(); i != S.end(); ++i)
    cout << *i << "\n";
}

솔루션 3

n 개 크기 배열을 만든 후에 이들의 위치를 무작위로 변경(swap)하고 처음 m 개를 선택하는 방법도 있다. 화투나 포카에서 카드를 섞는 것(shuffle)과 유사하다.

for i = [0, n)
  swap(i, randint(i, n - 1))

C++를 구현하면 다음과 같다.

void genshuf(int m, int n)
{
  int i, j;
  int *x = new int[n];
  for (i = 0;; i < n; i++)
    x[i] = i;
  for (i = 0; i < m; i++) {
    j = randint(i, n - 1);
    int t = x[i]; x[i] = x[j]; x[j] = t;
  }
  sort(x, x + m)
  for (i = 0; i < m; i++)
    cout << x[i] << "\n";
}

개념 코드와는 다르게 m개 까지만 swap한다. (Ashley Shepherd와 Alex Woronow)



기타

만약 n이 100만이고 m이 n - 10이라면 조금은 다르게 접근해야 한다. 이 경우에는 추출되지 않을 10개를 계산하는 것이 적합하다.

프로그래밍 혹은 문제 해결은 다음과 같이 진행된다.

1. Understand the Perceived Problem
2. Specify an Abstract Problem
3. Explore the Design Space
4. Implement One Solution
5. Retrospect