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

فصل ۳ از ۷

پیشرفت ترم
۰٪

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

تابعِ hash را داریم و می‌دانیم برخورد اجتناب‌ناپذیر است. این فصل از این دو، یک ساختارِ کامل می‌سازد — در حدودِ سی خط، بدونِ هیچ کتابخانه‌ای — و بعد دو بار اندازه‌اش می‌گیرد.

بارِ اول جدول ثابت می‌ماند: میانگینِ گام‌های جست‌وجو از 6.03 به 40.56 می‌رود و ستونِ نسبت 1.95 می‌شود. بارِ دوم همان کلیدها در جدولی می‌ریزند که وقتی شلوغ شد خودش را بزرگ می‌کند: 1.33، 1.28، 1.31، 1.32 — ستونِ نسبت 1.01. فرقِ این دو جدول، کلِ حرفِ این ترم است.

قفسه‌ای از خانه‌های شماره‌دار که از هر خانه یک زنجیرِ کوتاه از برگه‌ها آویزان است

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

  • یک hash table با bucket و chaining را از صفر بنویسی
  • load factor را حساب کنی و بگویی چرا جدولِ پر کند می‌شود
  • بگویی rehash چقدر خرج دارد و چرا با وجودِ آن، درج هنوز ارزان است

قبل از شروع#

از فصلِ ۲: poly_hash، برخورد، و قاعدهٔ «اندازهٔ جدول را عددِ اول بگیر».

از ترمِ ۲ فصلِ ۳: هزینهٔ amortised و دوبرابرشدنِ ظرفیت. این فصل دقیقاً همان الگو را روی یک ساختارِ دیگر تکرار می‌کند.

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

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

۱. کوچک‌ترین نسخهٔ ممکن، با دست#

پنج خانه می‌گیریم و شش کلید. هر خانه یک bucket است: یک list که هر جفتِ کلید-مقدارِ متعلق به آن خانه را نگه می‌دارد. وقتی دو کلید هم‌خانه شوند، هر دو در همان bucket کنارِ هم می‌نشینند — اسمِ این کار chaining است.

def poly_hash(key):
    """همان تابعِ فصلِ قبل: هر حرف در ۳۱ ضرب و با حرفِ بعدی جمع می‌شود."""
    h = 0
    for ch in str(key):
        h = (h * 31 + ord(ch)) % 1_000_003
    return h


def table_new(size):
    """به‌اندازهٔ size خانه، و هر خانه یک bucketِ خالیِ جداگانه."""
    return [[] for _ in range(size)]


def table_put(buckets, key, value):
    """کلید را در bucketِ خودش می‌گذارد؛ اگر از قبل بود، مقدارش را عوض می‌کند."""
    bucket = buckets[poly_hash(key) % len(buckets)]
    for pair in bucket:
        if pair[0] == key:
            pair[1] = value
            return
    bucket.append([key, value])


def table_get(buckets, key):
    """مقدار، و تعدادِ جفتی که تا رسیدن به آن نگاه شد."""
    bucket = buckets[poly_hash(key) % len(buckets)]
    steps = 0
    for pair in bucket:
        steps += 1
        if pair[0] == key:
            return pair[1], steps
    return None, steps


small = table_new(5)
for name, city in (("sara", "shiraz"), ("reza", "tabriz"), ("nima", "rasht"),
                   ("mina", "yazd"), ("kian", "ahvaz"), ("dara", "kerman")):
    table_put(small, name, city)
for i, bucket in enumerate(small):
    print(f"bucket {i}: {bucket}")
print("جست‌وجوی nima:", table_get(small, "nima"))
print("جست‌وجوی sina:", table_get(small, "sina"))
bucket 0: [['reza', 'tabriz'], ['kian', 'ahvaz']]
bucket 1: []
bucket 2: [['nima', 'rasht'], ['mina', 'yazd']]
bucket 3: []
bucket 4: [['sara', 'shiraz'], ['dara', 'kerman']]
جست‌وجوی nima: ('rasht', 1)
جست‌وجوی sina: (None, 0)

