جلسه سوم داده‌های حجیم (درخت جستجو در مدل 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/

پایان ترم الگوریتم پیشرفته

۱- از یک زمانبند حریصانه استفاده می‌کنیم. اگر زمان اجرای یک الگوریتم روی ۴ پردازنده ۲۶۰ ثانیه و روی ۳۲ پردازنده ۹۰ ثانیه باشد؛ آیا مقادیر T1=1024 و Tinfinity = 64 می‌توانند مقادیر معتبری باشند؟

۲-  الگوریتم push-relabel را روی گراف زیر اجرا کنید که همه‌ی یالهای آن وزن ۲ دارند به جز یال آخر که وزن ۱ دارد.

s->v1->....->vn->t

تعداد pushها و تعداد relabelها و زمان الگوریتم را حساب کنید.

۳- یک الگوریتم موازی برای محاسبه‌ی ترانهاده‌ی ماتریس X که n*n است بنویسید و کار و زمان و موازات آن را حساب کنید.

۴- یک شبکه شار داریم که یالهای آن آبی یا قرمز هستند. یالهای آبی ظرفیت ce دارند و یالهای قرمز کران پایین de دارند. شار بیشینه را می‌خواهیم به دست بیاوریم.

الف) برای آن یک LP بنویسید و ثابت کنید زمان آن خطی است.

ب) ثابت کنید اگر یالهای قرمز را بتوانیم خاموش و روشن کنیم؛ مسأله‌ی اینکه این گراف شار k دارد یا نه، np-complete است. (از subset-sum کمک بگیرید.)

۵- ثابت کنید دور فروشنده دوره‌گرد را نمی‌توان بهتر از یک تابع چندجمله‌ای بر حسب n تقریب زد.

۶- تابع پیشوندی در الگوریتم KMP را بنویسید و تحلیل کنید.

تمرین‌های الگوریتم پیشرفته

تمرین‌های کتاب که فقط شماره‌ی آنها داده شده بود. (این همه‌ی تمرین‌ها نیست)

Decentralized utilitarian mechanisms for scheduling games

http://www.sciencedirect.com/science/article/pii/S0899825613000560

Optimal Revenue-Sharing Double Auctions with Applications to Ad Exchanges

http://wwwconference.org/proceedings/www2014/proceedings/p19.pdf

Bicriteria Online Matching: Maximizing Weight and Cardinality

http://madalgo.au.dk/fileadmin/madalgo/OA_PDF_s/C312.pdf