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

این تمرین تئوری کسی بوده است که مقاله‌اش منبع درس است.

http://www.daimi.au.dk/~large/ioS13/project3.pdf

جواب‌ها:

۱- کافی است وقتی که در حافظه‌ی اصلی تکراری دیدیم حذفش کنیم و فقط یکی ازش نگه داریم.

در بهترین حالت همه‌ی اعداد یکسان پشت سر هم میان و زمان حذف کردنشان میشه Sort(Ni). پس حداقل این قدر زمان از کل زمان کم میشه.

اگر همه مساوی باشند جمله‌ی اولی صفر می‌شود. پس باید در نظر بگیریم که حداقل به اندازه‌ی خواندن همه‌ی ورودی زمان لازم داریم.

۲- پیمایش لیست‌ها زمان خطی می‌برد پس نمی‌شود از درخت بازه استفاده کرد. به جای آن از 2d range-tree استفاده می‌کنیم که برای پیاده‌سازی‌اش باید از Weighted B-tree استفاده کنیم. فقط هم باید این تغییر را بدهیم که در گره‌های میانی وقتی دیدیم یک زیردرخت کامل جزو جواب است همانجا تعدادش را برگردانیم و دیگر ادامه ندهیم.

۳- الگوریتم جاروب Bentley را با جاروب توزیع شده پیاده سازی می‌کنیم.