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

فصل ۳ از ۶

پیشرفت ترم
۰٪

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

یک index می‌سازیم و پرسش‌ها را از حدودِ دو میلی‌ثانیه به کسری از یک میکروثانیه می‌رسانیم — بیش از بیست‌وپنج هزار برابر. بعد قیمتش را به بایت اندازه می‌گیریم، و می‌بینیم که هر عبارتِ اضافه حدودِ ۸٫۵ بایت به آن اضافه می‌کند.

بعد سراغِ چیزی می‌رویم که همهٔ فصل‌های قبلی فرض گرفته بودند حل است: جا شدن. یک indexِ کامل‌ترِ همان مسئله را حساب می‌کنیم که در اندازهٔ کوچکش هشت مگابایت است و در اندازهٔ واقعی‌اش حدودِ هفتاد و پنج گیگابایت — و همان‌جا انتخابِ «واضح» برمی‌گردد سرِ جای اول، نه چون کند است، چون اصلاً وجود ندارد.

دو کفهٔ ترازو که یکی ساعت و دیگری انبارِ قفسه‌دار روی آن است

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

  • هزینهٔ حافظهٔ یک index را به بایت اندازه بگیری، نه حدس بزنی
  • معامله را به‌شکلِ یک نرخ بنویسی و بگویی آن نرخ «به‌ازای هر چه» است
  • تشخیص بدهی کِی دیوارِ مسئله حافظه است نه زمان
  • ساختاری را رد کنی که سریع‌تر است ولی در بازهٔ nِ تو ساخته نمی‌شود

قبل از شروع#

از ترمِ ۳ فصلِ ۵: dict و هزینهٔ ساختِ اولیه‌اش. از ترمِ ۲ فصلِ ۸: sys.getsizeof و اینکه list ارجاع نگه می‌دارد نه مقدار. از فصلِ ۱: برگهٔ شکلِ مسئله.

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

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

۱. مسئله، و شکلش#

فهرستی از عبارت داریم و پرسش این است: «کدام عبارت‌ها با این سه حرف شروع می‌شوند؟»

شکلِ مسئله، قبل از هر کدی: فهرست یک بار ساخته می‌شود و بعد q بار پرسیده می‌شود؛ هیچ درجی بعد از ساخت نداریم. پس نسبتِ خواندن به نوشتن بالاست و — طبقِ فصلِ ۱ — این همان خانه‌ای است که تصمیم را تعیین می‌کند. بازهٔ n: ده هزار تا هشتاد هزار عبارت.

LETTERS = "abcdefghij"
PREFIX = 3


def make_terms(n, seed=SEED):
    """n عبارتِ یکتا از یک الفبای ده‌حرفی."""
    rng = random.Random(seed)
    seen, out = set(), []
    while len(out) < n:
        word = "".join(rng.choice(LETTERS) for _ in range(rng.randint(6, 10)))
        if word not in seen:
            seen.add(word)
            out.append(word)
    return out


LADDER = [10_000, 20_000, 40_000, 80_000]
terms = {n: make_terms(n) for n in LADDER}
print("سه عبارتِ اول:", terms[10_000][:3])
print("پیشوندِ سه‌حرفیِ ممکن:", len(LETTERS) ** PREFIX)
سه عبارتِ اول: ['babjabbfd', 'aafjhj', 'cbcbaihdb']
پیشوندِ سه‌حرفیِ ممکن: 1000

الفبا عمداً ده حرف است، نه بیست و شش: با ده حرف تعدادِ پیشوندهای ممکن هزار تاست و هر پیشوند bucketِ پُری دارد. با بیست و شش حرف بیشترِ bucketها یک‌نفره می‌شدند و هیچ‌کدام از جدول‌های این فصل چیزی نشان نمی‌داد.

۲. دو نامزد، یک جواب#

def by_scan(items, prefix):
    """نامزد ۱ — هیچ ساختی، همهٔ عبارت‌ها را در هر پرسش ببین."""
    hits = []
    for term in items:
        if term.startswith(prefix):
            hits.append(term)
    return hits