کلِ ساختار همین است و دیگر هیچ چیز. شش کلید در سه bucket نشسته‌اند و دو bucket خالی مانده. جست‌وجوی nima یک گام خورد: poly_hash گفت خانهٔ ۲، و اولین جفتِ آن خانه همان بود.

و به سطرِ آخر خوب نگاه کن: جست‌وجوی کلیدی که اصلاً وجود ندارد صفر گام خورد. sina به یک bucket خالی افتاد، و «خالی» یعنی جوابِ «نه» بدونِ حتی یک مقایسه. این دقیقاً همان پرسشی است که در فصلِ ۱ هزار مقایسه خرج برمی‌داشت.

🔧 اگر کار نکرد: خطِ table_new وسوسه‌انگیزترین جای این کد برای کوتاه‌نویسی است، و کوتاه‌نویسی‌اش هیچ خطایی نمی‌دهد و ساختار را کاملاً خراب می‌کند:

broken = [[]] * 4                        # چهار ارجاع به یک list واحد
table_put(broken, "sara", "shiraz")
print("bucketهای معیوب:", broken)
print("طولِ هر bucket :", [len(b) for b in broken])

healthy = table_new(4)
table_put(healthy, "sara", "shiraz")
print("bucketهای درست:", healthy)
bucketهای معیوب: [[['sara', 'shiraz']], [['sara', 'shiraz']], [['sara', 'shiraz']], [['sara', 'shiraz']]]
طولِ هر bucket : [1, 1, 1, 1]
bucketهای درست: [[['sara', 'shiraz']], [], [], []]

یک درج، و هر چهار bucket پر شدند. [[]] * 4 چهار list نمی‌سازد؛ چهار ارجاع به یک list واحد می‌سازد. هیچ استثنایی بلند نمی‌شود، هیچ پیامی چاپ نمی‌شود، و جدولت از همان اولین درج غلط است. [[] for _ in range(size)] هر بار یک list تازه می‌سازد.

این بدترین ردهٔ خطاست: کدی که کار می‌کند و جوابِ غلط می‌دهد. تنها راهِ گرفتنش هم همان کاری است که این‌جا کردیم — ساختار را چاپ کردن و با چشم دیدن.

۲. load factor: نسبتی که همه‌چیز را تعیین می‌کند#

اندازهٔ جدول را ثابت می‌گذاریم روی ۱۰۱ خانه و تعدادِ کلیدها را بالا می‌بریم. نسبتِ تعدادِ کلید به تعدادِ خانه اسم دارد: load factor.

🌱 ریشه‌اش کجاست: load factor یک نسبت است، نه یک شمارش — «به‌ازای هر خانه، چند کلید». همین ایده در ریشه ترمِ ۲ فصل ۷ با نسبت و تناسب ساخته می‌شود. و خاصیتِ مهمش همان خاصیتِ هر نسبتی است: به اندازهٔ جدول و تعدادِ کلیدها جداگانه بند نیست، فقط به رابطهٔ آن دو بند است. جدولی با ۱۰۱ خانه و ۲۰۰ کلید، دقیقاً همان‌قدر شلوغ است که جدولی با ۱٬۰۱۰ خانه و ۲٬۰۰۰ کلید.

rng = random.Random(SEED)
POOL = [f"user-{rng.randrange(10 ** 9)}" for _ in range(8_000)]
print("کلیدهای یکتا:", len(set(POOL)), "· سه نمونه:", POOL[:3])


def build_fixed(keys, size):
    """جدولی با اندازهٔ ثابت — هرگز بزرگ نمی‌شود."""
    buckets = table_new(size)
    for k in keys:
        table_put(buckets, k, 1)
    return buckets


def lookup_cost(buckets, keys):
    """میانگین و بیشینهٔ گام‌های جست‌وجو برای همهٔ کلیدها."""
    total = 0
    worst = 0
    for k in keys:
        steps = table_get(buckets, k)[1]
        total += steps
        worst = max(worst, steps)
    return total / len(keys), worst


