۲۷ - ۵مَپ یا Map

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

اکثرِ ساختارهای داده‌ای که می‌بینیم توی کتابخونه ِ ‏‎containers‎‏ اند. پس اگه build‌ِش کنین، ‏‎Map‎‏ هم میاد. ‏‎Sequence‎‏ و ‏‎Set‎‏ و چندتا چیز دیگه هم میان. جلوتر می‌بینین که خیلی از ساختارهای داده API ِ مشابه دارن، ولی هر کدوم برای شرایطِ متفاوتی طراحی شدن.

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

ساختار ِ تایپِ ‏‎Map‎‏ این شکلیه:

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

type Size = Int

شاید از فصلِ قبل یادتون باشه که علامت تعجب‌ها برای نشون دادنِ اکیدی به کار میرن. ‏‎Tip‎‏ یه داده‌ساز برای "درپوش" گذاشتن روی شاخه ِ یه درخت ِه.

اگه دوست دارین باز کردنِ فیلد‌های اکید رو یاد بگیرین (همون نقشی که پراگما ِ ‏‎UNPACK‎‏ داره)، مستندات ِ GHC رو بخونین.

چه چیزی با ‏‎Map‎‏ سریع‌تر میشه؟

خب کاربردِ اصلی‌ش جستجو با کلید ِه. مقایسه‌ی زیر بینِ یه لیستِ شراکتی و ‏‎Data.Map‎‏ رو در نظر بگیرین:

module Main where

import Criterion.Main
import qualified Data.Map as M

genList :: Int -> [(String, Int)]
genList n = go n []
  where go 0 xs = ("0", 0) : xs
        go n' xs =
          go (n' - 1) ((show n', n') : xs)

pairList :: [(String, Int)]
pairList = genList 9001

testMap :: M.Map String Int
testMap = M.fromList pairList

main :: IO ()
main = defaultMain
  [ bench "lookup one thing, list" $
      whnf (lookup "doesntExist") pairList
  , bench "lookup one thing, map" $
      whnf (M.lookup "doesntExist") testMap
  ]

اگه یه چیز ارزون و خوشحال برای سریِ کوچیکی از جفت‌ها لازم دارین، لیست‌های شراکتی مثلِ ‏‎pairList‎‏ خوبَن، اما بهتره هر وقت کلید و مقدار دارین، بطورِ پیش‌فرض از ‏‎Map‎‏ استفاده کنین. با این کار از یه سری تابعِ به‌دردبخور برای جستجو کردنِ بهینه هم بهره‌مند میشین. عملیاتِ فروگذاری هم با ‏‎Map‎‏، جفت‌های کلید-مقداری ای که در حالِ حاضر وجود دارن رو سریع‌تر از لیست‌های شراکتی پیدا می‌کنن.

چه چیزی با ‏‎Map‎‏ کُندتَره؟

اگه تایپِ کلید‌تون ‏‎Int‎‏ باشه، معمولاً نشون از این داره که بهتره برین سراغِ ‏‎HashMap‎‏، ‏‎IntMap‎‏، یا ‏‎Vector‎‏؛ بسته به مسئله‌تون. مثلاً اگه تراکمِ حافظه ِ خوب و محلیّت لازم دارین (که باعث میشن جمع‌آوری و خوندن ِ مقادیر از یه ‏‎Vector‎‏ ِ بزرگ سریع‌تر بشه)، اون موقع احتمالاً ‏‎Map‎‏ مناسب نیست و بهتره برین سراغِ ‏‎Vector‎‏.