۲۷ - ۸وِکتور یا Vector

ساختار داده ِ بعدی که نگاه می‌کنیم، توی ‏‎containers‎‏ نیست؛ توی کتابخونه ِ خودش به اسمِ ‏‎vector‎‏ ِه. اگه به اون لینک برین، می‌بینین که بردارها رو "آرایه‌های بهینه" معرفی کرده. ما سراغ آرایه‌ها، یا تایپِ ‏‎Array‎‏ ِ هسکل نمیریم.

کسی زیاد از آرایه‌ها (یا دقیق‌تر بگیم، ‏‎Array‎‏ ِ هسکل) استفاده نمی‌کنه. تقریباً همیشه بجای آرایه از ‏‎Vector‎‏ استفاده میشه. تعریفِ تایپِ ‏‎Vector‎‏ ِ معمولی از این قراره:

-- | بردارهای جعبه‌شده، به
-- | ‎‏بُرِش زدنِ بهینه کمک می‌کنن.‏‎
data Vector a =
     Vector {-# UNPACK #-} !Int
            {-# UNPACK #-} !Int
            {-# UNPACK #-} !(Array a)
     deriving ( Typeable )

‏‎Vector‎‏ انواعِ زیادی داره. بعضی‌هاشون رو بخوایم بگیم: جعبه‌شده، جعبه‌نشده، تغییرناپذیر، تغییرپذیر، و بردارهای انبارشدنی، اما معمولاً فقط از همون نسخه‌ی معمولی‌ش که این بالا نوشتیم استفاده میشه. تو این فصل یه بخش به بردارهای تغییرپذیر اختصاص دادیم. منظور از جعبه‌شده اینه که بردار می‌تونه به هر نوع‌داده‌ای که بخواین اشاره کنه؛ جعبه‌نشده مقدارهای خام رو ارائه میده، بدون اشاره‌ی اشاره‌گر^* و می‌تونه خیلی در حافظه صرفه‌جویی کنه، اما فقط محدود به تایپ‌های ‏‎Bool‎‏، ‏‎Char‎‏، ‏‎Double‎‏، ‏‎Float‎‏، ‏‎Int‎‏، ‏‎Word‎‏، و توپل‌های مقادیرِ جعبه‌نشده هست. از اونجا که نیوتایپ لیفت‌نشده هست و هیچ اشاره‌ی اشاره‌گری نمی‌سازه، هر نیوتایپی که شاملِ یه تایپِ جعبه‌نشدنی باشه رو میشه از جعبه درآورد.

چه زمانی در هسکل ‏‎Vector‎‏ لازم میشه؟

زمانی ‏‎Vector‎‏ می‌خواین که:

اون برش زدن که گفتیم چی بود؟

این کامنت در تعریفِ ‏‎Vector‎‏ یادتون‌ه؟

-- | بردارهای جعبه‌شده، به
-- | ‎‏بُرِش زدنِ بهینه کمک می‌کنن.‏

 -- :م. متنِ اصلی
-- | Boxed vectors, supporting
-- | efficient slicing.

برش زدن یعنی بریدنِ یه تیکه از آرایه، یا ساختن یه زیر-آرایه. تایپِ ‏‎Vector‎‏ طوری طراحی شده که برش زدن‌ِش کم هزینه باشه. این مثال رو در نظر بگیرین:

module Main where

import Criterion.Main 
import qualified Data.Vector as V

slice :: Int -> Int -> [a] -> [a]
slice from len xs = 
  take len (drop from xs)

l :: [Int]
l = [1..1000]

v :: V.Vector Int
v = V.fromList [1..1000]

main :: IO ()
main = defaultMain
  [ bench "slicing list" $
      whnf (head . slice 100 900) l
  , bench "slicing vector" $
      whnf (V.head . V.slice 100 900) v
  ]

تو نتیجه‌ی این بنچمارک، ‏‎Vector‎‏ باید سریع‌تر از لیست باشه. چرا؟ چون تمامِ کاری که موقعِ ساختن ِ ‏‎Vector‎‏ ِ جدید (با ‏‎V.slice‎‏) باید انجام میشد، این بود:

-- Data.Vector از

instance G.Vector Vector a where
  -- بقیه‌ی متودها حذف شدن
  {-# INLINE basicUnsafeSlice #-}
  basicUnsafeSlice j n (Vector i _ arr) =
    Vector (i+j) n arr

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

به‌روزرسانیِ بردارها

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

module Main where

import Criterion.Main 
import qualified Data.Vector as V

testV' :: Int -> V.Vector Int
testV' n =
  V.map (+n) $ V.map (+n) $
    V.map (+n) $ V.map (+n)
    (V.fromList [1..10000]) 

testV :: Int -> V.Vector Int
testV n =
  V.map ( (+n) . (+n)
        . (+n) . (+n) )
        (V.fromList [1..10000]) 

main :: IO ()
main = defaultMain
  [ bench "vector map prefused" $
      whnf testV 9998
  , bench "vector map will be fused" $
      whnf testV' 9998
  ]

توی کتابخونه ِ ‏‎vector‎‏، جوششِ حلقه بصورت آماده تعریف شده، پس در خیلی از موارد (مثل نگاشت کردن)، فقط به خاطر اینکه ۴ بار نگاشت کردین چهارتا بردار درست نمی‌کنه. با استفاده از GHC RULES (م. یا قوانینِ GHC)، کُدِ ‏‎testV'‎‏ به کُدی که در ‏‎testV‎‏ می‌بینین تبدیل میشه. جا داره بگیم یکی از دلایلی که این بهینه‌سازی مطمئن‌ه، اینه که به خاطر تایپ‌ها، میدونیم چه کُدی اثر اجرا می‌کنه و چه کُدی نمی‌کنه.

با همه‌ی اینها، جوششِ حلقه نوش‌دارو نیست؛ ممکنه شرایطی پیش بیاد که بخواین بعضی المان‌ها رو یکی‌یکی تغییر بدین. کلاً راه‌های بهینه‌تری هم برای به‌روزرسانیِ بردارها وجود دارن. اینجا از اوپراتور ِ ‏‎(//)‎‏ از کتابخونه ِ ‏‎vector‎‏ استفاده می‌کنیم. با این اوپراتورِ به‌روزرسانیِ دسته‌ای میشه هربار چندین المانِ یه بردار رو تغییر داد:

module Main where

import Criterion.Main
import Data.Vector ((//))
import qualified Data.Vector as V

vec :: V.Vector Int
vec = V.fromList [1..10000]

slow :: Int -> V.Vector Int
slow n = go n vec
  where go 0 v = v
        go n v = go (n-1) (v // [(n, 0)])

batchList :: Int -> V.Vector Int
batchList n = vec // updates
  where updates =
          fmap (\n -> (n, 0)) [0..n]

main :: IO ()
main = defaultMain
  [ bench "slow" $ whnf slow 9998
  , bench "batch list" $
      whnf batchList 9998
  ]

مشکلِ مثال اول اینه که از API ِ دسته‌ای استفاده کرده اما... دسته‌ای نیست. اینکه اول همه‌ی لیستِ به‌روزرسانی‌ها ساخته، و بعد به تابعِ ‏‎(//)‎‏ داده بشه، خیلی کم هزینه‌تره (در تست‌های ما بین ۵۰۰ تا ۱۰۰۰ برابر ارزون‌تر). اگه از تابعِ به‌روزرسانی که با بردار ِ به‌روزرسانی‌ها کار می‌کنه استفاده کنیم، از این هم سریع‌تر میشه:

batchVector :: Int -> V.Vector Int
batchVector n = V.unsafeUpdate vec updates
  where updates =
          fmap (\n -> (n, 0))
          (V.fromList [0..n])

نتیجه‌ی بنچمارکِ این نسخه باید حدود ۱٫۴ برابر سریع‌تر باشه. ولی ما حریص‌تر از این حرف‌هاییم.

‏‎Vector‎‏‌های تغییرپذیر

”موریا! موریا! شگفتی سرزمین شمال. چنان در اعماق آن پیش رفتیم که همانا هراس بی‌نام را بیدار کردیم.“
—گلویین، یارانِ حلقه

اگه سریع‌تر بخوایم چطور؟ با اینکه خیلی‌ها واقف نیستن، اگه بخوایم، تو هسکل میشه از مزایای به‌روزرسانیِ دَرجا هم استفاده کرد. چیزی که هسکل رو متمایز می‌کنه اینه که این کار رو میشه بدونِ لطمه به شفافیت مرجع یا مشخصاتِ معادلاتیِ خیلی خوبی که بیانیه‌ها دارن انجام داد. اول نشون میدیم چطور باید انجام بشه، بعد توضیح میدیم که چطور طراحی شده تا قابلِ پیش‌بینی رفتار کنه.

مثال از راه رسید:

module Main where

import Control.Monad.Primitive
import Control.Monad.ST
import Criterion.Main
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as MV
import qualified
       Data.Vector.Generic.Mutable as GM

mutableUpdateIO
  :: Int
  -> IO (MV.MVector RealWorld Int)
mutableUpdateIO n = do
  mvec <- GM.new (n+1)
  go n mvec
  where go 0 v = return v
        go n v =
          (MV.write v n 0) >> go (n-1) v

mutableUpdateST :: Int -> V.Vector Int
mutableUpdateST n = runST $ do
  mvec <- GM.new (n+1)
  go n mvec
  where go 0 v = V.freeze v
        go n v =
          (MV.write v n 0) >> go (n-1) v

main :: IO ()
main = defaultMain
  [ bench "mutable IO vector"
    $ whnfIO (mutableUpdateIO 9998)
  , bench "mutable ST vector"
    $ whnf mutableUpdateST 9998
  ]

به ذره جلوتر ‏‎runST‎‏ رو توضیح میدیم. فعلاً حواسمون رو بیاریم روی سرعت: با تست‌های ما، نسخه‌ی ‏‎IO‎‏ ِ تغییرپذیر تقریباً ۷۰۰۰ برابر سریع‌تر از اون حلقه ِ دسته‌نشده ِ اصلی‌مون شد. نسخه‌ی ‏‎ST‎‏ تقریباً ۱٫۵ برابر کندتر از نسخه‌ی ‏‎IO‎‏ شد، ولی باز خیلی سریع بود. زمانِ اضافی که ‏‎ST‎‏ صرف کرد، به خاطر فریزکردنِ بردار ِ تغییرپذیر به یه بردار ِ معمولی بود. ما اینجا ‏‎ST‎‏ رو کامل توضیح نمیدیم، اما همونطور که خواهید دید، به دردِ وقت‌هایی می‌خوره که می‌خواین یه چیزی رو موقتاً تغییرپذیر کنین و مطمئن باشین که هیچ ارجاع ِ تغییرپذیری به خارج از موند ِ ‏‎ST‎‏ افشا نمیشه.

این جدول، نتایجی که ما با چندتا از عملیات‌های برداری گرفتیم رو نشون میده:

بیشترین پیشرفت به خاطر حذف کارهای احمقانه بود. فقط وقت‌هایی که می‌دونین واجبه، به استفاده از تغییرپذیری با ‏‎IO‎‏ یا ‏‎ST‎‏ متوصل شین. دقت کنین که چون این تست تقریباً ۱۰۰۰۰ اندیس در یک بردار رو به‌روزرسانی می‌کرد، وقتی از تغییرپذیری استفاده کردیم حدوداً هر به‌روزرسانی ۱٫۹ نانوثانیه، و وقتی بصورت دسته‌ای با یه بردار ِ پایا انجام دادیم، تقریباً ۱۷٫۶ نانوثانیه صرفِ هر به‌روزرسانی شد.

توضیح اجمالی از ‏‎ST Monad‎‏

‏‎ST‎‏ رو میشه نسخه‌ی تغییرپذیر ِ موند ِ ‏‎State‎‏ ِ اکید تعریف کرد. یا از یه زاویه‌ی دیگه، میشه گفت یه ‏‎IO‎‏ ایه که صرفاً محدود به تغییرپذیری‌ها ایه که امنیت‌شون تضمین‌شده‌ست.

چطوری امن‌اند؟ ‏‎ST‎‏ به قاعده‌ی فلسفیِ درخت توی جنگل^* اتکا داره. ایده‌ی پشتِ این درکِ "اخلاقاً بی‌اثر" در مقاله‌ی ریسه‌های اجراییِ حالتِ تابعی و تنبل^† معرفی شد. اول داده رو آزاد می‌کنه، تغییرش میده، بعد دوباره فریزِش می‌کنه تا دیگه نتونه تغییر کنه. پس می‌تونه در عینِ حفظِ شفافیت مرجع، تغییر کنه.

اگه بهینه‌کننده ترتیبِ کُدی که داده رو تغییر میده تغییر بده، یا به هر نحو دیگه‌ای با اون کُد بازی بشه، دیگه ‏‎ST‎‏ درست کار نمی‌کنه (درست مثلِ ‏‎IO‎‏). پس باید یه چیزی پشتِ‌پرده‌ی تایپ باشه که نذاره GHC همه چیز رو به‌هَم بزنه. تایپِ ‏‎ST‎‏ رو بررسی کنیم ببینیم:

Prelude> import Control.Monad.ST
Prelude> :info ST
newtype role ST nominal representational
newtype ST s a =
  GHC.ST.ST (GHC.ST.STRep s a)
...
Prelude> import GHC.ST
Prelude> :info STRep
type STRep s a =
     GHC.Prim.State# s
  -> (# GHC.Prim.State# s, a #)

یه کم زشته، اما به خاطرِ همه‌ی اون GHC Core هایی که فصلِ قبل دیدین دیگه نباید سورپرایز بشین! چیزی که اینجا مهمه اینه که ‏‎s‎‏ تایپ‌ش رو از اون چیزی می‌گیره که دارین تغییر میدین، اما هیچ شاهد ِ سطحِ جمله‌ای نداره. پس اینجا ‏‎State Monad‎‏ پاک‌شدنی‌ه؛ می‌تونه این فرایندِ موتاسیون رو ایزوله کنه و بعد آب شه بِره.

خیلی مهمه که متوجه باشین اون ‏‎s‎‏، حالتی که تغییر میدین نیست. تغییری که رخ میده، اثرِ جانبی ِ ناشی از ورود به بستار‌ها ایه که اثر رو پیاده می‌کنن. بر حسبِ اتفاق، این موندِ تغییردهنده‌ی حالت – که اکید و لیفت‌نشده هست – طوری کدِتون رو ساختار میده که ترتیبِ محاسبات و اثراتِ مرتبط‌شون رو، همونطور که باید حفظ می‌کنه.

منظورمون از بستار که گفتیم، بیانیه‌های لاندا بود.^* ورود به هر لاندا، اثرات‌ِش رو اجرا می‌کنه. به خاطرِ مهم بودنِ ترتیب در اجرای اثرها، اثرهای یه سری از لانداها دسته نمیشن (هر بیانیه‌ی جدید ممکنه وابسته به اثراتِ قبلی باشه). اول اثرها اجرا میشن، بعد اگه قرار به استفاده از مقدارِ حاصل از محاسبات باشه، اون مقدار هم حساب میشه.

پس تایپِ ‏‎s‎‏ چه کاربردی داره؟ خب، با اینکه میشه مؤدبانه از برنامه‌نویس‌ها خواهش کرد که یه مرجعِ تغییرپذیر (به عنوانِ جوابِ آخر) رو به یه ساختار داده ِ پایا و تغییرناپذیر فریز کنن... نمیشه روش حساب باز کرد. ‏‎ST‎‏ چنین چیزی رو در لحظه‌ی کامپایل اجبار می‌کنه، طوری که ‏‎s‎‏ هیچ وقت با هیچ چیز خارج از ‏‎ST Monad‎‏ قاطی نمیشه. به کَلکِ این کار میگن سورِ وجودی،^* اما قرار نیست فعلاً برای شما معنایی داشته باشه. فقط کمک می‌کنه ارجاع‌های تغییرپذیر رو اشتباهاً به کُدِ خارج از ‏‎ST‎‏ نشت ندین، که می‌تونه منجر به کُدی بشه که بسته به حالتِ بیت‌های حافظه کارهای غیرقابل پیش‌بینی انجام بده.

سعی کنین زیاد از ‏‎ST‎‏ ورود و خروج نکنین. ممکنه در شرایطی، این فریز و آب کردن ِ متعدد، انقدر هزینه رو بیشتر کنه که استفاده از ‏‎IO‎‏ به صرفه‌تر بشه. دسته‌ای کردنِ موتاسیون، برای عملکرد و خواناییِ کد خیلی خوبه.

تمرین‌ها: بردار

یه بنچمارک برای پروفایلینگِ مقدار حافظه‌ای که بردارهای جعبه‌شده و جعبه‌نشده (هردو محتویِ داده‌ها ِ یکسان) مصرف می‌کنن، setup کنین. این بنچمارک رو می‌تونین با یه بنچمارکِ دیگه هم ترکیب کنین (کاری که چند ثانیه‌ای طول بکشه). عمداً صورتِ تمرین رو مبهم گذاشتیم چون بالاخره باید خوندنِ مستندات و کدهای منبع رو یاد بگیرین.