درخت جستجو در مدل I/O. قسمت سوم: داده‌ساختارهای پویا در الگوریتم‌ها (جلسه پنجم)

در حالت عادی (مدل RAM نه I/O)، می‌توانیم از BST برای مرتب کردن عناصر استفاده کنیم. یعنی عناصر را یکی یکی به BST اضافه کنیم و با پیمایش درخت یک لیست مرتب از عناصر در زمان بهینه N log N به دست می‌آید.

اما مثلاً B-tree را با شروع از یک درخت M/B عنصری، به این هزینه می‌رسد:

sum_{i=0}^{N} log_(B) (M/B+Bi) = N log_(B) N/B

که با جواب بهینه در ضریب زیر متفاوت است:

B log_(B) M/B

که مقدار زیادی است.

یک راه حل ساختن B-tree از پایین به بالا است که با مرتب کردن عناصر امکان پذیر است. اما این کار را نمی‌شود با مثلاً persistent B-tree انجام داد. ما دنبال یک روش داده‌ساختارهای پویا در حالت کلی هستیم.

Buffer-tree:

یک B-tree با درجه رأس M/B و تعداد عناصر در هر برگ B در نظر می‌گیریم که هر گره یک بافر با اندازه‌ی M دارد.

هر وقت بافر یک گره پر می‌شود، عناصر را به عمق بعدی درخت می‌فرستیم. هر بلوک در هر عمق تعداد ثابتی بار پردازش می‌شود پس برای خالی کردن بافر، M/B زمان لازم است.

(زمان‌ها مثل قبل)

به روز رسانی: به حذف و درج‌ها زمان بدهید. با این کار بعداً می‌توانید اگر حذف و درج هر دو در بافر بودند آنها را حذف کنید و هیچ وقت در ساختار درختی اضافه نکنید. قبل از اینکه به ریشه اضافه کنید صبر کنید B عنصر جمع شود (بار اول مثلاً). هر وقت بافرها پر شدند آنها را خالی کنید.

برای مرتب سازی با این درخت، اول عناصر بافر را مرتب کنید، بعد آنها را با عناصر درخت که مرتب هستند ادغام کنید. این کار می‌تواند باعث پر شدن بافر شود که باید آن را در فرزندان تخلیه کنید. این کار را به صورت بازگشتی برای فرزندان هم انجام بدهید.

خالی کردن بافر با اندازه x زمان O(x/B+M/B) می‌برد که به O(x/B) تا I/O نیاز دارد.

ممکن است در این فرایند تعداد عناصر در بافر از M بیشتر باشند (وقتی که از گره بالایی آمده ولی هنوز اضافه نشده) ولی فقط Mتای آنها حداکثر نامرتب هستند.

وقتی بافر یک گره برگ خالی شد، نیاز به متوازن کردن است. (چون یک عمق اضافه شده)

همیشه این حالت برای درخت حفظ می‌کنیم که همه‌ی مسیرهای از ریشه تا برگ بافرشان خالی باشد. با این کار راحت می‌توانیم متوازن کنیم. (با ترکیب و تجزیه گره‌ها)

برای این کار باید به ترتیب BFS بافرها را خالی کنیم.

کاربرد buffer-tree در ساخت صف اولویت:

کوچکترین عنصر، در سمت چپ‌ترین مسیر قرار دارد، پس با O(1/B log_{M/B} N/B) تا I/O می‌توان به آن رسید.

فقط باید قبل از پرس‌و‌جو، بافرهای گره‌های این مسیر را تخلیه کنیم که برای اینکه زمان خالی کردن بافرها خیلی زیاد نشود، مجبوریم کل بافرهای درخت را خالی کنیم.

اما به صورت سرشکنی همچنان در همان زمان می‌شود عنصر را حذف کرد.

درخت جستجو در مدل I/O: قسمت دوم: ابعاد بالاتر (جلسه چهارم داده‌های حجیم)

در این جلسه هدف جواب دادن کوئری‌های پیدا کردن نقاط در بازه‌ی [x1,x2]*[y1,y2] است.

دو بعدی:

یک BST روی x می‌سازیم و در هر گره‌ی آن یک BST روی y می‌سازیم.

ایراد:

