성능 향상을 위한 알고리즘 기법

개요

당연한 말이지만 계산을 효율적으로 하는 것도 중요하지만, 가능하다면 계산을 피하는 것이 더 좋다. 대표적으로 지름길과 근삿값 계산이 있는데, 두 방식에 대해 살펴보자.

표 찾기

특정 계산을 중복적으로 하는 경우 결과를 미리 계산해두고 반복 사용하는 방식이다.

변환

• 자연로그 등이 포함된 부동소수점 계산 같은 경우는 계산 비용이 비싸다.
• 표를 만들어 비용이 비싼 계산 결과를 미리 만들어두면 비싼 계산을 없앨 수 있다.

텍스처 매핑

• 비디오 게임의 이미지를 만들 때 사용되는 텍스처 매핑이 있다.
• 비디오에서의 이미지는 항상 변하지 않는 상태가 아니다.
• 거리 혹은 주변 물체에 따라 달라지기도 한다.
• 이러한 변화에 대한 계산은 빠르게 이루어져야 보는 사람 입장에서 자연스럽다.
• MIP 매핑은 RGB의 낭비되는 비트를 효율적으로 사용하는 방식이다.
• 남는 1/4 공간에 이미지의 1/4크기 복사본을 넣는 것을 반복해 MIP 맵을 만든다.
• 해당 매핑 방식은 피라미드 구조와 같다.
• 피라미드 맨 위에서는 먼 거리의 이미지를, 맨 아래에서는 가장 가까운 거리의 이미지를 보여준다.
• 그래서 사용자가 보는 시점인 뷰포인트에 따라 빠르게 보여줄 수 있다.

문자 종류 판별

• 아스키코드 표를 이용한 효율적인 방법을 라이브러리에 추가했다.
• 비트를 사용하기 때문에 각 비트가 1인지만 확인하면 되서 빠르다.
• 00110100이라면 각 비트는 대문자 ,소문자, 숫자, 16진수, 구두점, 화면 출력 문자, 제어문자, 공백문자 인지에 대한 여부를 의미한다.

정수를 사용한 계산 방법

• 계산 비용 : 덧셈, 뺄셈 < 곱셈, 나눗셈 < 부동소수점 연산
• 비용이 큰 계산을 공식을 활용해 더 적은 비용의 계산으로 최대한 바꿔야 한다.

직선

• 정수만을 사용해 직선을 그리면 계산을 더 효율적으로 할 수 있다.
• 대표적으로 브레슨햄 알고리즘이 있다.
• 직선의 방정식에서 실수 연산 대신 정수 연산만으로 픽셀의 위치를 결정한다.
• 각 단계마다 발생하는 오차를 누적하고, 누적값이 임계값을 넘으면 y좌표를 조정한다.
• 오직 정수의 덧셈과 뺄셈 연산만 사용해 매우 빠르다.

곡선

• 타원 공식은 계산이 복잡해 컴퓨터가 빠르게 처리하기 어렵다.
• 곡선을 다룰 때도 정수를 사용한 계산이 가능하다.
• 차이를 이용하면 쉽게 계산할 수 있다.
• 타원을 한 번에 다 계산하지 않고 한 칸씩 움직이면서 변하는 차이만 계산해서 그린다.
• 즉, 이동하면서 타원에 가까운 칸만 칠한다.
• 수학 공식을 사용하지 않고 바로 전 칸과의 차이만 계산하면 되서 빠르다.

재귀적 분할

큰 문제를 여러 작은 문제로 나누어 처리하는 방법이다.

나선

• 원하는 점들을 계산하고 선으로 이으면 더 복잡한 곡선을 만들 수 있다.
• 극좌표 : 반지름과 각도를 사용하는 좌표계
• 각도를 작게하면 더 촘촘하게 원점 근처가 아니라도 점이 서로 겹쳐서 더 선명한(?) 곡선을 만들 수 있지만 그만큼 느리다.
• 원점에서 멀어질 수록 점 사이 거리가 멀어진다.
• 그린 점과 점 사이에 선을 그어주면 곡선이 그려진다.
• 당연히 원점에서 멀어질수록 점이 촘촘하지 않아 곡선이 삐뚤삐뚤해진다.
• 그래서 필요에 따라(원점에서 먼지에 따라) 더 많은 점을 계산해야 한다.
• 이때 거리 공식을 사용해 점 간의 거리가 먼 경우 재귀적으로 점 간의 거리가 충분히 가까워질 때까지 각도 차이를 반으로 줄이는 작업을 수행한다.

구성적인 기하

