دفتر ثبت فانوس دریایی

«مجموعه‌ی هش» گونه‌ای مجموعه‌ی تغییرپذیر و بدون ترتیب است که هر مقدار را حداکثر یک بار ذخیره می‌کند. جست‌وجو، درج و حذف همگی به‌طور میانگین 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? آزمون عضویت پروتکل مجموعه است. با member? (از sequences) فرق دارد؛ آن یکی یک پویش خطی روی دنباله انجام می‌دهد. برای یک مجموعه‌ی هش، in? یک جست‌وجوی هش است، به‌طور میانگین O(1)، و همین تمام دلیل استفاده از مجموعه‌ی هش است.

null? گزارش می‌دهد که آیا مجموعه هیچ عنصری دارد یا نه؛ راه مستقیم برای پرسیدن «آیا این خالی است؟» به‌جای مقایسه‌ی cardinality با صفر.

: 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 برمی‌گرداند، نه یک مجموعه‌ی هش.

چرا این مهم است

مجموعه‌ی هش به‌طور طبیعی برای پیمایش گراف در کنار جدول هش به کار می‌آید: جدول هش هر گره را به همسایه‌هایش نگاشت می‌کند و مجموعه‌ی هش ثبت می‌کند کدام گره‌ها قبلاً بازدید شده‌اند تا جست‌وجو به حلقه نیفتد یا کاری را دوباره انجام ندهد. آن‌گاه پیمایش چیزی نیست جز یک صف به‌همراه این دو ساختار که همان‌جا، در حین گسترش به بیرون، تغییر می‌کنند.