زمانی که می‌خواهیم درخت را روی بعد x آن متوازن کنیم، داده‌ساختارهای روی بعد y باید از اول ساخته شوند.

برای اینکه به حالت بهینه برسیم باید هزینه‌ی متوازن کردن با مجموع وزن گره‌های زیرمجموعه‌ی آن گره متناسب باشد.

درخت BB[alpha]-tree

نسبت وزن فرزند چپ و راست یک گره بین alpha,1-alpha است (alpha < 1). پس ارتفاع لگاریتم N است.

برای متوازن کردن از چرخش استفاده می‌کنیم. پیاده‌سازی آن در مدل I/O سخت است. ولی مشکل هزینه‌ی بعد دوم در متوازن کردن را حل می‌کند.

Weigh-balanced B-tree

ترکیب BB[alpha]-tree و B-tree است. به جای اینکه محدودیت درجه داشته باشیم، محدودیت وزن داریم. متوازن کردن آن مشابه B-tree با ادغام و جداسازی گره‌ها انجام می‌شود.

دو پارامتر b و k برای این درخت وجود دارد که برگها بین k/4,k عنصر دارند و گره‌های سطح l وزن بین b^l * k, 1/4*b^l *k دارند. (اصلاحیه: در پست جلسه‌ی سوم درخت (a,b) ریشه بین 2,b عنصر دارد استثناً) ریشه هم باید بیشتر از یک فرزند داشته باشد. در نتیجه‌ی این محدودیت وزن گره‌های میانی بین 1/4b,4b فرزند دارند.

بقیه (حذف و درج) مشابه قبل.

persistent tree:

می‌خواهیم امکان درج و حذف (update) روی داده‌ساختار فعلی داشته باشیم و بتوانیم برای بازه‌ای در گذشته هم پرس‌و‌جو داشته باشیم.

راه حل بدیهی: نگه داشتن یک نسخه از ساختمان داده به ازای هر زمان. (اضافه کردن یک بعد به ساختمان داده برای زمان آن)

ایراد: به روز رسانی زمانی معادل خواندن همه‌ی داده‌ها لازم دارد. زمان ساختمان داده هم به طور مشابه متناسب با خواندن توان دوم اندازه ورودی می‌شود.

راه حل بهتر: به هر عنصر یک بازه‌ی زمانی اضافه کنیم. می‌شود این بازه‌های وجود را با تکرار یک عنصر طوری ساخت که یک B-tree روی عناصر زنده داشته باشیم. برای این کار باید بلوک‌هایی که تعداد عناصر حذف شده (که آنها را فقط علامت می‌زنیم چون بعداً برای کوئری به گذشته لازمشان خواهیم داشت) زیادی دارند را به عنوان حذف شده علامت بزنیم. برای این کار بقیه عناصر بلوک حذف شده را به عنوان عنصر جدید درج می‌کنیم. وقتی یک بلوک حذف می‌شود، در پدر آن اشاره‌گرش را هم به عنوان حذف شده علامت می‌زنیم.

جلسه سوم داده‌های حجیم (درخت جستجو در مدل I/O)

اگر مثل حالت معمولی یک BST بسازیم زمان متناسب با log N می‌شود که زیاد است. ما می‌خواهیم به log_B N برسانیمش. (احتمالاً چون با روشی مثل آخر جلسه‌ی قبل می‌شود ثابت کرد که کران پایینش این است.)

برای این کار از روشی به نام BFS Blocking استفاده می‌کنیم که همان طور که از اسمش پیداست مشابه BFS درخت را بلوک‌بندی می‌کند. این درخت جواب بهینه را به ما می‌دهد که O(log_B N) برای کوئری (ارتفاع درخت) است و برای جستجوی یک بازه و گزارش کردن نقاط آن O( log_B N+ T/B) است. (T تعداد عناصر بازه = اندازه خروجی)

ایراد: برای به روز رسانی این درخت باید مثل AVL-tree زحمت زیادی کشید. در ضمن باید برگ‌ها هم بلوک‌بندی شده باشند (داده‌های آنها پشت سر هم باشد).

راه حل: استفاده از B-tree

