प्रकाशस्तंभ की लॉगबुक

हैश-सेट बदलने योग्य, बिना क्रम वाले संग्रह होते हैं जो हर वैल्यू को अधिकतम एक बार संग्रहीत करते हैं। ढूँढना, डालना और हटाना, तीनों औसतन 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 से आता है) से अलग है, क्योंकि member? किसी सीक्वेंस पर एक-एक करके, यानी रैखिक रूप से, स्कैन करता है। हैश-सेट के लिए 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 लौटाता है, हैश-सेट नहीं।

यह क्यों ज़रूरी है

हैश-सेट, हैशटेबल के साथ ग्राफ ट्रैवर्सल में स्वाभाविक रूप से काम आते हैं: हैशटेबल हर नोड को उसके पड़ोसी नोड से जोड़ती है, और हैश-सेट दर्ज रखता है कि कौन-कौन से नोड पहले ही देखे जा चुके हैं, ताकि खोज में लूप न बने और काम दोहराया न जाए। इसके बाद ट्रैवर्सल के लिए एक क्यू और ये दो स्ट्रक्चर चाहिए, जिन्हें बाहर की ओर बढ़ते हुए मौके पर ही बदलते जाते हैं।