순서가 있으면 집합 연산이 건너뛸 일을 알 수 있다.
집합을 오름차순 리스트로 저장하면 포함 검사는 목표를 지나친 순간 멈출 수 있고 합집합은 앞부분을 다시 훑지 않고 두 리스트를 합칠 수 있습니다.
생각해 볼 질문
집합 표현이 오름차순을 약속할 때 어떤 일을 더 하지 않아도 될까요?
- 오름차순을 표현 불변식으로 다루기
- 처음으로 목표보다 큰 항목을 만나면 포함 검사 멈추기
- 두 집합의 머리를 비교한 뒤 한쪽 또는 양쪽 꼬리로 진행하기
- 중복을 없애면서 합집합의 정렬 순서 유지하기
element-of-ordered-set?는 목표와 현재 머리를 비교합니다. 같으면 성공하고 목표가 더 작으면 즉시 실패하며 목표가 더 클 때만 꼬리를 방문합니다. 그래서 4를 찾을 때 1과 3과 5는 확인하지만 7과 9까지 가지 않습니다.
union-ordered-set은 두 머리를 비교합니다. 더 작은 값을 남기고 그 리스트만 진행하며 머리가 같으면 값 하나만 남기고 양쪽을 모두 진행합니다. 재귀 단계마다 현재 머리 하나 이상을 소비하므로 처음부터 다시 찾지 않고 정렬 순서를 유지합니다.
(begin
(define checks 0)
(define (element-of-ordered-set? item set)
(if (null? set)
#f
(begin
(set! checks (+ checks 1))
(cond ((= item (car set)) #t)
((< item (car set)) #f)
(else
(element-of-ordered-set? item (cdr set)))))))
(list (element-of-ordered-set? 4 '(1 3 5 7 9))
checks))리스펙스 학습용 런타임리스펙스 SICP 프로필 1.0.0
리스펙스 SICP 런타임 불러오는 중
리스펙스 · SICP 코드UTF-8 385 / 1,048,576바이트
예제
결과—
- 출력
- —
- 값
- —
- 진단
- —
보이는 실행 흐름0 / 0 개의 실행 이벤트
첫 프로그램은 (#f 3)을 반환합니다. 두 번째 프로그램은 (1 2 3 5 6 8 9)를 반환합니다.
포함 검사를 7과 9 전에 끝내는 5와의 비교를 찾으세요. 합집합에서는 머리를 비교할 때마다 왼쪽이나 오른쪽 또는 양쪽이 소비되면서 결과가 오름차순으로 남는지 살펴보세요. 이 실행 흐름은 입력이 이미 정렬된 집합이라는 조건에서만 이번 실행을 설명합니다.
힌트를 보기 전에 프로그램을 바꿔 보세요.
같은 두 머리 비교를 사용해 intersection-ordered-set을 작성하세요. 합집합 예제의 두 입력에 대한 교집합을 예상해 보세요.
힌트 하나 보기
두 머리가 같을 때만 값을 남기고 다르면 더 작은 머리를 버리세요.