به جای اینکه بیایم با متوازن کردن ارتفاع درخت را درست نگه داریم، کافی است روی درجه‌ی خروجی (تعداد فرزندان هر گره) شرط بگذاریم. چون این دلیل اصلی حفظ شدن ارتفاع درخت در BFS-blocking است. برای این کار قرار می‌دهیم درجه‌ی هر رأس theta(B) باشد. با این کار به B-tree می‌رسیم که عمل متوازن کردن در آن با ادغام یا جداکردن گره‌ها انجام می‌شود ولی همیشه درجه‌ی رأسها از مرتبه‌ی B است.

(a,b)-tree درختی است که در آن گره‌های یک سطح بین a تا b عنصر دارند. پس ارتفاع آن حداکثر O(log_a N) است. اگر a و b از مرتبه‌ی B باشند به همان جواب بهینه می‌رسیم. اما حالا این ساختمان داده‌ی جدید برای اضافه‌کردن و حذف کردن عنصر هم مشکلی ندارد و می‌تواند در همان زمان بهینه به این کوئری‌ها هم جواب بدهد. با ادغام و جدا کردن گره‌های میانی هر وقت که از بازه‌ی a,b خارج می‌شوند.

با تحلیل سرشکنی (amortized) می‌شود مقادیر a,b را پیدا کرد که بین دو ادغام و جداشدن به مقدار لازم فاصله باشد که سرشکن آن O(1) شود. (که چون در هر عمق انجام می‌شود لگاریتمی می‌شود).

جلسه دوم داده‌های حجیم (مرتب‌سازی)

در این مدل ترتیب دسترسی به داده‌ها خیلی مهم است. (اگر از قسمت قبل یادتان باشد برای خواندن تصادفی باید زمان متناسب با N مصرف کنیم در حالی که برای خواندن متوالی زمان متناسب با N/B که B یک عدد بزرگ است.)

صف: دو عمل این ساختمان داده اضافه کردن به ابتدا و حذف کردن از انتها است. پس هر کدام یک سری عمل خواندن/نوشتن متوالی است که زمان آن متناسب با میزان داده تقسیم بر B است. پس هر عمل push و pop زمان O(1/B) می‌برد.

پشته: مثل صف می‌شود گفت زمان O(1/B) می‌خواهد.

مرتب‌سازی با استفاده از صف:

ادغام:

کمتر از M/B صف مرتب‌شده داریم. آنها را به این صورت ادغام می‌کنیم که بلوک اول هر کدام را در حافظه‌ی اصلی می‌ریزیم. (چون تعداد لیست‌ها از M/B کمتر است در حافظه جا می‌شود). در هر بار انجام این کار یک بلوک از جواب به دست می‌آید (چون بلوک اول همه‌ی صف‌ها را داریم). آن را در یک صف جدید می‌ریزیم و همین کار را ادامه می‌دهیم. زمان این کار O(N/B) می‌شود.

تقسیم:

برای تقسیم کردن لیست (صف) به کمتر از M/B لیست نامرتب که عناصر هر لیست از لیست بعدی آن کمتر باشد با فرض اینکه مکان برش‌ها (برای حالت دو تایی میانه) را داشته باشیم. هر بلوک را تقسیم می‌کنیم و زمانی که بلوک مربوط به یک صف کامل شد I/O می‌زنیم تا آن را بنویسیم.

مرتب‌سازی ادغامی:

با استفاده از تابع ادغام می‌توانیم با شروع از لیست‌های M عضوی مرتب (چون این تعداد در حافظه جا می‌شود) و ادغام آنها به لیست مرتب شده برسیم. تعداد I/Oها به صورت یک تصاعد هندسی است که جمله‌ی اول آن N/M است (تعداد لیست‌های اولیه) و هر بار چون تعداد لیست‌ها تقسیم بر M/B می‌شود (ادغام می‌شوند)، بر این تعداد تقسیم می‌شود. (چون زمان ادغام متناسب با تعداد لیست‌ها است).

تعمیم مرتب‌سازی سریع:

