[한 권 컴퓨터 구조와 프로그래밍] 11장 - 성능 향상을 위한 알고리즘 기법

계산을 간소화하는 프로그래밍 트릭

표 찾기

  - 변환

  - 텍스처 매핑

    - MIP 맵 (다중 이미지 배치)

      - MIP 맵에서 가장 가까운 계층에 있는 이미지를 사용해서 계산 또는 그 이미지를 그냥 사용하면

         시간을 상당히 절약 가능

      - 자주 사용할 정보를 미리 계산 (저해상도 텍스쳐)

  - 문자 종류 판별

정수를 사용한 계산 방법

  - 직선

    - 부동소수점 연산은 정수 계산보다 훨씬 느림

  - 곡선 다루기

  - 다항식

재귀적 분할

  - 나선

    - 재귀적 분할 이용

  - 구성적인 기하

    - 쿼드트리는 재귀를 활용한 데이터 구조

  - 시프트와 마스크

    - 쿼드트리의 단점은 데이터가 메모리에서 분산됨, 쿼드트리의 참조 지역성은 나쁨

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

  - 멱급수 근삿값 계산

    - 사인 함수를 계산하기 위한 다른 방법으로 테일러 급수 활용 가능

  - CORDIC 알고리즘

    - 좌표 회전 디지털 컴퓨터 (COordinate Rotation DIgital Computer)

    - 벡터링 모드

    - 회전 모드

    - 표 검색 사용

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

  - 공간을 채우는 곡선

    - 자기 유사성을 보여줌 (프랙탈의 부분 집합)

      - 코흐 눈송이

      - 힐베르트 곡선

  - L 시스템

    - 린덴마이어 시스템

      - 생성 문법 (어떤 것이 생성될지 기술)

      - 자연스러워 보이는 물체 생성하기 좋음

      - 뜨개질 규칙

  - 스토캐스틱 기법

    - 랜덤이라는 말로 충분하지 않을 때 사용하는 용어

  - 양자화

    - 이미지에 있는 색에 대해 변환될 이미지에서 쓸 수 있는 색을 할당해야 함

    - 임계화(thresholding)

    - 망점 인쇄(halftone printing)

      - 이미지를 여러 크기의 점으로 분해

    - 디더링(dithering)

      - 임의의 진동 발생

    - 바이어 필터

      - 바이어 필터를 변형한 바이어 행렬

        - 이미지에 타일링 (x, y축 방향으로 같은 패턴 반복, 배열 디더링)

    - 무아레 패턴

    - 플로이드-스타인버그의 오류 분포 가중치를 이용한 알고리즘

정리