등대 일지

해시셋은 값을 최대 한 번만 저장하는, 변경할 수 있고 순서가 없는 컬렉션이에요. 조회, 삽입, 삭제는 모두 평균 O(1)이에요. 해시셋은 hash-sets에 들어 있고, sets 프로토콜을 구현해요.

해시셋 리터럴

HS{ "NS-1024" "WB-203" } .
! => HS{ "NS-1024" "WB-203" }

HS{ }는 빈 리터럴이에요. 다른 Factor 리터럴과 마찬가지로 공유되는 객체예요. 소스에서 HS{ }를 참조하는 곳은 모두 같은 셋을 가리켜요. HS{ } clone은 호출할 때마다 새롭고 독립적인 복사본을 만들어 줘요.

시퀀스에서 만들기

>hash-set ( seq -- set )    ! build a fresh set from a sequence

값이 이미 시퀀스에 들어 있다면, >hash-set이 중복을 버리면서 한 번에 셋으로 변환해 줘요.

USING: hash-sets prettyprint ;

{ "NS-1024" "WB-203" "NS-1024" } >hash-set .
! => HS{ "NS-1024" "WB-203" }

원소 추가와 제거

adjoin     ( elt set -- )    ! insert in place; no-op if already present
adjoin-all ( seq set -- )    ! insert every element of seq in place
delete     ( elt set -- )    ! remove in place; no-op if absent

세 가지 모두 셋 자체를 변경하고, 스택에는 아무것도 반환하지 않아요.

USING: hash-sets kernel sets ;

HS{ } clone
"NS-1024" over adjoin
"WB-203"  over adjoin
"NS-1024" over adjoin    ! duplicate — no effect
.                        ! => HS{ "NS-1024" "WB-203" }

adjoin-all은 한꺼번에 처리하는 형태예요. 시퀀스의 각 원소를 넣으면서, adjoin이 하나씩 처리할 때와 마찬가지로 중복은 건너뛰어요.

USING: hash-sets kernel sets ;

HS{ "NS-1024" } clone
{ "WB-203" "NS-1024" "QR-7" } over adjoin-all
.                        ! => HS{ "QR-7" "NS-1024" "WB-203" }  (order not guaranteed)

셋에 물어보기

in?         ( elt set -- ? )   ! is elt in the set?
null?       ( set -- ? )       ! is the set empty?
cardinality ( set -- n )       ! number of elements
members     ( set -- seq )     ! enumerate as a sequence

in?은 셋 프로토콜의 소속 검사예요. sequences에 있는 member?와는 달라요. member?는 시퀀스를 처음부터 끝까지 훑어요. 해시셋에서 in?은 해시 조회예요. 평균 O(1)이고, 이게 바로 해시셋을 쓰는 이유죠.

null?은 셋에 원소가 하나도 없는지 알려줘요. cardinality를 0과 비교하는 대신 "비어 있어요?"라고 곧바로 묻는 방법이에요.

: my-log ( -- set ) HS{ "NS-1024" "WB-203" } ;

"NS-1024" my-log in? .   ! => t
"X-99"    my-log in? .   ! => f
my-log null? .           ! => f
HS{ } clone null? .      ! => t
my-log cardinality .     ! => 2

셋 합치기

union     ( set1 set2 -- set )
intersect ( set1 set2 -- set )
diff      ( set1 set2 -- set )
set-like  ( set exemplar -- set' )

union은 "둘 중 하나에라도 있는 모든 원소", intersect는 "양쪽 모두에 있는 원소", diff는 "set1에는 있지만 set2에는 없는 원소"예요. 각각은 원래의 셋을 변경하지 않고 새로운 셋을 반환해요.

set-like는 set을 exemplar의 타입으로 변환해요. union/intersect/diff의 기본 구현은 이걸 이용해서 결과가 수신 객체의 타입과 일치하도록 만들어요. <my-set> <hash-set> union은 해시셋이 아니라 my-set을 반환하죠.

왜 중요할까요

해시셋은 그래프 순회에서 해시테이블과 자연스럽게 짝을 이뤄요. 해시테이블은 각 노드를 이웃에 대응시키고, 해시셋은 어떤 노드를 이미 방문했는지 기록해서 탐색이 맴돌거나 같은 일을 반복하지 않게 해줘요. 그러면 순회는 큐 하나에 이 두 구조를 더한 것이 되고, 바깥으로 훑어 나가면서 그 자리에서 변경돼요.