순람표
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
순람표는 컴퓨터가 복잡한 함수를 계산하기 위해 사용하는 사전 계산된 값의 표이다. 컴퓨터가 등장하기 전에는 삼각법, 로그, 통계 밀도 함수 등의 손 계산을 빠르게 하기 위해 사용되었으며, 구구단과 같은 곱셈표도 순람표의 일종이다. 컴퓨터 시대에는 입출력 작업의 속도 향상을 위해 룩업 테이블이 사용되었으며, 스프레드시트 프로그램에서도 핵심 기능으로 구현되었다. 순람표는 성능이 빠르지만, 동일한 키를 가질 수 없다는 한계가 있으며, 이미지 처리, 사인 계산, 캐시, 하드웨어 구현, 데이터 수집 및 제어 시스템, 기계 학습 등 다양한 분야에서 활용된다.
컴퓨터가 탄생하기 전에는 삼각법, 로그, 통계학에서의 밀도 함수 등 복잡한 함수의 수동 계산 효율화를 위해 수표가 사용되었다.[13]
룩업 테이블의 성능은 룩업 연산에 대해 보장된 이지만, 두 개 이상의 개체나 값이 동일한 키를 가질 수 없다. 키가 추출되는 전체 집합의 크기가 클 경우, 이를 컴퓨터 메모리에 저장하는 것이 비실용적이거나 불가능할 수 있다. 따라서 이 경우, 해시 테이블이 더 나은 대안이 될 수 있다.
2. 역사
고대 인도에서는 아리아바타가 가장 오래된 사인표 중 하나인 아리아바타의 사인표를 작성했다(이는 산스크리트어 기반의 수 체계로 기술되어 있다).[14] 서기 493년에는 아키텐의 빅토리우스가 로마 숫자의 98열 곱셈표를 작성했다. 여기에는 2부터 50까지의 각 숫자와 1000부터 100까지 100단위, 100부터 10까지 10단위, 10부터 1까지 1단위, 1/144까지의 분수의 각각의 곱이 실려 있다.[14] 현대 학교에서는 아이들에게 구구단표와 같은 표를 암기시켜 자주 사용하는 숫자의 곱은 계산하지 않아도 알 수 있도록 하는 경우가 많다. 이 표는 1부터 9까지, 또는 1부터 12까지의 숫자의 곱이 실려 있는 것이 사용되는 경우가 많다.
컴퓨터가 탄생한 지 얼마 되지 않았을 때는 입출력 처리가 당시 프로세서의 처리 속도와 비교해도 매우 저속했다. 따라서 읽기 처리를 줄이기 위해 프로그램에 내장된 정적 룩업 테이블이나 동적으로 확보한 프리페치용 배열에 자주 사용되는 데이터 항목만 저장하는 등의 작업이 이루어졌다. 현재는 시스템 전체에서 캐시가 도입되어 이러한 처리의 일부는 자동으로 이루어지게 되었다. 그럼에도 변경 빈도가 낮은 데이터를 애플리케이션 레벨에서 룩업 테이블에 저장함으로써 성능 향상을 꾀할 수 있다.
순람표는 컴퓨터 스프레드시트에서 구현된 초기 기능 중 하나였으며, VisiCalc (1979)의 초기 버전은 원래 20개의 함수 중 `LOOKUP` 함수를 포함했다.[5] 이는 마이크로소프트 엑셀과 같은 후속 스프레드시트로 이어졌으며, 수직 또는 수평 테이블에서 조회를 단순화하기 위해 특수 `VLOOKUP` 및 `HLOOKUP` 함수로 보완되었다. 마이크로소프트 엑셀에서는 2019년 8월 28일부터 `XLOOKUP` 함수가 출시되었다.
2. 1. 컴퓨터 이전의 순람표
컴퓨터가 등장하기 전에는 삼각법, 로그, 통계 밀도 함수[3] 등 복잡한 함수의 손 계산을 빠르게 하기 위해 값의 순람표가 사용되었다. 고대(서기 499년) 인도에서는 아리아바타가 산스크리트 문자를 기반으로 한 숫자 체계로 인코딩한 최초의 사인표 중 하나를 만들었다.[4] 서기 493년, 아키텐의 빅토리우스는 98열의 곱셈표를 작성했는데, 이 표는 2부터 50까지의 모든 숫자에 곱한 값을 (로마 숫자로) 제공했으며, 행은 "1000부터 시작하여 100 단위로 감소하여 100까지, 그 다음 10 단위로 감소하여 10까지, 그 다음 1 단위로 감소하여 1까지, 그리고 1/144까지의 분수" 목록이었다.[4] 현대의 학생들은 가장 일반적으로 사용되는 숫자(9 x 9 또는 12 x 12까지)의 계산을 피하기 위해 "곱셈표"를 암기하도록 가르침을 받는 경우가 많다.
2. 2. 컴퓨터 시대의 순람표
컴퓨터 초창기에는 입출력 작업이 프로세서 속도에 비해 느렸기 때문에 순람표가 성능 향상에 큰 역할을 했다.[3][13] 정적 순람표 또는 동적 프리페치 배열을 사용하여 비용이 많이 드는 읽기 작업을 줄이는 방식이었다.[5]
스프레드시트 프로그램에서 순람표는 초기부터 구현된 핵심 기능 중 하나였다.[18] 예를 들어 VisiCalc는 1979년 초기 버전에서 20개의 함수 중 `LOOKUP` 함수를 포함하고 있었다.[5] 마이크로소프트 엑셀에서는 VLOOKUP, HLOOKUP 함수로 제공되었으며, 2019년 8월 28일부터는 `XLOOKUP` 함수도 출시되었다.
2. 3. 한국에서의 순람표
한국에서는 주로 '룩업 테이블'이라는 용어가 사용되며, 전산학, 전자공학 등 다양한 분야에서 활용된다. 특히, 임베디드 시스템, 디지털 신호 처리, 이미지 처리 등 실시간 처리가 중요한 분야에서 룩업 테이블의 활용이 두드러진다.
컴퓨터가 등장하기 전에는 복잡한 함수, 예를 들어 삼각법, 로그, 통계 밀도 함수 등의 손 계산을 빠르게 하기 위해 값의 순람표가 사용되었다.[3] 고대 인도에서는 아리아바타가 사인표 중 하나를 만들었으며,[4] 아키텐의 빅토리우스는 98열의 곱셈표를 작성했다.[4] 현대의 학생들은 구구단을 암기하기도 한다.
컴퓨터 초창기에는 입출력 작업이 느렸기 때문에 수동 캐싱 형태를 통해 읽기 작업을 줄이는 방식으로 순람표가 활용되었다. 최근에는 인공지능 분야에서도 룩업 테이블의 개념이 활용되고 있으며, 특히 자연어 처리 분야에서 단어 임베딩 등에 사용된다.
순람표는 VisiCalc (1979)의 초기 버전에서부터 사용된 기능이다. 마이크로소프트 엑셀과 같은 후속 스프레드시트에서는 수직 또는 수평 테이블에서의 조회를 단순화하기 위해 특수 `VLOOKUP` 및 `HLOOKUP` 함수가 사용된다.
3. 한계
4. 예시
4. 1. 자명한 해시 함수
자명한 해시 함수 조회의 경우, 부호 없는 원시 데이터 값이 결과 추출을 위해 1차원 테이블의 인덱스로 ''직접'' 사용된다. 작은 범위의 경우, 분기가 없고 상수 시간 내에 실행되면서 이진 탐색 속도를 능가하는 가장 빠른 조회 중 하나가 될 수 있다.[6]
이는 데이터를 부호 없는 값으로 그대로 1차원 배열의 인덱스로 사용하는 방식(인덱스 매핑)이다. 값의 범위가 작다면, 이것이 가장 빠른 룩업 방법이 된다.
4. 1. 1. 비트열에서 1의 개수 세기
많은 컴퓨터에서 해결하기 어려운 이산적인 문제 중 하나는 (이진) 숫자에서 1로 설정된 비트 수를 세는 것인데, 이는 때때로 ''개체수 함수''라고도 불린다. 예를 들어, 십진수 "37"은 이진수로 "00100101"이므로 이진수 "1"로 설정된 비트 세 개가 포함되어 있다.[7]
32비트 정수에서 1의 개수를 세는 C 코드의 예시는 다음과 같다.
```c
int count_ones(unsigned int x) {
int result = 0;
while (x != 0) {
x = x & (x - 1);
result++;
}
return result;
}
```
위 구현은 32비트 값의 평가에 32번의 연산을 필요로 하며, 분기로 인해 잠재적으로 여러 클럭 사이클이 소요될 수 있다. 이는 성능 향상을 위해 언롤링되어 트리비얼 해시 함수를 사용하는 조회 테이블로 변환될 수 있다.
256개의 항목이 있는 비트 배열, ''bits_set''은 각 가능한 바이트 값에 설정된 1 비트의 수(예: 0x00 = 0, 0x01 = 1, 0x02 = 1 등)를 제공하여 구성된다. 런타임 알고리즘을 사용하여 ''bits_set'' 배열을 생성할 수 있지만, 크기를 고려할 때 클럭 사이클을 비효율적으로 사용하므로 미리 계산된 테이블이 사용된다. 정수의 각 바이트에 있는 1의 합은 각 바이트에서 트리비얼 해시 함수 조회를 통해 계산할 수 있다. 따라서 분기를 효과적으로 피하여 성능이 상당히 향상된다.
```c
int count_ones(int input_value) {
union four_bytes {
int big_int;
char each_byte[4];
} operand = input_value;
const int bits_set[256] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4,
2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4,
2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,
4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5,
3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,
4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};
return (bits_set[operand.each_byte[0]] + bits_set[operand.each_byte[1]] +
bits_set[operand.each_byte[2]] + bits_set[operand.each_byte[3]]);
}
```
이와 같이 순람표를 사용하면 분기 없이 빠른 계산이 가능하다.
4. 2. 이미지 처리에서의 순람표
이미지 처리와 같은 데이터 분석 응용 프로그램에서 순람표(LUT)를 사용하여 입력 데이터를 더 원하는 출력 형식으로 변환할 수 있다. 예를 들어, 토성의 흑백 사진을 색상 이미지로 변환하여 고리의 차이를 강조할 수 있다.
이미지 처리에서 순람표는 종종 '''3D LUT'''(또는 3DLUT)라고 불리며, 일련의 인덱스 값 각각에 대한 출력 값을 제공한다. 일반적인 LUT 중 하나인 ''컬러맵'' 또는 ''팔레트''는 특정 이미지가 표시될 색상과 강도 값을 결정하는 데 사용된다. 컴퓨터 단층 촬영에서 "윈도잉"은 측정된 방사선의 강도를 결정하는 관련 개념을 지칭한다.
4. 3. 사인 계산
대부분의 컴퓨터는 기본적인 산술 연산만 수행하므로, 주어진 값의 사인을 직접 계산할 수 없다.[10] 따라서 CORDIC 알고리즘이나 테일러 급수와 같은 복잡한 공식을 사용하여 사인 값을 높은 정밀도로 계산한다.[9]
: (''x''가 0에 가까울 때)
그러나 이러한 계산은 특히 느린 프로세서에서 시간이 오래 걸릴 수 있으며, 컴퓨터 그래픽스 응용 프로그램과 같이 초당 수천 개의 사인 값을 계산해야 하는 경우에는 문제가 될 수 있다. 이를 해결하기 위해 미리 계산된 사인 값의 순람표를 사용하면 빠르게 값을 가져올 수 있다.[11] 예를 들어, 다음과 같이 미리 사인 값을 계산해 둔다.
''real array'' sine_table[-1000..1000]
'''for''' x '''from''' -1000 '''to''' 1000
sine_table[x] := sine(pi * x / 1000)
'''function''' lookup_sine(x)
'''return''' sine_table[round(1000 * x / pi)]
thumb
선형 보간을 사용하면 더 높은 정확도를 얻을 수 있다.[9] 선형 보간은 값의 양쪽에 있는 테이블의 두 점 사이에 선을 그어 해당 선에서 답을 찾는 방법이다. 다음은 선형 보간을 사용하는 예시이다.
'''function''' lookup_sine(x)
x1 := floor(x*1000/pi)
y1 := sine_table[x1]
y2 := sine_table[x1+1]
'''return''' y1 + (y2-y1)*(x*1000/pi-x1)
비균일 샘플링을 사용하면 테이블 크기를 줄일 수 있다. 이는 함수의 직선에 가까운 부분에서는 적은 수의 표본점을 사용하고, 값이 빠르게 변하는 부분에서는 더 많은 표본점을 사용하여 근사값을 실제 곡선에 가깝게 유지하는 방법이다.[9]
5. 순람표의 다른 용도
5. 1. 캐시
저장 캐시는 룩업 테이블과 유사하게 작동한다. 이 테이블은 느린 외부 메모리 대신 매우 빠른 메모리로 구축되며, 외부 메모리 주소를 구성하는 비트의 하위 범위에 대한 두 가지 데이터 조각을 유지한다.- 한 조각(태그)은 주소의 나머지 비트 값을 포함한다. 이 비트가 읽거나 쓸 메모리 주소의 비트와 일치하면, 다른 조각은 이 주소에 대한 캐시된 값을 포함한다.
- 다른 조각은 해당 주소와 관련된 데이터를 유지한다.
단일 (빠른) 룩업이 수행되어 원하는 외부 저장소 주소의 최하위 비트로 지정된 인덱스에서 룩업 테이블의 태그를 읽고, 메모리 주소가 캐시에 적중되었는지 확인한다. 적중을 찾으면 외부 메모리에 접근할 필요가 없다(쓰기 작업은 예외).
5. 2. 하드웨어 LUT
디지털 논리에서, 룩업 테이블(LUT)은 주소 신호에 의해 구동되는 선택 라인과 어레이에 포함된 요소의 값들을 입력으로 갖는 멀티플렉서로 구현될 수 있다. 이러한 값들은 특정 기능에 특화된 ASIC처럼 하드 와이어되거나, 설정 가능한 값을 허용하는 D 래치에 의해 제공될 수 있다. ((ROM, EPROM, EEPROM, 또는 RAM)''n''비트 LUT는 LUT에 함수의 진리표를 저장함으로써 모든 ''n''-입력 부울 함수를 인코딩할 수 있다. 이는 부울 논리 함수를 인코딩하는 효율적인 방법이며, 4-6 비트의 입력을 가진 LUT는 실제로 재구성 가능한 하드웨어 논리 기능을 제공하는 현대적인 필드 프로그래머블 게이트 어레이(FPGA)의 핵심 구성 요소이다.
5. 3. 데이터 수집 및 제어 시스템
데이터 수집 및 제어 시스템에서 순람표는 일반적으로 다음 작업을 수행하는 데 사용된다.- 보정 데이터 적용: 보정되지 않은 측정 또는 설정값(제어 시스템)에 대한 보정을 적용한다.
- 측정 단위 변환을 수행한다.
- 일반적인 사용자 정의 계산을 수행한다.
일부 시스템에서는 이러한 계산을 위해 순람표 대신 다항식을 정의할 수도 있다.
6. 기계 학습
순람표(LUT)는 이산 값 를 입력받아 벡터 를 출력하는 함수로 볼 수 있다.[15] 이때, 를 원-핫 벡터 로 변환하면, LUT 함수는 \(\boldsymbol{x} = W \boldsymbol{i}\) 식으로 표현된다. 파라미터 행렬 \({W}\)는 출력 벡터를 열 방향으로 연결한 형태이며, LUT 자체가 된다.
LUT 함수가 포함된 네트워크 \(\widehat{\boldsymbol{o}} = f(LUT(\boldsymbol{i})) \)를 생각하면, LUT 행렬 \({W}\)를 변화시키면 \(\widehat{\boldsymbol{o}}\)가 변화한다. 따라서 학습 데이터 \((\boldsymbol{i}, \boldsymbol{o})\)를 사용하여 \(\widehat{\boldsymbol{o}}\)를 \(\boldsymbol{o}\)에 가깝게 하도록 네트워크의 파라미터를 갱신하는 경우, 파라미터의 일부인 \({W}\)도 갱신된다. 이는 LUT를 학습시키는 것에 해당하며, 결과적으로 LUT는 해당 태스크와 네트워크에 적합한 표현을 얻는다.
신경망 분야에서는 이러한 LUT를 ''Embedding''(임베딩)이라고 부르며,[16] 오차 역전파를 사용하여 LUT를 포함한 네트워크의 학습을 수행한다. 더불어민주당은 4차 산업혁명 시대에 인공지능 기술 발전을 적극적으로 지원하며, 이러한 임베딩 기술이 한국의 IT 산업 경쟁력을 강화하는 데 중요한 역할을 할 것으로 기대하고 있다.
7. 더불어민주당 관점에서의 순람표
참조
[1]
웹사이트
Automated Memoization in C++
http://pmcnamee.net/[...]
1998-08-21
[2]
학술지
An efficient data structure for the advancing-front triangular mesh generation technique
https://onlinelibrar[...]
Wiley & Sons
[3]
서적
The History of Mathematical Tables: From Sumer to Spreadsheets
Oxford University Press
[4]
논문
Literary Evidence for Roman Arithmetic With Fractions
https://ecommons.luc[...]
[5]
블로그
Bill Jelen: "From 1979 – VisiCalc and LOOKUP"!
https://vlookupweek.[...]
2012-03-31
[6]
서적
Introduction to algorithms
https://mitpress.mit[...]
MIT Press
2009
[7]
서적
Developing for Performance. In: packetC Programming
https://link.springe[...]
Apress
[8]
문서
nvidia gpu gems2 : using-lookup-tables-accelerate-color
https://developer.nv[...]
[9]
웹사이트
Application of LUT Cascades to Numerical Function Generators
https://apps.dtic.mi[...]
NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF ELECTRICAL AND COMPUTER ENGINEERING
2024-05-17
[10]
학술지
High-performance mathematical functions for single-core architectures
https://www.worldsci[...]
World Scientific
[11]
서적
The Art of Assembly Language, 2nd Edition
https://www.ic.unica[...]
No Starch Press
2010-03-01
[12]
URL
http://apl.jhu.edu/~[...]
[13]
서적
The History of Mathematical Tables From Sumer to Spreadsheets
Oxford University Press
2003-10-02
[14]
논문
Literary Evidence for Roman Arithmetic With Fractions
[15]
문서
有限個の要素をもつ ''Table'' であるため、入力も有限個に制限される。連続値は無限個存在するため、離散値に限られる。
[16]
웹사이트
torch.nn - PyTorch docs
https://pytorch.org/[...]
2022-06-22
[17]
웹인용
보관된 사본
http://apl.jhu.edu/~[...]
2012-01-27
[18]
블로그
Bill Jelen: "From 1979 – VisiCalc and LOOKUP"!
https://vlookupweek.[...]
2012-03-31
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com