[C++] Algorithms and Lifting

함수 템플릿은 다양한 데이터 유형에 대한 작업을 수행하고 해당 작업을 구현하기 위해 인수로 전달된 다양한 작업을 사용할 수 있다는 점에서 일반 함수를 일반화한 것이다. 알고리즘은 문제를 해결하기 위한 절차 또는 공식이다. 결과를 생성하기 위한 유한한 일련의 계산 단계다. 따라서 함수 템플릿을 종종 알고리즘이라고 한다. 특정 데이터에 대해 특정 작업을 수행하는 함수에서 다양한 데이터 유형에 대해 보다 일반적인 작업을 수행하는 알고리즘으로 어떻게 이동할까? 좋은 알고리즘을 얻는 가장 효과적인 방법은 하나의 구체적인 예에서 일반화하는 것이다. 이러한 일반화를 Lifting이라고 한다. 즉, 이러한 일반화를 Lifting이라고 한다. 성과를 유지하고 합리적인 것을 주시하면서 구체적인 것에서 추상적인 것으로 나아가는 것이 중요하다. 

Lifting의 과정을 알아보자.

double add_all(double∗ array, int n)
	// one concrete algorithm on array of doubles
{
	double s {0};
	for (int i = 0; i<n; ++i)
		s = s + array[i];
	return s;
}

분명히 이것은 인수 배열의 합을 계산한다.

struct Node {
	Node∗ next;
	int data;
};

int sum_elements(Node∗ first, Node∗ last)
	// another concrete algorithm on list of ints
{
	int s = 0;
	while (first!=last) {
		s += first−>data;
		first = first−>next;
	}
	return s;
}

이것은 Node에 의해 구현된 단일 연결 목록의 정수 합계를 계산한다.

이 두 코드 조각은 세부 사항과 스타일이 다르지만 숙련된 프로그래머는 즉시 "이것은 누적 알고리즘의 두 가지 구현일 뿐이다'라고 말할 것이다. 이것은 인기 있는 알고리즘이다. 가장 널리 사용되는 알고리즘과 마찬가지로 이 알고리즘에는 reduce, fold, sum 및 집계를 비롯한 많은 이름이 있다. 그러나 두 가지 구체적인 예에서 단계적으로 일반적인 알고리즘을 개발하여 들어 올리는 과정에 대한 감을 느끼도록 하자. 먼저 데이터 유형을 추상화하여 다음 항목에 대 구체적이지 않도록 한다.

• double vs int, or
• array vs linked list.

// pseudo code:
T sum(data)
// somehow parameter ize by the value type and the container type
{
	Ts=0
	while (not at end) {
		s = s + current value
		get next data element
	}
	return s
}

이를 구체화하기 위해 '컨테이너' 데이터 구조에 액세스 하는 세 가지 작업이 필요하다.

• Not at end
• Get current value
• Get next data element

실제 데이터의 경우 세 가지 작업도 필요하다.

• Initialize to zero
• Add
• Return the result

분명히 이것은 다소 부정확하지만 코드로 변환할 수 있다.

// concrete STL-like code:
template<typename Iter, typename Val>
Val sum(Iter first, Iter last)
{
	Val s = 0;
	while (first!=last) {
		s=s+ ∗first;
		++first;
	}
	return s;
}

여기에서 일련의 값을 나타내는 일반적인 STL 방법을 활용하자. 시퀀스는 세 가지 작업을 지원하는 한 쌍의 반복자로 표시된다.

• * : 현재 값에 액세스 하기 위해
• ++ : 다음 요소로 이동하기 위한 ++
• != : 시퀀스의 끝에 있는지 확인하기 위해 반복자를 비교

이제 배열과 연결 목록, int와 double 모두 사용할 수 있는 알고리즘(함수 템플릿)이 있다. double*이 반복자의 예이기 때문에 배열 예는 즉시 작동한다.

double ad[] = {1,2,3,4};
double s = sum<double∗>(ad,ad+4);

손으로 만든 단일 연결 목록을 사용하려면 반복자를 제공해야 한다. 몇 가지 작업이 주어지면 Node*가 반복자가 될 수 있다.

struct Node { Node∗ next; int data; };

Node∗ operator++(Node∗ p) { return p−>next; }
int operator∗(Node∗ p) { return p−>data; }
Node∗ end(lst) { return nullptr; }

void test(Node∗ lst)
{
	int s = sum<int∗>(lst,end(lst));
}

nullptr을 끝 반복자로 사용한다. 호출자가 누산기 변수에 사용할 유형을 지정할 수 있도록 명시적 템플릿 인수 (여기서는 <int>)를 사용한다.

지금까지 가지고 있는 것은 많은 실제 코드보다 더 일반적이다. 예를 들어, sum()은 부동 소수점 숫자 목록(모든 정밀도), 정수 배열(모든 범위) 및 vector <char>와 같은 다른 많은 유형에 대해 작동한다. 중요하게도 sum()은 직접 만든 함수만큼 효율적이다. 성능을 희생하여 일반성을 달성하면 안 된다.

숙련된 프로그래머는 sum()을 더 일반화할 수 있음을 알 수 있다. 특히 템플릿 인수를 추가로 사용하는 것은 어색하고 초기 값 0이 필요했다. 호출자가 초기 값을 제공한 다음 Val을 추론하도록 하여 이 문제를 해결할 수 있다.

template<typename Iter, typename Val>
Val accumulate(Iter first, Iter last, Val s)
{
	while (first!=last) {
		s=s+ ∗first;
		++first;
	}
	return s;
}

double ad[] = {1,2,3,4};
double s1 = accumulate(ad,ad+4,0.0); // accumulate in a double
double s2 = accumulate(ad,ad+4,0); // accumulate in an int

근데 왜 +일까? 때때로 요소를 곱하고 싶을 때가 있다. 사실, 시퀀스의 요소에 적용하고 싶은 연산이 꽤 있다. 이것은 추가 일반화로 이어진다.

template<typename Iter, typename Val, typename Oper>
Val accumulate(Iter first, Iter last, Val s, Oper op)
{
	while (first!=last) {
		s = op(s,∗first);
		++first;
	}
	return s;
}

이제 인수 op를 사용하여 요소 값을 누산기와 결합한다.

double ad[] = {1,2,3,4};
double s1 = accumulate(ad,ad+4,0.0,std::plus<double>); // as before
double s2 = accumulate(ad,ad+4,1.0,std::multiply<double>);

표준 라이브러리는 더하기 및 곱하기와 같은 일반적인 연산을 인수로 사용할 함수 개체로 제공한다. 여기에서 호출자가 초기 값을 제공하도록 하는 유틸리티를 볼 수 있다. 0과 *는 누적을 위해 잘 어울리지 않는다. 표준 라이브러리는 사용자가 'add'의 결과와 누산기를 결합하기 위해 =에 대한 대안을 제공할 수 있도록 하는 accumulate()의 추가 일반화를 제공한다.

Lifting은 응용 분야에 대한 지식과 약간의 경험이 필요한 기술이다. 알고리즘 설계를 위한 가장 중요한 단일 지침은 알고리즘 사용을 저해하는 기능 (표기법 또는 런타임 비용)을 추가하지 않고 구체적인 예제에서 알고리즘을 Lifting 하는 것이다. 표준 라이브러리 알고리즘은 성능 문제에 많은 주의를 기울여 수행한 Lifting의 결과다.