بنیاد — ساختمان داده و الگوریتم، با اندازه‌گیری واقعی

فصل ۳ از ۹

پیشرفت ترم
۰٪

در این فصل چه یاد می‌گیری#

فصلِ قبل با یک تناقض تمام شد: بعضی از appendها یک کپیِ کاملِ O(n) هستند، پس چرا ساختنِ یک list بزرگ با append سریع است؟

این فصل جوابش را با سه اندازه‌گیری می‌دهد. اول تک‌تکِ چهارصد هزار append را جدا می‌سنجیم و گران‌ترین‌هایشان را پیدا می‌کنیم — که هزاران برابر بقیه‌اند و همه دقیقاً روی لحظه‌های بزرگ‌شدن افتاده‌اند. بعد نشان می‌دهیم میانگینِ همان‌ها صاف است. و آخر می‌بینیم که اگر ظرفیت به‌جای ضرب‌شدن هر بار مقدارِ ثابتی اضافه می‌شد، کلِ ماجرا O(n²) می‌شد.

بینِ راه یک انتظارِ کتابِ درسی هم می‌شکند: ظرفیتِ list پایتون دو برابر نمی‌شود. ضریبش را اندازه می‌گیریم.

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

آخر این فصل می‌توانی:

  • بگویی «هزینهٔ amortised» چه چیزی را ادعا می‌کند و چه چیزی را ادعا نمی‌کند
  • گران‌ترین تکِ عملیات را از میانگینِ بلندمدتش جدا کنی و هر دو را گزارش کنی
  • نشان بدهی چرا رشدِ ضربیِ ظرفیت لازم است و رشدِ ثابت فاجعه است

قبل از شروع#

از فصلِ ۲: ظرفیت در برابرِ طول، تابعِ capacity، و اینکه هر بزرگ‌شدن یک کپیِ کامل است.

اجرا زمانِ تقریبی
CPU (پیش‌فرضِ Colab) حدودِ یک دقیقه

📓 نوت‌بوک: نوت‌بوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

۱. ظرفیت واقعاً چند برابر می‌شود؟#

فصلِ قبل از روی «شش پله برای هر دو برابر شدن» حدس زد که ضریبِ رشد حدودِ 1.12 است. حالا مستقیم اندازه‌اش می‌گیریم.

🤔 اول حدس بزن: بیشترِ کتاب‌ها می‌گویند آرایهٔ پویا ظرفیتش را دو برابر می‌کند. بنویس انتظار داری ستونِ «نسبت به قبلی» در این جدول چه عددی بدهد.

CELL = 8
EMPTY = sys.getsizeof([])


def capacity(values):
    return (sys.getsizeof(values) - EMPTY) // CELL


steps = []
values = []
cap = 0
for i in range(20_000):
    values.append(i)
    new = capacity(values)
    if new != cap:
        steps.append(new)
        cap = new

print(f"{'ظرفیت':>10}{'نسبت به قبلی':>16}")
for a, b in zip([None] + steps[:-1], steps):
    print(f"{b:>10}" + (f"{'—':>16}" if a is None else f"{b / a:>16.3f}"))
print(f"\nتعدادِ پله‌ها تا بیست هزار: {len(steps)}")
     ظرفیت    نسبت به قبلی
         4               —
         8           2.000
        16           2.000
        24           1.500
        32           1.333
        40           1.250
        52           1.300
        64           1.231
        76           1.188
        92           1.211
       108           1.174
       128           1.185
       148           1.156
       172           1.162
       200           1.163
       232           1.160
       268           1.155
       308           1.149
       352           1.143
       400           1.136
       456           1.140
       520           1.140
       592           1.138
       672           1.135
       760           1.131
       860           1.132
       972           1.130
      1100           1.132
      1244           1.131
      1404           1.129
      1584           1.128
      1788           1.129
      2016           1.128
      2272           1.127
      2560           1.127
      2884           1.127
      3248           1.126
      3660           1.127
      4124           1.127
      4644           1.126
      5228           1.126
      5888           1.126
      6628           1.126
      7460           1.126
      8396           1.125
      9452           1.126
     10640           1.126
     11976           1.126
     13480           1.126
     15172           1.126
     17072           1.125
     19212           1.125
     21620           1.125

تعدادِ پله‌ها تا بیست هزار: 53

ضریب از 2.000 شروع می‌کند و به 1.125 می‌رسد و همان‌جا می‌ماند.

پس آن جملهٔ کتابِ درسی — «ظرفیت دو برابر می‌شود» — برای این پیاده‌سازی غلط است. فقط دو پلهٔ اولش دو برابر است و بقیه یک‌هشتم اضافه می‌کنند.