def build_index(items):
    """نامزد ۲ — یک بار بساز: پیشوند به فهرستِ عبارت‌ها."""
    index = {}
    for term in items:
        index.setdefault(term[:PREFIX], []).append(term)
    return index


index = {n: build_index(terms[n]) for n in LADDER}
picker = random.Random(SEED)
asks = {n: [t[:PREFIX] for t in picker.sample(terms[n], 200)] for n in LADDER}
print("جوابِ دو نامزد در هر چهار اندازه یکی است؟",
      all(by_scan(terms[n], p) == index[n].get(p, []) for n in LADDER for p in asks[n]))
print("نمونه — تعدادِ عبارت با پیشوندِ", asks[80_000][0], ":",
      len(index[80_000][asks[80_000][0]]))
جوابِ دو نامزد در هر چهار اندازه یکی است؟ True
نمونه — تعدادِ عبارت با پیشوندِ eji : 73

برابریِ جواب اول می‌آید، نه آخر — و اینجا از == روی خودِ فهرست استفاده شده، نه فقط روی طولش، چون دو فهرستِ هم‌طول با اعضای متفاوت جوابِ یکسان نیستند.

۳. جدولِ زمانِ پرسش#

🤔 اول حدس بزن: ستونِ نسبتِ هر دو نامزد را بنویس. برای پیمایش راحت است؛ برای index دقت کن — bucketها با n بزرگ‌تر می‌شوند، پس آیا زمانِ پرسش هم بزرگ‌تر می‌شود؟

print("— ۲۰۰ پرسش با پیمایشِ کامل")
table([(n, 1000 * clock(lambda k=n: [by_scan(terms[k], p) for p in asks[k]], repeat=2))
       for n in LADDER], "زمان (ms)", ",.1f")
print("\n— ۲۰۰ پرسش با index")
table([(n, 1000 * clock(lambda k=n: [index[k].get(p, []) for p in asks[k]], repeat=3))
       for n in LADDER], "زمان (ms)", ",.4f")
— ۲۰۰ پرسش با پیمایشِ کامل
         n         زمان (ms)     نسبت به سطر قبل
    10,000              46.2                   —
    20,000              90.9                1.97
    40,000             181.5                2.00
    80,000             400.3                2.21

— ۲۰۰ پرسش با index
         n         زمان (ms)     نسبت به سطر قبل
    10,000            0.0131                   —
    20,000            0.0139                1.06
    40,000            0.0141                1.01
    80,000            0.0136                0.96

2.0 در برابرِ 1.0: O(n) در برابرِ O(1). جوابِ index همان bucketِ آماده را برمی‌گرداند و به بزرگی‌اش کاری ندارد، چون فهرست را نمی‌سازد — همان فهرست را که یک بار ساخته شده، تحویل می‌دهد.

در n = 80,000 این یعنی 400.3 میلی‌ثانیه در برابرِ 0.0136 — روی این ماشین بیش از بیست‌وپنج هزار برابر. و این نسبت با n بزرگ‌تر هم می‌شود، چون ستونِ چپ رشد می‌کند و ستونِ راست نه.

تا اینجا هیچ دلیلی برای انتخابِ پیمایش وجود ندارد. حالا ستونی را اضافه می‌کنیم که در جدولِ زمان نیست.

۴. قیمت، به بایت#

def index_bytes(box):
    """خودِ dict، به‌علاوهٔ bucketهایش. رشته‌ها شمرده نمی‌شوند — چرا، پایین‌تر."""
    return sys.getsizeof(box) + sum(sys.getsizeof(v) for v in box.values())


print(f"{'n':>10}{'بایتِ index':>16}{'نسبت':>10}{'بایتِ هر عبارتِ اضافه':>24}")
last_n = last_b = None
for n in LADDER:
    size = index_bytes(index[n])
    ratio = "—" if last_b is None else f"{size / last_b:.2f}"
    marginal = "—" if last_b is None else f"{(size - last_b) / (n - last_n):.2f}"
    print(f"{n:>10,}{size:>16,}{ratio:>10}{marginal:>24}")
    last_n, last_b = n, size
         n     بایتِ index      نسبت   بایتِ هر عبارتِ اضافه
    10,000         188,784         —                       —
    20,000         270,064      1.43                    8.13
    40,000         440,464      1.63                    8.52
    80,000         779,888      1.77                    8.49