FIXED = 101
LADDER = [1_000, 2_000, 4_000, 8_000]
for n in LADDER:
    average, worst = lookup_cost(build_fixed(POOL[:n], FIXED), POOL[:n])
    print(f"n={n:>6,}  load factor={n / FIXED:>6.2f}"
          f"  میانگینِ گام={average:>6.2f}  بلندترین زنجیر={worst:>4}")
کلیدهای یکتا: 8000 · سه نمونه: ['user-835549143', 'user-473233031', 'user-125467289']
n= 1,000  load factor=  9.90  میانگینِ گام=  6.03  بلندترین زنجیر=  20
n= 2,000  load factor= 19.80  میانگینِ گام= 10.88  بلندترین زنجیر=  30
n= 4,000  load factor= 39.60  میانگینِ گام= 20.85  بلندترین زنجیر=  53
n= 8,000  load factor= 79.21  میانگینِ گام= 40.56  بلندترین زنجیر=  98

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

یعنی جدولِ پر، هیچ جادویی ندارد: هر bucket خودش یک فهرستِ کوچک است و جست‌وجو در آن، همان جست‌وجوی خطیِ فصلِ ۱. جدول فقط کار را به size تکه شکسته.

🤔 اول حدس بزن: با ثابت ماندنِ اندازهٔ جدول، اگر تعدادِ کلیدها دو برابر شود میانگینِ گام چند برابر می‌شود؟ بنویسش، بعد جدول را ببین.

table([(n, lookup_cost(build_fixed(POOL[:n], FIXED), POOL[:n])[0]) for n in LADDER],
      "میانگینِ گام", ",.2f")
         n      میانگینِ گام     نسبت به سطر قبل
     1,000              6.03                   —
     2,000             10.88                1.80
     4,000             20.85                1.92
     8,000             40.56                1.95

نزدیکِ 2 و رو به بالا رفتن به سمتِ 2. یعنی O(n) — همان مرتبه‌ای که با جست‌وجوی خطیِ ساده هم داشتیم.

عددِ ۱۰۱ فقط یک ثابت است، و ثابت مرتبه را عوض نمی‌کند. جدولی که بزرگ نمی‌شود، hash table نیست؛ صد و یک فهرستِ کوچک است.

(ستونِ نسبت از 1.80 شروع می‌شود نه از 2.00، چون در سطرهای اول آن «یک گامِ اولِ» هر جست‌وجو هنوز سهمِ محسوسی از کل دارد. هرچه زنجیرها بلندتر می‌شوند، سهمش کمتر و نسبت به 2 نزدیک‌تر می‌شود.)

۳. جدولی که خودش را بزرگ می‌کند#

راهِ حل روشن است: نگذاریم load factor بالا برود. هر وقت از حدی گذشت، جدولِ بزرگ‌تری می‌سازیم و همه‌چیز را دوباره جا می‌دهیم — چون خانهٔ هر کلید به len(buckets) بند است و با عوض شدنِ اندازه، عوض می‌شود. اسمِ این کار rehash است.

اندازه‌ها را از یک فهرستِ آمادهٔ عددِ اول برمی‌داریم که هر کدام تقریباً دو برابرِ قبلی است — یکی به‌خاطرِ قاعدهٔ فصلِ ۲، و یکی به‌خاطرِ ترمِ ۲ فصلِ ۳: رشدِ ضربی، نه جمعی.

GROW_AT = 0.75
TABLE_SIZES = (11, 23, 47, 97, 199, 401, 809, 1_619, 3_251, 6_521, 13_043, 26_099)
BUCKETS, COUNT, STEP, MOVES = 0, 1, 2, 3


def grow_new():
    """[bucketها، تعدادِ کلید، شمارهٔ اندازهٔ فعلی، تعدادِ جابه‌جایی]"""
    return [table_new(TABLE_SIZES[0]), 0, 0, 0]


def rehash(t):
    """اندازهٔ بعدی را می‌سازد و هر جفت را در خانهٔ تازه‌اش می‌گذارد."""
    t[STEP] += 1
    bigger = table_new(TABLE_SIZES[t[STEP]])
    for bucket in t[BUCKETS]:
        for pair in bucket:
            bigger[poly_hash(pair[0]) % len(bigger)].append(pair)
            t[MOVES] += 1
    t[BUCKETS] = bigger