و این دقیقاً همان لحظه‌ای است که این دوره برایش ساخته شده: یک جملهٔ درست‌به‌نظر، یک اندازه‌گیریِ پنج‌خطی، و یک عددِ متفاوت. جمله را نپذیر؛ عدد را بگیر.

ولی حالا سؤالِ مهم‌تر: آیا 1.125 هم مثلِ 2 کافی است؟ جوابش را بخشِ ۴ می‌دهد و جواب مثبت است — چیزی که اهمیت دارد ضربی بودن است، نه خودِ عددِ دو.

۲. تک‌تکِ appendها#

حالا سراغِ چیزی می‌رویم که تا اینجا هیچ‌وقت نکرده‌ایم: به‌جای زمانِ کلِ حلقه، زمانِ تک‌تکِ عملیات را می‌گیریم.

🤔 اول حدس بزن: چهارصد هزار append می‌زنیم و هر کدام را جدا می‌سنجیم. بنویس گران‌ترینشان نسبت به میانه چند برابر می‌شود: ده؟ صد؟ بیشتر؟

N = 400_000
now = time.perf_counter

values = []
per_op = []
for i in range(N):
    start = now()
    values.append(i)
    per_op.append(now() - start)

ordered = sorted(per_op)
print(f"میانهٔ هر append   : {1e6 * ordered[N // 2]:>10.4f} µs")
print(f"گران‌ترین append   : {1e6 * ordered[-1]:>10.4f} µs")
print(f"نسبتِ گران‌ترین به میانه: {ordered[-1] / max(ordered[N // 2], 1e-9):>10,.0f} برابر")
print(f"مجموعِ همه         : {1000 * sum(per_op):>10.1f} ms")
میانهٔ هر append   :     0.1000 µs
گران‌ترین append   :   590.9000 µs
نسبتِ گران‌ترین به میانه:      5,909 برابر
مجموعِ همه         :       57.0 ms

گران‌ترین append هزاران برابرِ میانه است. پس «append ارزان است» به‌عنوانِ یک جملهٔ سرراست غلط است.

میانه آن‌قدر کوچک است که به حدِ تفکیکِ ساعت می‌خورد — همان چیزی که فصلِ ۲ ترمِ ۱ درباره‌اش هشدار داد. برای همین این عدد را به‌عنوان یک اندازه‌گیریِ دقیق نمی‌خوانیم؛ فقط می‌گوییم «زیرِ حدِ تفکیک». چیزی که واقعاً می‌خواهیم بدانیم این است که گران‌ها کجا افتاده‌اند.

۳. گران‌ها کجا افتاده‌اند؟#

اگر توضیحِ فصلِ ۲ درست باشد، گران‌ترین appendها باید دقیقاً روی اندیس‌هایی باشند که ظرفیت در آن‌ها عوض شده. این یک پیش‌بینیِ آزمون‌پذیر است.

یک نکتهٔ نحوی در کدِ زیر که فعلاً فقط باید بشناسی‌اش: sorted(..., key=...) یعنی «مرتب کن، ولی نه بر اساسِ خودِ عضوها — بر اساسِ چیزی که این تابع از هر عضو درمی‌آورد». این‌جا عضوها اندیس‌اند و کلیدِ مرتب‌سازی -per_op[i] است، یعنی زمانِ هر عمل با علامتِ منفی، تا کندترین‌ها اول بیایند. ترمِ ۴ فصلِ ۸ کاملاً بازش می‌کند؛ تا آن‌جا هر بار که ببینی‌اش همین یک جمله کافی است.

grown_at = []
probe = []
cap = 0
for i in range(N):
    probe.append(i)
    new = capacity(probe)
    if new != cap:
        grown_at.append(i)
        cap = new
grown = set(grown_at)

slowest = sorted(range(N), key=lambda i: -per_op[i])[:12]
total = sum(per_op)
on_growth = sum(per_op[i] for i in grown_at)
print("تعدادِ کلِ بزرگ‌شدن‌ها در این مسیر:", len(grown_at))
print("کندترین دوازده append روی این اندیس‌ها افتادند:")
print(" ", sorted(slowest))
print("چند تایشان دقیقاً روی یک بزرگ‌شدن بود؟",
      sum(1 for i in slowest if i in grown), "از ۱۲")
print(f"\nسهمِ این {len(grown_at)} عمل از تعدادِ کلِ عملیات: "
      f"{100 * len(grown_at) / N:.3f} درصد")
