프리컴퓨팅

Precomputation
20세기 사전 계산된 공통 로그 수학적 표의 일부.

알고리즘에서 사전 컴퓨팅은 실행 시간 전에 초기 계산을 수행하여 실행될 때마다 반복적인 계산을 피하기 위해 알고리즘이 사용할 수 있는 룩업 테이블을 생성하는 행위다. 사전 컴퓨팅은 알고리즘의 입력에 의존하지 않는 값비싼 계산의 결과에 의존하는 알고리즘에 자주 사용된다. 프리컴퓨팅의 사소한 예로는 런타임에 필요한 정밀도에 대한 근사치를 계산하기보다는 하드코딩된 수학적 상수인 π이나 e를 사용하는 것이다.

데이터베이스에서 materialization이라는 용어는 materialized 뷰와 [1][2]같이 사전 컴퓨팅의 결과를 저장하는 것을 의미하기 위해 사용된다.[3][4]

개요

알고리즘 실행 초기에 일련의 중간 결과를 미리 계산하는 것은 종종 알고리즘 효율을 상당히 증가시킬 수 있다. 이것은 하나 이상의 입력이 결과가 적절한 크기의 메모리 블록에 저장될 수 있을 정도로 충분히 작은 범위로 제한될 때 유리해진다. 메모리 액세스는 본질적으로 시간 복잡성이 일정하기 때문에(캐싱 지연은 제외), 작은 입력 범위에 걸쳐 일정한 효율성보다 낮은 구성요소를 가진 알고리즘은 값을 미리 계산하여 개선할 수 있다. 보간도 선형 연산이기 때문에 값들의 이산형 부분집합을 계산하고 중간 입력 값에 대해 보간함으로써 효율적인 근사 알고리즘을 얻을 수 있는 경우도 있다.

역사

컴퓨터의 출현하기 전에, 값 인쇄된 조회 테이블 사람들에 의해 그러한 삼각 테이블, 로그 테이블 및 통계적 밀도를 functions[5]학교 아이들은 종종 가장 일반적으로 사용되는 숫자의 계산을 피하기 위해"단"를 외우는 것을 배운다에서 복잡한 기능의 손 계산 속도를 높이기 위해 사용되었다.(up ~ 9 x 9 또는 12 x 12). 서기 493년경에도 아키타인의 빅토리아우스는 98열 곱셈표를 써서 (로마 숫자로) 2배에서 50배까지 모든 숫자의 산물을 주었고 행은 "1000부터 시작해서 수백에서 백배까지 내려간 다음, 수십에서 10배까지 내려간 다음, 1배로 내려간 다음 분수가 한다"고 했다.wn ~ 1/4"

예

디지털 삼각함수의 현대적인 컴퓨터 구현조차도 보간 알고리즘에 대한 계수를 제공하거나 연속적인 근사 알고리즘을 초기화하기 위해 사전 계산된 조회 테이블을 사용하는 경우가 많다.

암호 시스템에 대한 많은 공격은 사전 컴퓨팅을 포함한다.

현대 효율적인 알고리즘의 일부로 대규모 사전 컴퓨팅의 예는 다음과 같다.

컴파일러는 결과 코드의 런타임 속도를 높이기 위한 수단으로 광범위하게 프리컴퓨팅을 사용한다. 이 프리컴퓨팅은 사실상 프로그램 코드 자체에 대한 부분 평가의 한 형태로 간주될 수 있다. 이러한 종류의 사전 컴퓨팅의 예로는 데이터 흐름 분석과 강도 감소 단계를 들 수 있다.

참고 항목

참조

  1. ^ Jiawei Han; Micheline Kamber (9 June 2011). Data Mining: Concepts and Techniques: Concepts and Techniques. Elsevier. p. 159. ISBN 978-0-12-381480-7.
  2. ^ Sven Groppe (29 April 2011). Data Management and Query Processing in Semantic Web Databases. Springer Science & Business Media. p. 178. ISBN 978-3-642-19357-6.
  3. ^ Karen Morton; Kerry Osborne; Robyn Sands; Riyaj Shamsudeen; Jared Still (28 October 2013). Pro Oracle SQL. Apress. p. 48. ISBN 978-1-4302-6220-6.
  4. ^ Marie-Aude Aufaure; Esteban Zimányi (16 January 2012). Business Intelligence: First European Summer School, EBISS 2011, Paris, France, July 3-8, 2011, Tutorial Lectures. Springer Science & Business Media. p. 43. ISBN 978-3-642-27357-5.
  5. ^ Campbell-Kelly, Martin; Croarken, Mary; Flood, Raymond; et al., eds. (2003). The History of Mathematical Tables From Sumer to Spreadsheets. Oxford University Press. ISBN 978-0-19-850841-0.
  6. ^ 마허, 데이비드. W. J.와 존 F. 마코프스키. "분수 로만 산술에 대한 문헌 증거", '클래식 문헌학'(2001) 96번 4번(2001) 페이지 376–399(페이지 383페이지 참조