ستونِ نسبت 1.43 است، بعد 1.63، بعد 1.77 — به 2 نزدیک می‌شود ولی هیچ‌وقت نمی‌رسد. دلیلش همان ثابتِ ترمِ ۱ فصلِ ۷ است، این بار روی حافظه: خودِ dict هزار کلید دارد و اندازه‌اش با n عوض نمی‌شود، و هر bucket هم یک سربارِ ثابت دارد. مرتبهٔ حافظه O(n) به‌علاوهٔ یک ثابت است، و در این بازه ثابت هنوز دیده می‌شود.

ستونِ آخر تمیزتر از ستونِ نسبت حرف می‌زند: 8.13، 8.52، 8.49. هر عبارتِ اضافه حدودِ هشت و نیم بایت به index اضافه می‌کند و بس.

🌱 ریشه‌اش کجاست: ستونِ آخر یک نرخ است، و نرخ همیشه یک «به‌ازای هر چه؟» دارد — اینجا «به‌ازای هر عبارتِ اضافه». ساختنِ همین جمله و ثابت کردنِ یک طرفِ کسر برای اینکه دو چیزِ نابرابر قابلِ مقایسه شوند، در ریشه ترمِ ۲ فصل ۸ ساخته می‌شود. بدونِ آن «به‌ازای هر چه؟»، عددِ ۷۷۹٬۸۸۸ فقط بزرگ است — نه گران، نه ارزان.

big = index[80_000]
print("خودِ dict (هزار کلید)      :", f"{sys.getsizeof(big):>10,} بایت")
print("مجموعِ bucketها             :",
      f"{sum(sys.getsizeof(v) for v in big.values()):>10,} بایت")
print("فهرستِ اصلیِ عبارت‌ها        :", f"{sys.getsizeof(terms[80_000]):>10,} بایت")
print("مجموعِ خودِ رشته‌ها          :",
      f"{sum(sys.getsizeof(t) for t in terms[80_000]):>10,} بایت")
خودِ dict (هزار کلید)      :     26,032 بایت
مجموعِ bucketها             :    753,856 بایت
فهرستِ اصلیِ عبارت‌ها        :    711,960 بایت
مجموعِ خودِ رشته‌ها          :  3,920,365 بایت

رشته‌ها در حسابِ index نیامدند و این عمدی است: bucketها همان اشیاء را ارجاع می‌دهند که فهرستِ اصلی دارد، نه کپی‌شان. پس index سه مگابایتِ رشته را دوباره نمی‌خرد؛ فقط هشتاد هزار ارجاعِ تازه می‌سازد — و هشت بایتِ هر ارجاع دقیقاً همان 8.49ِ ستونِ قبل است.

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

۵. نرخِ معامله: «به‌ازای هر چه؟»#

سؤالِ «۷۸۰ کیلوبایت ارزشش را دارد؟» جواب ندارد. سؤالی که جواب دارد این است: به‌ازای چند پرسش؟

n = 80_000
per_scan = clock(lambda: [by_scan(terms[n], p) for p in asks[n]], repeat=2) / 200
per_index = clock(lambda: [index[n].get(p, []) for p in asks[n]], repeat=3) / 200
saved = per_scan - per_index
cost = index_bytes(index[n])
print(f"n = {n:,} · صرفه‌جویی در هر پرسش: {1000 * saved:.3f} ms"
      f" · قیمتِ ثابت: {cost:,} بایت\n")
print(f"{'تعدادِ پرسش (q)':>18}{'کلِ صرفه‌جویی (ms)':>22}{'بایت به‌ازای هر ms':>22}")
for q in (1, 100, 10_000, 1_000_000):
    print(f"{q:>18,}{q * saved * 1000:>22,.1f}{cost / (q * saved * 1000):>22,.2f}")