print(f"سهمِ همان‌ها از کلِ زمان                : {100 * on_growth / total:.1f} درصد")
del probe, per_op
تعدادِ کلِ بزرگ‌شدن‌ها در این مسیر: 78
کندترین دوازده append روی این اندیس‌ها افتادند:
  [88988, 112636, 126720, 142564, 160388, 180440, 203000, 228380, 256932, 289052, 325188, 365840]
چند تایشان دقیقاً روی یک بزرگ‌شدن بود؟ 12 از ۱۲

سهمِ این 78 عمل از تعدادِ کلِ عملیات: 0.019 درصد
سهمِ همان‌ها از کلِ زمان                : 8.9 درصد

تقریباً همه‌شان. گاهی هر دوازده‌تا و گاهی یازده‌تا — آن یکی معمولاً لحظه‌ای است که سیستم‌عامل وسطِ کار پرید، همان نویزِ فصلِ ۳ ترمِ ۱. پیش‌بینی درست درآمد و توضیحِ فصلِ ۲ تأیید شد.

ولی دو سطرِ آخر مهم‌ترند، چون به نویز بند نیستند: آن هفتاد و هشت عمل صدمِ درصدِ کلِ عملیات‌اند و چند درصدِ کلِ زمان را می‌خورند. یعنی چند صد برابرِ سهمِ عادلانه‌شان.

و به فاصلهٔ اندیس‌ها نگاه کن: هرچه جلوتر می‌رویم، بزرگ‌شدن‌ها دیرتر به دیرتر اتفاق می‌افتند — چون ظرفیت ضربی رشد می‌کند و هر بار جای بیشتری باز می‌شود.

📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ اندیسِ دوازده کندترین append با فهرستِ اندیس‌هایی که ظرفیت در آن‌ها عوض شد — دو اندازه‌گیریِ کاملاً مستقل روی همان دنبالهٔ عملیات. در کدام بازهٔ n؟ یک مسیرِ چهارصد هزارتایی، از صفر تا n. با چند تکرار، و کمینه یا میانگین؟ یک اجرا و بدونِ خلاصه — چون سؤال دربارهٔ جای گران‌ها است نه اندازه‌شان، و جایشان قطعی است.

۴. پس چرا کلِ ساختن ارزان است؟#

append گاهی O(n) است. ولی آن «گاهی» چقدر است؟ جوابش را می‌شود بدونِ ساعت شمرد: مدلی می‌سازیم که فقط تعدادِ عنصرهای جابه‌جاشده را می‌شمارد.

🤔 اول حدس بزن: برای دو حالت حدس بزن — ظرفیتی که هر بار دو برابر می‌شود و ظرفیتی که هر بار صد و بیست و هشت خانه اضافه می‌کند. ستونِ نسبتِ هر کدام چه عددی می‌دهد؟

def copied_multiplicative(n, factor=2):
    """ظرفیت هر بار در factor ضرب می‌شود."""
    cap, copied = 0, 0
    for size in range(1, n + 1):
        if size > cap:
            copied += size - 1              # همهٔ عناصرِ قبلی منتقل می‌شوند
            cap = max(cap + 1, int(cap * factor))
    return copied


def copied_constant(n, step=128):
    """ظرفیت هر بار step خانه اضافه می‌کند."""
    cap, copied = 0, 0
    for size in range(1, n + 1):
        if size > cap:
            copied += size - 1
            cap += step
    return copied


LADDER = [10_000, 20_000, 40_000, 80_000]
print("— ظرفیت هر بار دو برابر می‌شود")
table([(n, copied_multiplicative(n)) for n in LADDER], "عنصرِ منتقل‌شده", ",d")
print("\n— ظرفیت هر بار ۱۲۸ خانه اضافه می‌کند")
table([(n, copied_constant(n)) for n in LADDER], "عنصرِ منتقل‌شده", ",d")
print("\n— ظرفیت هر بار در ۱٫۱۲۵ ضرب می‌شود (کارِ خودِ پایتون)")
table([(n, copied_multiplicative(n, 1.125)) for n in LADDER], "عنصرِ منتقل‌شده", ",d")
— ظرفیت هر بار دو برابر می‌شود
         n   عنصرِ منتقل‌شده     نسبت به سطر قبل
    10,000            16,383                   —
    20,000            32,767                2.00
    40,000            65,535                2.00
    80,000           131,071                2.00