• 쿼드트리는 2차원 공간을 네 부분으로 계속해서 분할하는 트리 구조다.
• 그래서 항상 노드의 크기는 상위 노드의 1/4다.
• 노드는 흰색과 검은색 두 가지 값을 갖는다.
• 좌표의 값은 루트 노드부터 시작해 현재 노드가 흰색이나 검은색이면 값을 반환하고, 아니라면 속한 사분면을 찾아 해당 자식 노드로 이동해 재귀적으로 탐색하면 값을 찾는다.
• 값 설정(색 변경 혹은 삭제)도 마찬가지로 재귀적으로 탐색하며 현재 노드가 흰색이나 검은색인지 확인하고, 아니라면 속한 사분면을 찾아 자식 노드로 이동해 값을 설정한다.
• 만약 자식 노드도 모두 같은 색이 되면 부모 노드를 해당 색으로 병합해 트리의 깊이를 줄인다.
• 쿼드트리에 불리언 연산을 수행할 수도 있다.
• NOT 연산을 수행하면 노드의 색을 반전할 수 있다.
• AND 연산을 수행하면 모두 검은색이면 검은색, 하나라도 흰색이면 흰색이 되고, 자식 노드가 있다면 각 사분면별로 재귀적으로 AND 연산을 수행하고, 모든 자식이 동일한 색이 되면 병합한다.
• OR 연산은 하나라도 검은색이면 검은색, 모두 흰색일 때만 흰색이 되고, 마찬가지로 자식 노드에 재귀적으로 OR 연산 수행 후 결과가 동일하면 병합한다.
• 3차원에서는 2차원보다 노드가 2배 더 필요해 쿼드트리를 옥트리로 확장한다.

시프트와 마스크

• 쿼드트리는 데이터가 메모리에 분산되어 참조 지역성이 좋지 않다.
• 비트 단위로 처리할 경우 메모리 접근 횟수가 늘어나 느려진다.
• 접근 횟수를 줄여야만 한다.
• 비트맵 텍스트를 화면에 표시할 때는 각 문자의 비트 패턴을 메모리에 저장하고 원하는 위치에 해당 비트만을 남기거나 덮어쓰는 방식으로 처리해야 한다.
  • 원본 비트맵에서 필요한 비트만 남김
  • 나머지는 마스크로 제거
  • 덮어쓸 위치에 맞게 시프트 연산으로 비트 이동
  • 마스킹된 결과와 새로운 비트 패턴을 OR 연산으로 결합 후 메모리에 기록

계산을 회피하는 그 밖의 수학적 기법들

연산 비용이 비싼 계산을 비용 효율적으로 계산하는 방법도 좋지만, 당연히 계산 자체를 회피하는게 더 좋다.

멱급수 근삿값 계산

• 충분히 가깝다는 원리를 사용한 또 다른 계산 방식이다.
• 멱급수는 함수를 무한한 항의 합으로 표현하는 방법이다.
• 하지만 실제로 무한히 계산할 수는 없으니 몇 개 항만 더해 충분히 정확한 근삿값을 구한다.

CORDIC 알고리즘

• 45도에서 시작해 계산하고 싶은 값보다 작으면 화살표를 더 회전시킨다.
• 크다면 반대로 회전시킨다.
• 위 과정을 반복해 원하는 각도에 도달하게한다.

무작위성과 관련 있는 예제들

• 난수를 만들려면 공식을 사용해야하는데 공식으로 만든 난수는 완전한 난수일 수가 없다.
• 하지만 크립토그래피를 제외한 대부분의 계산 작업에서는 완전한 난수가 아니여도 괜찮다.
• 의사 난수성을 활용한 근삿값 계산 방법을 알아보자.

공간을 채우는 곡선

• 여러 방향으로 반복되는 패턴의 곡선으로 반복될 때마다 더 많은 공간을 채운다.
• 곡선들은 자기 유사성을 갖고, 프랙탈 집합의 부분집합이다.
• 대표적으로 힐베르트 곡선이 있다.

L 시스템

• 어떤 것이 생성될지를 기술하는 생성 문법이다.
• 예를 들면 힐베르트 곡선 규칙에 사용한 규칙은 어떤 패턴을 생성하는지 기술한다.

스토캐스틱 기법

• 랜덤보다 더 랜덤한 것
• 임의성을 추가해 다양성을 높이는 기법이다.

양자화

• 컬러를 흑백으로 표현하는 경우처럼 색에 대한 근삿값을 구하지 못하고 최대한 열심히 흑백으로 표현해야 할 때 양자화가 필요하다.
• 즉, 원래 표현할 색(컬러)을 대체할 색(흑백)을 할당하는 작업이다.
• 임계값을 정해 그보다 더 밝은 값을 흰색, 어두운 값을 검은색으로 지정하는 임계화를 진행한다.
• 그후 망점 인쇄를 통해 이미지를 여러 크기의 점으로 분해한다.
• 다음으로 해상도를 희생해 색이나 명암을 인식할 수 있게 하는 트레이드 오프 작업인 디더링을 진행한다.
• 디더링 알고리즘으로 대표적인 것은 바이어 행렬을 사용한 타일링 패턴이다.

후기

와…