n = 80,000 · صرفه‌جویی در هر پرسش: 1.811 ms · قیمتِ ثابت: 779,888 بایت

   تعدادِ پرسش (q)    کلِ صرفه‌جویی (ms)    بایت به‌ازای هر ms
                 1                   1.8            430,548.13
               100                 181.1              4,305.48
            10,000              18,113.8                 43.05
         1,000,000           1,811,384.0                  0.43

همان ۷۸۰ کیلوبایت، و نرخ در چهار سطر شش مرتبه عوض می‌شود.

اگر فقط یک پرسش داری، برای هر میلی‌ثانیه صرفه‌جویی چهارصد کیلوبایت پرداخته‌ای — معاملهٔ احمقانه‌ای است. اگر یک میلیون پرسش داری، کمتر از نصفِ یک بایت. q در جدولِ بخشِ ۳ اصلاً نبود، و بدونِ آن هیچ‌کدام از این دو جمله را نمی‌شد نوشت.

📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ دو نامزد برای یک پرسش، روی یک فهرستِ یکسان و همان دویست پیشوندِ ثابت، با جوابِ برابرِ تأییدشده. در کدام بازهٔ n؟ ۱۰٬۰۰۰ تا ۸۰٬۰۰۰ عبارت، با الفبای ده‌حرفی و پیشوندِ سه‌حرفی. با چند تکرار، و کمینه یا میانگین؟ دو تا سه تکرار به‌علاوهٔ گرم‌کننده، کمینه؛ جدولِ حافظه یک اجرا و قطعی.

۶. وقتی دیوار حافظه است#

تا اینجا index برنده بود. حالا پرسش را کمی سخت‌تر می‌کنیم: «چند عبارت هم با این سه حرف شروع می‌شود و هم به آن سه حرف ختم؟»

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

K = len(LETTERS) ** PREFIX


def code_of(part):
    value = 0
    for ch in part:
        value = value * 10 + (ord(ch) - 97)
    return value


def build_cross(items, k=K):
    """برای هر جفتِ (پیشوند، پسوند) یک خانه."""
    grid = [[0] * k for _ in range(k)]
    for term in items:
        grid[code_of(term[:PREFIX])][code_of(term[-PREFIX:])] += 1
    return grid


grid = build_cross(terms[80_000])
grid_bytes = sys.getsizeof(grid) + sum(sys.getsizeof(row) for row in grid)
print(f"جدولِ متقاطع {K}×{K} = {K * K:,} خانه")
print(f"  حافظه            : {grid_bytes:,} بایت")
print(f"  به‌ازای هر خانه   : {grid_bytes / (K * K):.2f} بایت")
for wider in (10_000, 100_000):
    need = grid_bytes / (K * K) * wider * wider
    print(f"  با {wider:>7,} پیشوند: {wider * wider:>15,} خانه ≈ "
          f"{need / 1024 ** 3:>6.1f} گیگابایت")
جدولِ متقاطع 1000×1000 = 1,000,000 خانه
  حافظه            : 8,064,856 بایت
  به‌ازای هر خانه   : 8.06 بایت
  با  10,000 پیشوند:     100,000,000 خانه ≈    0.8 گیگابایت
  با 100,000 پیشوند:  10,000,000,000 خانه ≈   75.1 گیگابایت

هزار پیشوند: هشت مگابایت، ساخته شد. صد هزار پیشوند: هفتاد و پنج گیگابایت، ساخته نمی‌شود.

و دقت کن که هیچ‌کدام از این عددها به n ربطی ندارند. جدولِ متقاطع به تعدادِ پیشوندهای ممکن بند است، نه به تعدادِ عبارت‌ها؛ با هزار عبارت هم همین هشت مگابایت را می‌گیرد. مرتبه‌اش O(K²) است و K جایی در صورتِ مسئله پنهان شده که کسی نگاهش نمی‌کند: طولِ پیشوند. یک حرف بیشتر یعنی K ده برابر و حافظه صد برابر.

