انتقال به جلو (Move-to-Front)
لیستی که خودش را سازمان می‌دهد: هر عضوی که درخواست شد به جلوی لیست می‌رود، پس عضوهای پرکاربرد جلو می‌مانند؛ هزینه‌اش حداکثر ۴ برابر بهترین روش آفلاین است.
در یک لیست پیوندی، پیدا کردن عضو kام k قدم طول می‌کشد. اگر بعضی عضوها بیشتر درخواست شوند، بهتر است جلوی لیست باشند. ولی ما از قبل نمی‌دانیم کدام‌ها؛ الگوریتم باید آنلاین تصمیم بگیرد.
- زمان:
O(position) per request - حافظه:
O(1) extra - CLRS، فصل ۲۷
لیست اولیه ۱ ۲ ۳ ۴ ۵ است و درخواست‌ها چند بار به ۴ و ۵ برمی‌گردند؛ بعد از اولین بار، آن‌ها جلوی لیست‌اند و ارزان‌اند.
def move_to_front(L, R):lst = list(L[0])cells = [lst] # for the picture: the list as one table rowcost = 0for x in R[0]:i = 0while i < len(lst) and lst[i] != x:i = i + 1if i == len(lst):lst.append(x)cost = cost + i + 1lst.pop(i)lst.insert(0, x)return cost
شروع اجرا
جدول هنوز خالی است.
متغیرهای محلی
نارنجی = در همین گام عوض شد
L list
R list
Call stack
- move_to_front()خط 1
توضیح
ایده
در یک لیست پیوندی، پیدا کردن عضو kام k قدم طول می‌کشد. اگر بعضی عضوها بیشتر درخواست شوند، بهتر است جلوی لیست باشند. ولی ما از قبل نمی‌دانیم کدام‌ها؛ الگوریتم باید آنلاین تصمیم بگیرد.
انتقال به جلو ساده‌ترین قاعده است: هر عضوی که درخواست شد، به جلوی لیست برود. قاعده‌های دیگر:
- جابه‌جایی (Transpose): عضو درخواست‌شده فقط با عضو جلوی خودش جابه‌جا شود.
- شمارش بسامد: لیست به ترتیب تعداد درخواست‌ها مرتب بماند.
تحلیل رقابتی
Sleator و Tarjan نشان دادند هزینه‌ی انتقال به جلو روی هر دنباله‌ی درخواست حداکثر ۴ برابر هزینه‌ی بهترین روش آفلاین است که همه‌ی درخواست‌ها را از قبل می‌داند (با شمارش جابه‌جایی‌ها). برای Transpose چنین ضمانتی وجود ندارد.
ورودی
L لیست اولیه است و R درخواست‌ها. درخواستی که در لیست نیست به ته لیست اضافه می‌شود.