def grow_put(t, key, value):
    """درج، و بزرگ کردنِ جدول به‌محضِ اینکه load factor از GROW_AT رد شود."""
    bucket = t[BUCKETS][poly_hash(key) % len(t[BUCKETS])]
    for pair in bucket:
        if pair[0] == key:
            pair[1] = value
            return
    bucket.append([key, value])
    t[COUNT] += 1
    if t[COUNT] > GROW_AT * len(t[BUCKETS]) and t[STEP] + 1 < len(TABLE_SIZES):
        rehash(t)


def build_growing(keys):
    t = grow_new()
    for k in keys:
        grow_put(t, k, 1)
    return t


for n in LADDER:
    t = build_growing(POOL[:n])
    average, worst = lookup_cost(t[BUCKETS], POOL[:n])
    print(f"n={n:>6,}  اندازهٔ جدول={len(t[BUCKETS]):>6,}"
          f"  load factor={n / len(t[BUCKETS]):>5.2f}"
          f"  میانگینِ گام={average:>5.2f}  بلندترین زنجیر={worst:>3}")
n= 1,000  اندازهٔ جدول= 1,619  load factor= 0.62  میانگینِ گام= 1.33  بلندترین زنجیر=  5
n= 2,000  اندازهٔ جدول= 3,251  load factor= 0.62  میانگینِ گام= 1.28  بلندترین زنجیر=  4
n= 4,000  اندازهٔ جدول= 6,521  load factor= 0.61  میانگینِ گام= 1.31  بلندترین زنجیر=  5
n= 8,000  اندازهٔ جدول=13,043  load factor= 0.61  میانگینِ گام= 1.32  بلندترین زنجیر=  6

load factor در هر چهار سطر حولِ 0.62 ثابت مانده، و به‌همراهش میانگینِ گام هم. بلندترین زنجیر با هشت برابر شدنِ کلیدها از ۵ به ۶ رفت — یعنی تقریباً هیچ.

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

table([(n, lookup_cost(build_growing(POOL[:n])[BUCKETS], POOL[:n])[0]) for n in LADDER],
      "میانگینِ گام", ",.2f")
         n      میانگینِ گام     نسبت به سطر قبل
     1,000              1.33                   —
     2,000              1.28                0.97
     4,000              1.31                1.02
     8,000              1.32                1.01

0.97، 1.02، 1.01. نزدیکِ یک، یعنی O(1): هزینهٔ یک جست‌وجو به تعدادِ کلیدهای داخلِ جدول بستگی ندارد.

این همان عنوانِ ترم است و حالا با عدد پشتیبانی می‌شود. و مقایسه‌اش با جدولِ بخشِ ۲ را در یک سطر بنویس: در n = 8,000 جدولِ ثابت 40.56 گام می‌خواست و جدولِ بزرگ‌شونده 1.32 — بیش از سی برابر کمتر، با همان کلیدها و همان تابعِ hash.

۴. rehash رایگان نیست#

هر بار که جدول بزرگ می‌شود، همهٔ جفت‌ها جابه‌جا می‌شوند. شمرده‌ایمشان.

table([(n, build_growing(POOL[:n])[MOVES]) for n in LADDER], "جابه‌جایی", ",d")
         n         جابه‌جایی     نسبت به سطر قبل
     1,000             1,194                   —
     2,000             2,409                2.02
     4,000             4,848                2.01
     8,000             9,739                2.01

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

دلیلش دقیقاً همان چیزی است که ترمِ ۲ فصلِ ۳ دربارهٔ list نشان داد: چون هر اندازه دو برابرِ قبلی است، جابه‌جایی‌های گذشته روی هم از یک برابرِ اندازهٔ فعلی بیشتر نمی‌شوند. یک درجِ تک ممکن است خیلی گران باشد — همان درجی که rehash را راه می‌اندازد — ولی میانگینِ بلندمدت ثابت می‌ماند. این همان amortised است.

