스텐실 벡터
스텐실 벡터 (Stencil Vectors)
스텐실 벡터는 벡터와 비슷하지만 연관된 마스크(mask) fixnum을 갖고 있어서, 마스크에 설정된 비트 수가 벡터의 길이를 결정합니다. HAMT(hash array mapped trie) 같은 자료 구조를 구현하는 데 유용합니다.
출처: Racket Reference
본문
스텐실 벡터는 벡터와 같지만, 연관된 마스크 fixnum을 가지며, 마스크에서 설정된 비트 수가 벡터의 길이를 결정합니다. 스텐실 벡터는 [Torosyan21] 같은 일부 자료 구조, 예를 들어 HAMT(hash array mapped trie, 해시 배열 매핑 트라이)를 구현하는 데 유용합니다.
개념적으로, 스텐실 벡터의 마스크는 전체 크기의 스텐실 벡터 중 어떤 가상 요소들이 존재하는지를 나타냅니다. 그러나 마스크 비트는 stencil-vector-ref와 stencil-vector-set!을 통한 접근이나 변이에는 영향을 주지 않습니다. 예를 들어 어떤 스텐실 벡터가 마스크 25를 갖고 있다면, 이것은 #b11001로도 쓸 수 있습니다. 낮은 비트부터 높은 비트로 읽으면, 그 마스크는 가상 슬롯 0, 3, 4에 값이 존재함을 나타냅니다. 그 스텐실 벡터의 요소가 'a, 'b, 'c라면, 'a는 가상 슬롯 0에 있고 인덱스 0으로 접근하며, 'b는 가상 슬롯 3에 있고 인덱스 1로 접근하고, 'c는 가상 슬롯 4에 있고 인덱스 2로 접근합니다.
마스크에서 비트들의 상대적 순서는 stencil-vector-update와 함께하는 함수형 갱신 연산에 관련이 있습니다. 제거할 요소는 제거 마스크로 지정하고, 추가할 요소는 추가 마스크를 통해 남은 요소들에 대한 상대적 순서로 정렬됩니다. 예를 들어 요소가 'a, 'b, 'c이고 마스크가 #b11001인 스텐실 벡터에서 시작해, 추가 마스크 #b100100으로 새 요소 'd와 'e를 추가하면, 마스크가 #b111101이고 요소 순서가 'a, 'd, 'b, 'c, 'e인 스텐실 벡터가 만들어집니다.
스텐실 벡터의 최대 크기는 64비트 플랫폼에서 58개 요소이고 32비트 플랫폼에서 26개 요소입니다. 이 제한된 크기는 컴팩트한 내부 표현을 가능하게 하고 갱신 연산이 상대적으로 단순함을 보장합니다. 스텐실 벡터는 변이 가능하지만, 주로 변이 없이 사용해 영속(persistent) 자료 구조를 구현하는 것을 목적으로 합니다.
두 스텐실 벡터가 같은 마스크를 갖고, 대응하는 슬롯의 값들이 equal?이면 두 스텐실 벡터는 서로 equal?입니다.
출력된 벡터는 #<stencil ...>로 시작하며, 이 출력 형태는 read로 분석할 수 없습니다. s-exp->fasl과 serialize 함수는 스텐실 벡터를 지원하지 않는데, 부분적으로는 64비트 플랫폼의 스텐실 벡터가 32비트 플랫폼에서는 표현되지 못할 수 있기 때문입니다. 스텐실 벡터는 자료형 구현을 위한 메모리 내 표현으로 사용되도록 의도되었습니다.
base 패키지의 8.5.0.7 버전에서 추가되었습니다.
procedure
(stencil-vector? v) → boolean?
v : any/c
v가 스텐실 벡터이면 #t를, 그렇지 않으면 #f를 반환합니다.
예시:
> (stencil-vector #b10010 'a 'b)
#<stencil 18: a b>
> (stencil-vector #b111 'a 'b 'c)
#<stencil 7: a b c>
base 패키지의 8.5.0.7 버전에서 추가되었습니다.
procedure
(stencil-vector-mask-width) → exact-nonnegative-integer?
현재 플랫폼에서 스텐실 벡터에 허용되는 최대 요소 수를 반환합니다. 결과는 64비트 플랫폼에서 58이거나 32비트 플랫폼에서 26입니다.
procedure
(stencil-vector mask v ...) → stencil-vector?
mask : (integer-in 0 (sub1 (expt 2 (stencil-vector-mask-width))))
v : any/c
마스크 mask와 요소 v들을 결합한 스텐실 벡터를 반환합니다. 제공된 v들의 수는 mask의 2의 보수 표현에서 설정된 비트 수와 일치해야 합니다.
base 패키지의 8.5.0.7 버전에서 추가되었습니다.
procedure
(stencil-vector-mask vec)
→ (integer-in 0 (sub1 (expt 2 (stencil-vector-mask-width))))
vec : stencil-vector?
vec의 마스크를 반환합니다. 스텐실 벡터의 마스크는 생성 시점에 결정되며 나중에 변경할 수 없습니다.
예시:
> (stencil-vector-mask (stencil-vector #b10010 'a 'b))
18
base 패키지의 8.5.0.7 버전에서 추가되었습니다.
procedure
(stencil-vector-length vec)
→ (integer-in 0 (sub1 (stencil-vector-mask-width)))
vec : stencil-vector?
vec의 길이(즉 벡터의 슬롯 수)를 반환합니다. 결과는 (fxpopcount (stencil-vector-mask vec))와 같습니다.
예시:
> (stencil-vector-length (stencil-vector #b10010 'a 'b))
2
base 패키지의 8.5.0.7 버전에서 추가되었습니다.
procedure
(stencil-vector-ref vec pos) → any/c
vec : stencil-vector?
pos : exact-nonnegative-integer?
vec의 슬롯 pos에 있는 요소를 반환합니다. 첫 번째 슬롯은 위치 0이고 마지막 슬롯은 (stencil-vector-length vec)보다 하나 작습니다.
예시:
> (stencil-vector-ref (stencil-vector #b10010 'a 'b) 1)
'b
> (stencil-vector-ref (stencil-vector #b111 'a 'b 'c) 1)
'b
base 패키지의 8.5.0.7 버전에서 추가되었습니다.
procedure
(stencil-vector-set! vec pos v) → void?
vec : stencil-vector?
pos : exact-nonnegative-integer?
v : any/c
vec의 슬롯 pos를 v를 포함하도록 갱신합니다.
예시:
> (define st-vec (stencil-vector #b101 'a 'b))
> st-vec
#<stencil 5: a b>
> (stencil-vector-set! st-vec 1 'c)
> st-vec
#<stencil 5: a c>
base 패키지의 8.5.0.7 버전에서 추가되었습니다.
procedure
(stencil-vector-update vec
remove-mask
add-mask
v ...) → stencil-vector?
vec : stencil-vector?
remove-mask : (integer-in 0 (sub1 (expt 2 (stencil-vector-mask-width))))
add-mask : (integer-in 0 (sub1 (expt 2 (stencil-vector-mask-width))))
v : any/c
vec와 같지만, remove-mask에 해당하는 요소들이 제거되고, 주어진 v들이 add-mask로 결정된 기존(제거되지 않은) 요소들에 대한 상대적 위치에 추가된 스텐실 벡터를 반환합니다.
예시:
> (define st-vec (stencil-vector #b101 'a 'b))
> (stencil-vector-update st-vec #b0 #b10 'c)
#<stencil 7: a c b>
> (stencil-vector-update st-vec #b0 #b1000 'c)
#<stencil 13: a b c>
> st-vec ; unchanged by updates
#<stencil 5: a b>
> (stencil-vector-update st-vec #b1 #b1 'c)
#<stencil 5: c b>
> (stencil-vector-update st-vec #b100 #b100 'c)
#<stencil 5: a c>
> (stencil-vector-update st-vec #b100 #b0)
#<stencil 1: a>
base 패키지의 8.5.0.7 버전에서 추가되었습니다.
더 알아보기
- 벡터(Vectors) 관련 문서
- HAMT 자료 구조 구현 관련 내용