Praying: 컴퓨터 프로그램의 구조와 해석(1) 2장 2

2.3 글자(기호) 데이터

2.3.1 따옴표 연산

글자를 데이터처럼 다루고자 한다면, 글자 자체를 데이터로 "인용할" 표현수단을 도입해야한다.

=> (list a b) 라는 식을 만든다면 'a'와 'b'라는 '문자'가 list에 대입되는 것이 아니라
a와 b에 존재하는 변수를 대입한다.

=> 이러한 이유로 ' '를 통해 문자를 데이터화한다.
ex)
(list 'a 'b) -> (a b)
==> 자연어와 다른 점: 글자 데이터 앞에 하나만 친다
(define b 2)
(list 'a b) -> (a 2)

(car '(a b c)) -> (car (quote a b c)) -> a

(cdr '(a b c)) -> (cdr (quote a b c)) -> (b c)

* '() == nil

글자 데이터 기본 연산: eq?(글자 두개 비교)
ex)
(define (memq item x)
(cond ((null? x) false)
((eq? item (car x)) x)
(else (memq item (cdr x)))))

2.3.2 연습: 글자 식의 미분
ex) a*x^2+b*x+c

요약된 데이터로 미분하는 프로그램 짜기

가정)
모든 식이 오로지 덧셈식과 곱셈식만으로 이루어져 있다.

식을 미분하는 규칙)
1. 상수를 미분하면 0, x를 미분하면 1
2. 분배 법칙
3. d(u*v)/dx = u*(dv/dx)+v*(du/dx)

=> 2, 3번 규칙은 재귀 정의다. 아무리 높은 차수의 미분방정식이 있다하더라도 2, 3번 규칙을 반복적으로 사용하다보면 결국 미분결과로서 0 or 1 이 나오게 된다.(1번)

(define (deriv exp var) //deriv 미분방정식 미분변수
(cond ((number? exp) 0) //상수인가?
((variable? exp) //변수인가?
(if? (same-variable? exp var) 1 0)) //밑과 지수가 각각 1과 0인가?
((sum? exp) //덧셈식인가?
(make-sum (deriv (addend exp) var) //식에서 가수를 골라낸 후 미분
(deriv (augend exp) var))) //식에서 피가수를 골라낸 후 미분
((product? exp) //곱셈식인가?
(make-sum
(make-product (multiplier exp) //식에서 곱수를 골라낸다
(deriv (multiplicand exp) var)) //식에서 피곱수를 골라낸 후 미분
(make-product (deriv (multiplier exp) var) //식에서 곱수를 골라낸 후 미분
(multiplicand exp)))) //식에서 피곱수를 골라낸다.
(else
(error "unknown expression type -- DERIV" exp))))

대수식 표현하기
// (+ (* a x) b)를 ax + b로 표현하기

(define (variable? x) (symbol? x)) -> 단순한 기호 인가 변수인가?

(define (same-variable? v1 v2)
(and (variable? v1) (variable? v2) (eq? v1 v2))) -> 두 변수가 서로 같은가?

