복합 데이터: 종합과 도전 과제

단원에서 이룬 것

이 단원은 데이터의 컬렉션을 표현하고 기본 알고리즘으로 처리하는 법을, 그 비용을 추정하면서 가르치려 했다. 이 목적은 도입 수업이 이미 아는 것으로 선언한 것에만 기대어 이루어졌다. 불변식을 갖춘 반복문, 함수와 그 전달 방식, 정수의 산술이다. 변수 다섯 개로 남는 데이터를 말없이 버리던 점수 프로그램은 이제 벡터로 쓰인다. 또 모든 쌍을 살피면 백만 개의 데이터에 몇 분이 걸리던 동점의 물음에는, 정렬한 뒤 이웃끼리 비교하여 답한다.

배열

배열 수업은 크기가 고정된 시퀀스인 std::array 타입을 소개했다. 그 인덱스는 오프셋이므로 0부터 센다. 인덱스 $i$의 값이 유효한 것은 $0 \leq i < n$일 때, 그리고 그때에만이라는 것, [] 연산자로 하는 접근마다 이를 반복문의 불변식으로 증명해야 한다는 것, 그리고 범위를 벗어난 접근은 정의되지 않은 동작이며 .at() 함수가 그것을 정해진 중단으로 바꾼다는 것을 확립했다. 또 std::size_t 타입을 도입하고, C 배열을 읽는 법을 가르쳤다.

벡터

벡터 수업은 push_back 함수로 늘어나는 시퀀스를 소개하고, 데이터의 열을 저장해야 하는 때를 정했다. 어떤 데이터에 대한 결정이 뒤의 데이터에 달려 있을 때다. 표준 순회(누적, 필터링, 변환)를 그 불변식과 라이브러리의 약식 표기(std::ranges::count, std::ranges::max, std::ranges::fold_left)와 함께 확립했고, 벡터의 전달 규칙과 크기와 용량의 차이를 보였다. 이 차이에서 push_back 함수의 평균 상수 비용과, 벡터가 이사할 때 참조가 무효화되는 일이 나온다.

알고리즘의 비용

알고리즘의 비용 수업은 두 번째 물음을 더했다. 최악의 경우에 지배적 연산을 세는 것, 증가 차수로 분류하는 것, $n$의 값을 두 배로 할 때의 효과를 예측하는 것, 그리고 std::chrono::steady_clock 시계로, 최적화를 켜고 새니타이저 없이, 되풀이하여 중앙값을 취하며 측정하는 것이다.

탐색과 정렬

탐색과 정렬 수업은 이진 탐색을 그 불변식과 척도로 정당화했고, 선택 정렬과 삽입 정렬을 작성하여 그 비교 횟수를 셌으며, 범위 라이브러리의 알고리즘을 아무도 검사하지 않는 정렬된 상태라는 사전 조건과 함께 소개했고, 탐색하기 전에 정렬하는 편이 나은 때를 계산했다.

표

표 수업은 표를 행 단위와 열 단위로 순회했고, 전치와 행렬의 곱을 그 삼차 비용과 함께 계산했으며, 가장자리를 벗어나지 않고 이웃 칸을 셌고, 인덱스 $i \cdot \mathit{columns} + j$의 식으로 표를 평탄화한 벡터에 저장했다.

레코드

레코드 수업은 병렬 벡터를 각 필드에 초깃값이 있는 struct 타입으로 바꾸었다. 레코드를 전달하고 반환하는 법, 프로젝션을 써서 필드 하나로 레코드를 정렬하고 탐색하는 법, std::ranges::stable_sort 함수로 여러 기준에 따라 정렬하는 법, 그리고 레코드와 벡터를 담은 레코드로 문제를 모델링하는 법을 가르쳤다.