جدول پویا (تحلیل سرشکن)

آرایه‌ای که هر وقت پر شد دو برابر می‌شود؛ کپی‌ها گاهی گران‌اند ولی هزینه‌ی سرشکن هر درج حداکثر ۳ است.

آرایه‌ای می‌خواهیم که هر چقدر بخواهیم در آن درج کنیم. وقتی جدول پر شد، جدولی دو برابر بزرگ‌تر می‌سازیم و همه‌ی عضوها را در آن کپی می‌کنیم.

ادامه‌ی توضیح ↓

زمان: O(1) amortized per insert
حافظه: O(n)
CLRS، بخش ۱۶.۴

ورودی:

n=9خروجی PDF

۹ درج؛ جدول در درج‌های ۲، ۳، ۵ و ۹ بزرگ می‌شود و ۱+۲+۴+۸ = ۱۵ کپی لازم است. هزینه‌ی کل ۲۴، کمتر از ۳ × ۹.

def dynamic_table(items):
capacity = 1
table = [None]
size = 0
copies = 0
for item in items:
if size == capacity:
capacity = 2 * capacity
bigger = [None] * capacity
for i in range(size):
bigger[i] = table[i]
copies = copies + 1
table = bigger
table[size] = item
size = size + 1
return size + copies

ناوردا: بعد از هر درج، تعداد کل کپی‌ها از دو برابر تعداد عضوها کمتر است، پس هزینه‌ی کل حداکثر ۳n است.

شروع اجرا

متغیرهای محلی

نارنجی = در همین گام عوض شد

`items` list

538192746

Call stack

dynamic_table()خط 1

گام ۱ از ۱۰۴

رشد تعداد عملیات با اندازه‌ی ورودی

میانگین ۱۲ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.

insert
copy
ورودی فعلی (n=9)

نمایش به شکل جدول

n	insert	copy
4	4	3
6	6	7
8	8	7
10	10	15
12	12	15
14	14	15
16	16	15

توضیح

ایده

تحلیل سرشکن

یک درج تکی ممکن است گران باشد (کپی کل جدول)، ولی این گرانی‌ها نادرند. بعد از n درج، کپی‌ها 1 + 2 + 4 + … < 2n هستند؛ پس هزینه‌ی کل کمتر از 3n و هزینه‌ی سرشکن هر درج O(1) است.

روش حسابداری: برای هر درج ۳ سکه بپرداز: یکی برای خود درج، یکی برای کپی آینده‌ی همین عضو و یکی برای کپی آینده‌ی یک عضو قدیمی‌تر. سکه‌ها همیشه کافی‌اند.

در trace به چه چیزی نگاه کنی

میله‌ها جدول فعلی‌اند و خانه‌های خالی هم دیده می‌شوند.
نمودار رشد نشان می‌دهد تعداد کپی‌ها خطی رشد می‌کند، نه درجه دو.