مشابه قبل می‌شود این کار را انجام داد. فقط یک قسمت می‌ماند که پیدا کردن برش‌ها (مثل میانه) است. از همان الگوریتم میانه پیدا کردن در یک مجموعه استفاده می‌کنیم. اول میانه هر پنج تا عنصر متوالی را پیدا می‌کنیم و بعد یک لیست N/5 عنصری به دست می‌آید که به صورت بازگشتی میانه‌ی آن را حساب می‌کنیم. حالا که میانه را به دست آوردیم لیست‌ها را بر اساس آن دو قسمت می‌کنیم. و همین کار را به صورت بازگشتی ادامه می‌دهیم تا به تعداد برش مورد نیاز برسیم.

تحلیل پیدا کردن میانه (Selection):

؟؟؟

کران پایین مرتب‌سازی در مدل I/O:

باید بعد از یک I/O بگوید چقدر از N! حالت ورودی حذف می‌شوند و فرض کرده M عدد در حافظه است و با یک I/O حداکثر B عنصر خوانده/نوشته می‌شوند و بیشترین تعداد حالت‌هایی که این کار ایجاد می‌کند را حساب می‌کند. بعد تعداد کل حالت‌ها را بر این تقسیم می‌کند. چون به این بیشترین می‌شود رسید مشکلی پیش نمی‌آید. اما اگر نمی‌شد به نظرم باید این را هم حساب می‌کرد که آیا واقعاً می‌شود که چنین اتفاقی بیفتد یا نه. (پر بودن حافظه و ...)

جلسه اول داده‌های حجیم

تعریف مدل I/O:

مدل حافظه خارجی (External Memory) که به آن مدل آگاه از کش (Cache Aware) هم می‌گویند. در این مدل ما اندازه‌ی بلوک دیسک (B) و اندازه‌ی حافظه RAM یعنی M را می‌دانیم. هدف این است که با کمترین تعداد I/O، (در هر I/O یک بلوک از حافظه خوانده یا نوشته می‌شود) را به دست آوریم.

در این مدل فرض می‌کنیم که M>B^2 است. (در یک سری الگوریتم‌ها لازم می‌شود!)

زمان عملیات متداول در این مدل:

خواندن متوالی: در حالت عادی زمان آن متناسب با N (تعداد عناصر ورودی) است اما اینجا N/B است چون Bتا Bتا خوانده می‌شود.

مرتب‌سازی: در حالت عادی زمان آن N log N است اما اینجا N/B log_(M/B) N/B است.

جایگشت دادن: (فکر کنم منظور پیدا کردن جایگشت بعدی باشد) درحالت عادی زمان N می‌برد، در این مدل زمان مینیمم N و N/B log_(M/B) N/B می‌برد.

جستجو: در حالت عادی (جستجوی دودویی) زمان log N می‌برد. اینجا زمان log_B N می‌برد.

* B خیلی در این روابط مهم است چون بزرگ است و باعث می‌شود مثلاً N/B<<N باشد.

مدل بی‌خبر از کش:

در این مدل ما B را نمی‌دانیم و می‌تواند حتی سلسله مراتبی باشد. برای حالت سلسله مراتبی من اولش فکر می‌کردم باید یک B معادل پیدا کنیم اما الآن دیدم نوشته است که به ازای هر مرحله‌ی کش یک بار اجرای الگوریتم را در نظر می‌گیریم. یعنی مثل این است که به تعداد سلسله مراتب آن داریم مسأله را حل می‌کنیم. (این مدل پروژه کارشناسی ارشد یک نفر توی ام‌آی‌تی بوده!)

مدل جویباری:

در این مدل دسترسی تصادفی به داده‌ها نداریم بلکه تصادفی متوالی به صورت یکی یکی در چند جریان داریم. عوامل مهم در کارایی یک الگوریتم جویباری تعداد بارهایی که کل داده‌ها (جویبار) را می‌خوانیم، حافظه‌ی در دسترس و زمان اجرای الگوریتم است.

درس داده‌های حجیم در دانشگاه‌های دیگر

http://www.cs.utah.edu/~jeffp/teaching/MCMD.html

http://algo2.iti.kit.edu/sanders/courses/algen09-10/rdslides.pdf

http://cs.yazd.ac.ir/farshi/Teaching/IO-Efficient-Alg-3912/IO-Eff.html

Massive Data Algorithmics

http://users-cs.au.dk/large/ioS12/