table([(n, 1000 * clock(lambda keys=POOL[:n]: build_growing(keys), repeat=3))
       for n in LADDER], "زمانِ ساخت (ms)", ",.1f")
         n   زمانِ ساخت (ms)     نسبت به سطر قبل
     1,000               3.5                   —
     2,000               7.4                2.12
     4,000              14.5                1.95
     8,000              28.2                1.94

ساعت هم می‌گوید ساختنِ جدول خطی است. یعنی n درج، هر کدام با هزینهٔ ثابتِ amortised.

📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ یک hash table با اندازهٔ ثابت، در برابرِ همان ساختار با سیاستِ بزرگ‌شدن — با کلیدهای کاملاً یکسان و همان تابعِ hash. در کدام بازهٔ n؟ ۱٬۰۰۰ تا ۸٬۰۰۰ کلید؛ جدولِ ثابت ۱۰۱ خانه و جدولِ بزرگ‌شونده از ۱۱ خانه شروع می‌کند و در سقفِ GROW_AT = 0.75 می‌ماند. با چند تکرار، و کمینه یا میانگین؟ جدول‌های گام و جابه‌جایی یک اجرا، چون شمارش‌اند و قطعی؛ جدولِ زمان سه تکرار به‌علاوهٔ گرم‌کننده، کمینه.

✅ چک کن: GROW_AT را از 0.75 به 4.0 ببر و فقط جدولِ بخشِ ۳ را دوباره بگیر. میانگینِ گام باید از حدودِ 1.3 به حدودِ 2.2 برود و ستونِ نسبت باید هنوز نزدیکِ 1 بماند — چون جدول همچنان بزرگ می‌شود، فقط دیرتر. اگر ستونِ نسبت به 2 رفت، احتمالاً به‌جای GROW_AT شرطِ t[STEP] + 1 < len(TABLE_SIZES) را دست زده‌ای و جدول از یک جایی به بعد اصلاً بزرگ نمی‌شود.

🤖 از دستیارت بپرس: «در یک hash table با chaining، چرا load factor مهم‌تر از تعدادِ کلیدهاست؟» بعد این را هم بپرس: «اگر به‌جای دو برابر کردنِ اندازه، هر بار صد خانه اضافه کنم، کلِ کارِ rehashها چه شکلی رشد می‌کند؟» — جوابِ درست O(n²) است و باید بتواند بگوید چرا؛ اگر دستیارت گفت «فرقی نمی‌کند»، جدولِ بخشِ ۴ را با همان تغییر بگیر و جلویش بگذار.

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

کلمه تلفظ به حروف فارسی یعنی چه
hash table هَش تیبل ساختاری که جای هر کلید را از hashش حساب می‌کند
bucket باکِت یک خانهٔ جدول، که هر تعداد جفت می‌تواند داشته باشد
chaining چینینگ نگه داشتنِ کلیدهای هم‌خانه در یک فهرستِ کوچک، کنارِ هم
load factor لود فَکتور نسبتِ تعدادِ کلیدها به تعدادِ خانه‌ها
rehash ری‌هَش ساختنِ جدولِ بزرگ‌تر و جا دادنِ دوبارهٔ همهٔ کلیدها

تمرین‌ها

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

در فصل بعد#

جدولِ بخشِ ۳ می‌گوید میانگینِ گام 1.32 است. فصلِ بعد همان ساختار را با کلیدهایی پر می‌کند که کسی عمداً برایش ساخته و همان عدد به 256.50 می‌رسد.

آن‌جا سه پرسشِ متفاوت را از هم جدا می‌کنیم — بدترین حالت، حالتِ متوسط، و حالتی که واقعاً داری — و می‌بینیم چرا گزارش کردنِ فقط یکی از این سه، گمراه‌کننده است. و یک جدول هم می‌آید که میانگینش 4.17 است و بدترین گامش 53؛ همان جدولی که اگر فقط میانگینش را گزارش کنی، هیچ چیزِ مهمی نگفته‌ای.

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

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