۲۷ - ۶سِت یا Set

این هم توی ‏‎containers‎‏ ِه. شبیهِ ‏‎Map‎‏ ِه، فقط جفت‌های کلید-مقدارِش اون "مقدار" رو ندارن. خب، کلید ِ خالی به چه درد می‌خوره؟

وقتی از ‏‎Map‎‏ استفاده می‌کنیم، توابع‌ش محدودیت ِ ‏‎Ord‎‏ دارن تا حتماً کلیدها مرتب باشن. این یکی از چیزهایی‌ه که باعثِ سریع شدنِ جستجو در ‏‎Map‎‏ میشه. وقتی کلیدها به ترتیب باشن، در واقع فضای مسئله رو نصف می‌کنه: مثلاً اگه بین کلیدهای ۱ تا ۱۰ دنبالِ کلید ِ ۶ باشیم، لازم نیست نیمه‌ی اولِ اون مجموعه رو بگردیم، چون از ۶ کوچیکتراند. ‏‎Set‎‏ هم مثلِ ‏‎Map‎‏ ساختارِ شراکتی داره، نه خطی.

تابع‌های ‏‎Set‎‏ هم همون محدودیت ِ ‏‎Ord‎‏ رو دارن، اما دیگه جفتِ کلید-مقدار نداریم – فقط کلید داریم. یا میشه گفت اینجا کلیدها همون مقادیر اند. یعنی ‏‎Set‎‏ یه مجموعه‌ی مرتب و یکتا از مقادیر رو ارائه میده.

این نوع‌داده ِ ‏‎Set‎‏ ِه:

data Set a
  = Bin
    {-# UNPACK #-}
    !Size !a !(Set a) !(Set a)
  | Tip

type Size = Int

در واقع معادلِ یه تایپِ ‏‎Map‎‏ با مقادیرِ واحد ِه.

module Main where

import Criterion.Main
import qualified Data.Map as M
import qualified Data.Set as S

bumpIt (i, v) = (i + 1, v + 1)

m :: M.Map Int Int
m = M.fromList $ take 10000 stream
  where stream = iterate bumpit (0, 0)

s :: S.Set Int
s = S.fromList $ take 10000 stream
  where stream = iterate (+1) 0

membersMap :: Int -> Bool
membersMap i = M.member i m

membersSet :: Int -> Bool
membersSet i = S.member i s

main :: IO ()
main = defaultMain
  [ bench "member check map" $
      whnf membersMap 9999 
  , bench "member check set" $
      whnf membersSet 9999
  ]

اگه کُدِ بالا رو بنچمارک بگیرین، برای هردوشون نتایجِ مشابه می‌گیرین، شاید ‏‎Map‎‏ یه کوچولو کند‌تر از ‏‎Set‎‏ باشه. دلیلِ این تشابه اینه که توی کتابخونه ِ ‏‎containers‎‏ این دوتا ساختارهای داده تقریباً عینِ همدیگه‌اند.

دیگه چیز زیادی نمونده که بگیم. همون معایب و محاسنِ ‏‎Map‎‏ رو داره، عملیات‌های اصلی‌ش هم عملکرد ِ یکسانی دارن، اینجا فقط یه کم محدودیتِ بیشتری دارین.

تمرین: تمرینِ بنچمارک

برای خودتون یه بنچمارک درست کنین که ثابت کنه ‏‎Map‎‏ و ‏‎Set‎‏ عملکرد ِ مشابهی دارن. عملیات ِ دیگه‌ای غیر از تستِ عضویت هم امتحان کنین، مثلِ فروگذاری یا اتحاد.