— ظرفیت هر بار ۱۲۸ خانه اضافه می‌کند
         n   عنصرِ منتقل‌شده     نسبت به سطر قبل
    10,000           394,368                   —
    20,000         1,567,488                3.97
    40,000         6,249,984                3.99
    80,000        24,960,000                3.99

— ظرفیت هر بار در ۱٫۱۲۵ ضرب می‌شود (کارِ خودِ پایتون)
         n   عنصرِ منتقل‌شده     نسبت به سطر قبل
    10,000            88,035                   —
    20,000           178,286                2.03
    40,000           321,112                1.80
    80,000           650,744                2.03

سه جدول، دو دنیای متفاوت.

  • رشدِ ضربی — چه با ضریبِ 2 و چه با 1.125 — ستونِ نسبتِ 2.00 می‌دهد. یعنی کلِ کارِ انتقال روی n بار append، خودش O(n) است. تقسیمش بر n می‌شود یک عددِ ثابت.
  • رشدِ ثابت ستونِ نسبتِ 4.00 می‌دهد: O(n²). برای هشتاد هزار عضو نزدیکِ بیست و پنج میلیون عنصر جابه‌جا می‌شود، در حالی که نسخهٔ ضربی با ضریبِ 2 حدودِ صد و سی هزارتا و با ضریبِ واقعیِ پایتون حدودِ ششصد و پنجاه هزارتا — یعنی در بدترین حالت هم نزدیکِ چهل برابر کمتر.

و همین‌جا کلِ حرفِ فصل است: هزینهٔ amortised یعنی هزینهٔ کلِ یک دنبالهٔ عملیات، تقسیم بر تعدادشان. برای append این عدد ثابت است، پس می‌گوییم «append هزینهٔ O(1)ِ amortised دارد».

و دقت کن این جمله چه چیزی را ادعا نمی‌کند: ادعا نمی‌کند هیچ appendی گران نیست. بخشِ ۲ خلافش را نشان داد. ادعا می‌کند گران‌ها آن‌قدر کم‌اند که وقتی خرجشان بینِ همه پخش شود، سهمِ هرکس ثابت می‌ماند.

🌱 ریشه‌اش کجاست: چرا مجموعِ انتقال‌ها O(n) درمی‌آید؟ چون اگر ظرفیت دو برابر شود، انتقال‌ها 1 + 2 + 4 + … + n می‌شوند و مجموعِ توان‌های دو همیشه کمتر از دو برابرِ آخرینشان است. توان و دو برابر کردنِ پیاپی در ریشه ترمِ ۱ فصل ۸ ساخته می‌شود.

و برای هر ضریبِ دیگری هم می‌شود همین را نوشت. آخرین انتقال حدودِ n عضو جابه‌جا می‌کند، انتقالِ قبلی‌اش n ÷ f، آن یکی n ÷ f²، و همین‌طور. جمعِ این دنباله دو کران دارد که هر دو ضریبی ثابت از n هستند:

n ÷ (f - 1)   ≤   مجموعِ کلِ انتقال‌ها   ≤   n × f ÷ (f - 1)

دو کران لازم است، نه یک فرمولِ دقیق — چون عددِ واقعی به این بستگی دارد که n کجای فاصلهٔ بینِ دو بزرگ‌شدنِ متوالی افتاده باشد. بیایید هر دو کران را با شمارنده وارسی کنیم:

print(f"{'ضریب':>8}{'شمردهٔ واقعی':>20}{'n ÷ (f-1)':>16}{'n × f ÷ (f-1)':>18}")
for f in (2, 1.125, 1.05):
    got = copied_multiplicative(80_000, f)
    print(f"{f:>8}{got:>20,}{80_000 / (f - 1):>16,.0f}{80_000 * f / (f - 1):>18,.0f}")
    ضریب        شمردهٔ واقعی       n ÷ (f-1)     n × f ÷ (f-1)
       2             131,071          80,000           160,000
   1.125             650,744         640,000           720,000
    1.05           1,621,558       1,600,000         1,680,000

هر سه عددِ شمرده‌شده داخلِ کرانِ خودشان‌اند، و مهم‌ترین ستون ستونِ سوم است. f = 2 می‌دهد n، f = 1.125 می‌دهد هشت برابرِ n، و f = 1.05 بیست برابرِ n. هر سه ضریبِ ثابت‌اند و ثابت یعنی O(n) — ولی ثابتشان بیست برابر با هم فرق دارد، و همین دلیلِ اینکه هیچ پیاده‌سازی‌ای ضریبِ رشد را 1.05 نمی‌گذارد.