پس اینجا زمان اصلاً موضوع نیست. برای این پرسشِ تازه دو نامزد داشتیم: جدولِ متقاطعِ کامل، و پیمایشِ کامل. اولی سریع‌ترین جوابِ ممکن را می‌دهد و در Kهای بزرگ اصلاً ساخته نمی‌شود — نه چون کند است، چون در حافظه جا نمی‌شود. دومی — همان نامزدی که در بخشِ ۳ بیست‌وپنج هزار برابر عقب بود — به K هیچ کاری ندارد، چون هیچ چیزی نگه نمی‌دارد. و نامزدی که وجود نداشته باشد، سرعتش موضوعیت ندارد.

⚠️ مواظب باش: در Colab وقتی از سقفِ حافظه رد می‌شوی معمولاً MemoryError نمی‌گیری؛ نشست بدونِ هیچ پیامی ری‌استارت می‌شود و همهٔ متغیرهایت می‌روند. پس قبل از ساختنِ هر ساختارِ بزرگی، مثلِ همین بخش، اول با یک ضرب و تقسیم حجمش را حساب کن. عددی که با کاغذ حساب شده، جای نشستی را که از دست می‌رود نمی‌گیرد — ولی جلوی از دست رفتنش را می‌گیرد.

✅ چک کن: خطِ PREFIX = 2 را بالای همین سلولِ آخر بگذار و دوباره اجرایش کن. K باید صد شود و حافظهٔ جدولِ متقاطع حدودِ صد برابر کمتر. اگر فقط ده برابر کم شد، K را جایی به‌صورتِ عددِ ثابت نوشته‌ای، نه از روی PREFIX.

🔧 اگر کار نکرد: index برای پیشوندی که هیچ عبارتی ندارد کلید ندارد، و این تفاوتِ [] با خطا دادن است:

try:
    index[10_000]["zzz"]
except KeyError as err:
    print(f"{type(err).__name__}: {err}")
print("با get:", index[10_000].get("zzz", []))
KeyError: 'zzz'
با get: []

پیمایشِ کامل چنین مشکلی ندارد — فهرستِ خالی برمی‌گرداند و تمام. این هم بخشی از قیمتِ index است و در هیچ جدولی دیده نمی‌شود: هر ساختارِ پیش‌ساخته یک حالتِ «نداریم» دارد که باید صریح مدیریتش کنی، وگرنه یک پرسشِ بی‌جواب برنامه را می‌شکند.

🤖 از دستیارت بپرس: «چه وقت پیش‌محاسبه ارزشش را ندارد؟» بعد جدولِ بخشِ ۵ را جلویش بگذار و بپرس: «این نرخ به‌ازای هر چه است؟» — جوابِ درست باید q را نام ببرد. اگر بدونِ پرسیدنِ تعدادِ پرسش گفت «ایندکس بساز»، جدولِ بخشِ ۶ را هم نشانش بده.

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

کلمه تلفظ به حروف فارسی یعنی چه
space-time trade-off اسپیس-تایم تِرِیداف خریدنِ زمانِ کمتر با حافظهٔ بیشتر، یا برعکس
precomputation پری‌کامپیوتیشن حساب کردنِ جواب پیش از پرسیده شدنش
marginal cost مارجینال کاست هزینه‌ای که یک عضوِ اضافه می‌آورد، نه کلِ هزینه

تمرین‌ها

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

در فصل بعد#

سه فصل ابزارِ انتخاب ساختیم و هر سه یک چیز را فرض گرفته‌اند: که بهینه‌سازی خوب است و بیشترش بهتر.

فصلِ بعد این فرض را می‌شکند و سه معیار می‌سازد که هر کدام به‌تنهایی می‌گویند «بس است» — یکی‌شان همان چیزی است که ترمِ ۱ فصلِ ۳ ساخت و از همان‌جا وعده‌اش داده شده بود. و بدترین حالتش را هم نشان می‌دهد: نسخه‌ای که سریع‌تر است، هیچ خطایی نمی‌دهد، و جوابِ غلط برمی‌گرداند.

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

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