(define (make-sum a1 a2) (list '+ a1 a2))
(define (make-product m1 m2) (list '* m1 m2))

(define (sum? x)
(and (pair? x) (eq? (car x) '+)))
(define (product? x)
(and (pair? x) (eq? (car x) '*)))

(define (augend s) (cadr s))
(define (multiplicand p) (cadr p))

(define (addend s) (caddr s))
(define (multiplier p) (caddr p))

이 식들을 가지고 미분을 했을때 깔끔하게 나오지 않는다.
ex)
d(x*y)/dx = x*0+1*y ----------> y
깔끔하게

깔끔하게 식을 고친다
// deriv 식을 고치는 것이 아닌 make-sum을 고친다.
// 이런 식으로 기계를 고치듯이 기계 전체를 바꾸기 보다는 기계 부품을 바꾼다.

(define (make-sum a1 a2)
(cond ((=number? a1 0) a2) //한 식이 어떤 수와 같은지 알아보는 프로시저
((=number? a2 0) a1)
((and (number? a1) (number? a2)) (+ a1 a2))
(else (list '+ a1 a2))))

(define (make-product m1 m2)
(cond ((or (=number? m1 0) (=number? m2 0)) 0)
((=number? m1 1) m2)
((=number? m2 1) m1)
((and (number? m1) (number? m2)) (* m1 m2))
(else (list '* m1 m2))))

2.3.3 연습: 집합을 나타내는 방법

집합 연산: union-set, intersection-set, element-of-set, adjoin-set
element-of-set?: 어떤 데이터가 집합의 원소인지 알아보는 술어 연산
adjoin-set: 물체 하나와 집합 하나를 인자로 받아서 그 물체와 집합을 엮은 새 집합을 내놓는다.

차례 없는 리스트로 표현한 집합

(define (element-of-set? x set)
(cond ((null? set) false)
((equals? x (car set)) true) // x 와 set에 있는 원소가 같으면 true
(else (element-of-set? x (cdr set)))))

(define (adjoin-set x set)
(if (element-of-set? x set)
set
(cons x set)))

(define (intersection-set set1 set2)
(cond ((or (null? set1) (null? set2)) '())
((element-of-set? (car set1) set2)
(cons (car set1)
(intersection-set (cdr set1) set2)))
(else (intersection-set (cdr set1 set2))))

==>한 데이터의 표현 방식을 설계할 때 효율은 큰 고민거리 중 하나이다. 위에서 보다시피 모든 집합 연산에서 element-of-set?을 쓰므로, 이 연산의 빠르기가 집합 구현의 효율에 큰 힘을 미친다. //기계부품이 좋을 수로 기계의 성능이 좋은 것과 비슷한 이치

차례 매긴 리스트로 표현된 집합

집합연산의 속도를 끌어올리는 방법)
집합의 표현 방식을 바꾸어서 리스트 속 모든 원소가 오름차순으로 늘어서게끔 만든다.
->집합 속 두 원소를 비교해 어느 것이 큰 지 따질 방법이 필요
1) 글자가 원소일 때 => 사전 차례
2) 물체마다 구별되는 수를 매겨 놓고 수를 비교한다.

원소에 차례를 매겨서 좋은 점)
한 집합의 모든 원소를 훑어보지 않아도 된다.
ex)
(define (element-of-set? x set)
(cond ((null? set) false)
((= x (car set)) true)
((< x (car set)) false)
//찾던 원소보다 더 큰 원소를 만나면 그 원소는 집합에 없다는 뜻
(else (element-of-set? x (cdr set)))))

(define (intersection-set set1 set2)
(if (or (null? set1) (null? set2))
'()
(let ((x1 (car set1)) (x2 (car set2))) //x1, x2는 두 집합의 첫번째 원소
(cond ((= x1 x2) //x1 = x2 이면 이 값은 교집합의 원소이다.
(cons x1
(intersection-set (cdr set1)
(cdr set2))))
((< x1 x2) //x1 < x2 이면 x1은 교집합의 원소가 아니다.
(intersection-set (cdr set1) set2))
((< x2 x1) //x1 > x2 이면 x2는 교집합의 원소가 아니다.
(intersection-set set1 (cdr set2)))))))

두 갈래 나무로 표현한 집합 <= 차례 매긴 리스트 보다 효율 좋음

각 마디에는 집합원소(열매)가 하나씩
왼쪽 고리는 그 마디에 있는 원소보다 작은 원소들, 오른쪽 고리는 그보다 큰 원소들

같은 집합을 여러가지 방식으로 표현할 수 있다.

장점)

x가 집합의 원소인지 아닌 따질때 먼저 x와 맨 꼭대기 마디의 열매를 견준다. x가 열매보다 작으면 왼쪽나무만 살펴보면 되고, 반대로 x가 열매보다 크면 오른쪽나무만 살펴보면 된다.

// 훓어내려갈 때 마다 따져나가야 할 수가 반씩 줄어든다.

ex)

(define (entry tree) (car tree))

(define (left-branch tree) (cadr tree))

(define (right-branch tree) (caddr tree))

(define (make-tree entry left right)

(list entry left right))

(define (element-of-set? x set)

(cond ((null? set) false)

((= x (entry set)) true)

((< x (entry set))

(element-of-set? x (left-branch set)))

((> x (entry set))

(element-of-set? x (right-branch set)))))

(define adjoin-set x set) // 변수 x 와 집합 set을 받아들인다.

(cond ((null? set) (make-tree x '() '())) // null 일때

((= x (entry set)) set) // x = set일때

((< x (entry set)) // x < set 일때

(make-tree (entry set)

(adjoin-set x (left-branch set)) //왼쪽 가지에 x

(right-branch set)))

((> x (entry set)) // x > set 일때
(make-tree (entry set)
(left-branch set)
(adjoin-set x (right-branch set))))) //오른쪽 가지에 x
*주의점!!!
나무의 생김새가 균형잡히게 나와야 한다.
=> 새로운 연산식(adjoin-set)을 정의해 사용한다.

집합에서 정보 찾아내기

찾고자 하는 데이터에 빨리 다가갈 수 있도록 연산의 효율을 끌어올리는 것이 중요하다.
=> 각 데이터마다 키를 부여해주는 것
=> 데이터 부여된 키를 뽑아내는 프로시저 필요!!

(define (lookup given-key set-of-records)
(cond ((null? set-of-records) false)
((equals? given-key (key (car set-of-records)))
(car set-of-records))
(else (lookup given-key (cdr set-of-records)))))

2.3.4 연습 : 허프만 인코딩 나무
=>글자의 출현빈도에 따라 코드의 길이를 다르게 주는 방식

만드는 법)
가장 적게 나오는 글자가 나무뿌리에서 가장 떨어져있게 하면 된다.

ex)
나뭇잎 집합 {(A 8) (B 3) (C 1) (D 1) (E 1) (F 1) (G 1) (H 1)}
묶어내기 {(A 8) (B 3) ({C D} 2) (E 1) (F 1) (G 1) (H 1)}
묶어내기 {(A 8) (B 3) ({C D} 2) ({E F} 2) (G 1) (H 1)}
묶어내기 {(A 8) (B 3) ({C D} 2) ({E F} 2) ({G H} 2)}
묶어내기 {(A 8) (B 3) ({C D} 2) ({E F G H} 4)}
묶어내기 {(A 8) ({B C D} 5) ({E F G H} 4)}
묶어내기 {(A 8) ({B C D E F G H} 9)}
마지막으로 묶어내기 {({A B C D E F G H} 17)}

=> 마지막 마디가 남을 때까지 가장 가벼운 가지 2개를 묶는다.

표현하는 방법

(define (make-leaf symbol weight)
(list leaf symbol weight))

(define (leaf? object)
(eq? (car object) 'leaf))

(define (symbol-leaf x) (cadr x))

(define (weight-leaf x) (caddr x))

(define (make-code-tree left right) //허프만 트리 생성 프로시저
(list left
right
(append (symbols left) (symbols right))
(+ (weight left) (weight right))))

(define (left-branch tree) (car tree))

(define (right-branch tree) (cadr tree))

(define (symbols tree) //문자 집합
(if (leaf? tree)
(list (symbol-leaf tree))
(caddr tree)))

(define (weight tree) //무게 집합
(if (leaf? tree)
(weight-leaf tree)
(caddr tree)))

디코딩 프로시저

(define (decode bits tree)
(define (decode-1 bits current-branch)
(if (null? bits)
'()
(let ((next-branch //next-branch 정의
(choose-branch (car bits) current-branch)))
(if (leaf? next-branch)
(cons (symbol-leaf next-branch)
(decode-1 (cdr bits) tree))
(decode-1 (cdr bits) next-branch)))))
(decode-1 bits tree))

(define (choose-branch bit branch) //문자를 비트로 변환
(cond ((= bit 0) (left-branch branch))
((= bit 1) (right-branch branch))
(else (error "bad bit -- CHOOSE-BRANCH" bit))))

무게가 있는 원소들의 집합

앞의 나무표현 방식에서는 잎이 아닌 마디에 글자 집합이 들어 있었는데, 이 집합을 리스트로 표현했다. 하지만, 위에서 얘기한 알고리즘대로 나무를 만들려면, 가장 작은 원소를 잇달아 묶어내는 과정에서 나뭇잎과 나무들로 이루어진 집합을 쓸 수 있어야 한다. 가장 작은 원소를 찾는 일이 되풀이되므로, 이런 경우에는 차례 매긴 집합 표현을 쓰는 것이 편리하다.

(define (adjoin-set x set)
(cond ((null? set) (list x))
((< (weight x) (weight (car set))) (cons x set))
(else (cons (car set)
(adjoin-set x (cdr set))))))

위에 adjoin-set과 차이점)
원소를 무게에 따라 분류한다.

(define (make-leaf-set pairs) //글자와 빈도 쌍으로 이루어진 리스트: pairs
(if (null? pairs)
'()
(let ((pair (car pairs))) //pair 정의
(adjoin-set (make-leaf (car pair)
(cadr pair))
(make-leaf-set (cdr pairs))))))

Praying

2015년 1월 24일 토요일

컴퓨터 프로그램의 구조와 해석(1) 2장 2

댓글 없음:

댓글 쓰기