✅ چک کن: قبل از هر اجرایی، از همان کران n ÷ (f - 1) پیش‌بینی کن که copied_multiplicative(80_000, 1.05) چند درمی‌آید، بعد اجرایش کن و خطای پیش‌بینی‌ات را بنویس. حالا جدولِ چهار اندازه‌ایِ همان ضریب را بگیر: عدد باید حدودِ دوازده برابرِ ضریبِ 2 باشد ولی ستونِ نسبت هنوز 2.00 بماند. اگر ستونِ نسبت به 4 رفت، factor را زیرِ یک گذاشته‌ای و ظرفیت اصلاً بزرگ نمی‌شود.

۵. زمانِ واقعی، برای همان ادعا#

شمارش می‌گوید کلِ ساختن O(n) است. ساعت هم باید همین را بگوید.

def build(n):
    out = []
    for i in range(n):
        out.append(i)
    return out


BUILD = [200_000, 400_000, 800_000, 1_600_000]
table([(n, 1000 * clock(lambda k=n: build(k), repeat=3)) for n in BUILD])
print("\nهر append به‌طورِ متوسط:",
      f"{1e9 * clock(lambda: build(1_600_000), repeat=3) / 1_600_000:.1f} نانوثانیه")
         n         زمان (ms)     نسبت به سطر قبل
   200,000               7.3                   —
   400,000              16.5                2.27
   800,000              39.7                2.40
 1,600,000              75.1                1.89

هر append به‌طورِ متوسط: 46.3 نانوثانیه

ستونِ نسبت نزدیکِ 2 است. ساعت و شمارنده یک چیز می‌گویند: n بار append روی هم O(n) است.

🔧 اگر کار نکرد: اگر خواستی همین اندازه‌گیری را روی یک list که از قبل ساخته شده انجام بدهی، تلهٔ فصلِ ۳ ترمِ ۱ برمی‌گردد — اندازه‌گیریِ گرم. این‌جا شکلِ دیگری دارد:

shared = []
warm = 1000 * clock(lambda: shared.append(1), repeat=5)
print(f"زمانِ یک append روی ظرفِ مشترک: {warm:.6f} ms")
print(f"طولِ ظرف بعد از اندازه‌گیری   : {len(shared):,}")
زمانِ یک append روی ظرفِ مشترک: 0.000100 ms
طولِ ظرف بعد از اندازه‌گیری   : 6

عددِ زمان بی‌معناست و سطرِ دوم دلیلش را لو می‌دهد: clock شش بار تابع را صدا زد و هر بار یک عضو اضافه شد، پس اندازه‌گیری روی شش ظرفِ متفاوت انجام شده. هر اندازه‌گیری باید ظرفِ تازهٔ خودش را داشته باشد — همان قاعدهٔ «ورودیِ دست‌نخورده».

🤖 از دستیارت بپرس: «تفاوتِ هزینهٔ amortised و هزینهٔ بدترین حالت چیست؟» بعد این را هم بپرس: «در چه نوع برنامه‌ای هزینهٔ amortised جوابِ درست نیست و باید بدترین تک‌عملیات را گزارش کرد؟» — یکی از جواب‌های درست برنامه‌ای است که باید در یک مهلتِ ثابت جواب بدهد؛ آن‌جا یک append هزار برابری همان چیزی است که مهلت را می‌شکند، هرچقدر هم که میانگین خوب باشد.

واژه‌های تازهٔ این فصل#

کلمه تلفظ به حروف فارسی یعنی چه
amortised cost اِمورتایزد کاست هزینهٔ کلِ یک دنبالهٔ عملیات، تقسیم بر تعدادشان
worst-case cost ورست‌کیس کاست گران‌ترین تکِ عملیاتِ ممکن
growth factor گروث فکتور عددی که ظرفیت هر بار در آن ضرب می‌شود

تمرین‌ها

اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.

در فصل بعد#

سه فصل است داریم دربارهٔ انتهای ظرف حرف می‌زنیم: append در انتها، بزرگ‌شدن در انتها، خانهٔ خالی در انتها.

فصلِ بعد به ابتدای ظرف نگاه می‌کند و همه‌چیز عوض می‌شود. یک جدولِ دوبرابری برای append می‌گیریم و یکی برای insert(0, x): ستونِ اولی نزدیکِ 2 است و دومی نزدیکِ 4. بعد ظرفِ دیگری معرفی می‌شود که همان کارِ ابتدای ظرف را دوباره صاف می‌کند — و آن هم با جدول اثبات می‌شود، نه با ادعا.

به آخر این فصل رسیدی!

اگر ساختی و جواب داد، این دکمه مال توست.