۲۷ - ۷سیکوئِنس یا Sequence

‏‎Sequence‎‏ نوع‌داده ِ خوبیه که برپایه‌ی درخت‌های انگشتی ساخته شده؛ متأسفانه توی این کتاب درخت‌های انگشتی رو توضیح نمیدیم، اما پیشنهاد می‌کنیم خودتون یه نگاهی بهشون بندازین.^* با ‏‎Sequence‎‏ میشه هم از ابتدا و هم از انتها append ِ ارزون داشت. یکی از مشکلاتِ رایجِ لیست‌ها اینه که append فقط از ابتدا ارزون‌ه.

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

newtype Seq a = Seq (FingerTree (Elem a))

-- چیز مهمی نیست، فقط نقش Elem
-- این رو داره که در تایپ‌ها (موقع 
-- استفاده) المان‌ها و گره‌ها رو
-- ‎‏از هم جدا کنه.‏‎
newtype Elem a = Elem { getElem :: a }

data FingerTree a
  = Empty
  | Single a
  | Deep {-# UNPACK #-} !Int !(Digit a)
         (FingerTree (Node a)) !(Digit a)

چه چیزی با ‏‎Sequence‎‏ سریع‌تره؟

cons و append در دو انتهای ساختارِ داده و الحاق کارهایی‌اند که ‏‎Sequence‎‏ به خاطرشون شناخته شده‌ست. البته اکثرِ مواقع، لیست گزینه‌ی بهتری نسبت به ‏‎Sequence‎‏ ِه. دسترسی به دُم با ‏‎Sequence‎‏ به صرفه‌تر از لیست‌ه. این یه مثال از حالتی‌ه که چون لیست یه کم بزرگه، ‏‎Sequence‎‏ بهتر عمل می‌کنه:

module Main where

import Criterion.Main 
import qualified Data.Sequence as S

lists :: [[Int]]
lists = replicate 10 [1..100000]

seqs :: [S.Seq Int]
seqs =
  replicate 10 (S.fromList [1..100000]) 

main :: IO ()
main = defaultMain
  [ bench "concatenate lists" $
      nf mconcat lists
  , bench "concatenate sequences" $
      nf mconcat seqs
  ]

دقت کنین که اینجا، زمانِ خیلی زیادی در بنچمارک صرفِ پیمایش ِ ساختارِ داده میشه، چون برای اطمینان از اینکه همه‌ی کار انجام بشه داریم تا حالت معمولی محاسبه می‌کنیم. برحسب اتفاق، به خاطر پیمایش (یا اندیس‌گیری) ِ سریع‌تر در ‏‎Sequence‎‏، این کار تفاوت بینِ لیست و ‏‎Sequence‎‏ هم برجسته‌تر می‌کنه. این رو در نظر بگیرین:

module Main where

import Criterion.Main 
import qualified Data.Sequence as S

lists :: [Int]
lists = [1..100000]

seqs :: S.Seq Int
seqs = S.fromList [1..100000]

main :: IO ()
main = defaultMain
  [ bench "indexing list" $
      whnf (\xs -> xs !! 9001) lists
  , bench "indexing sequence" $
      whnf (flip S.index 9001) seqs
  ]

وقتی ما این بنچمارک رو اجرا کردیم، اختلاف بین لیست و ‏‎Sequence‎‏ در مقیاسِ ۱۰۰ بود.

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

‏‎Sequence‎‏ هم مثل ‏‎Map‎‏ یه ساختارِ داده ِ پایا هست، پس تراکم حافظه‌ش به خوبیِ ‏‎Vector‎‏ نیست (الان میرسیم). اندیس‌گیری با ‏‎Int‎‏ هم، برای ‏‎Vector‎‏ سریع‌تره. در بعضی موارد، اگه لیست کوچیک باشه، تایپِ لیست برای cons کردن و الحاق سریع‌تر عمل می‌کنه. وقتی می‌خواین به انتهای یه لیستِ طولانی، apped ِ کم هزینه داشته باشین، خوبه ‏‎Sequence‎‏ هم امتحان کنین، اما اگه عملکرد براتون مهمه، تصمیمِ نهایی رو بر مبنای داده‌ها ِ بنچمارکینگ بگیرین.