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

فصل ۶ از ۷

پیشرفت ترم
۰٪

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

تا حالا هر کلیدی که به set و dict داده‌ایم رشته یا عدد بوده. این فصل می‌پرسد چه چیزی اصلاً می‌تواند کلید باشد، و از یک خطای واقعی شروع می‌کند: TypeError: unhashable type: 'list'.

بعد قاعده‌ای را می‌بینی که پشتِ آن خطاست، و یک dict که سه بار درج می‌شود و آخرش یک عضو دارد. آخرِ فصل هم، با همان hash table دست‌سازِ فصلِ ۳، کلیدی را که بعد از درج عوض شده گم می‌کنیم — در حالی که خودش هنوز همان‌جا داخلِ bucket نشسته و کاملاً دیده می‌شود.

کلیدی که بعد از ساخته شدنِ قفل، دندانه‌هایش تغییر کرده و دیگر در همان قفل نمی‌چرخد

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

  • بگویی hashable بودن یعنی چه و چرا list نیست
  • قاعدهٔ هم‌خوانیِ __hash__ و __eq__ را با یک مثالِ اجراشدنی توضیح بدهی
  • کلیدِ مرکب بسازی و هزینه‌اش را اندازه بگیری

قبل از شروع#

از فصلِ ۲: hash به‌عنوان تابعی که کلید را به عدد تبدیل می‌کند، و اینکه hash(1) و hash(1.0) و hash(True) یکی‌اند.

از فصلِ ۳: poly_hash، bucket و chaining. کدِ همان جدول این‌جا دوباره می‌آید.

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

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

۱. خطایی که همه یک بار می‌گیرند#

seen = set()
seen.add("user-1")
seen.add(("user", 1))
print("تا اینجا مشکلی نیست:", len(seen))
try:
    seen.add(["user", 1])
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
تا اینجا مشکلی نیست: 2
TypeError: unhashable type: 'list'

🔧 اگر کار نکرد: پیام دقیقاً می‌گوید چه چیزی کم است: list قابلِ hash گرفتن نیست. راهِ حل تقریباً همیشه یک نویسه است — [ را به ( عوض کن و همان محتوا در یک tuple می‌نشیند که hashable است. اگر محتوا باید تغییرپذیر بماند، آن‌وقت اصلاً نباید کلید باشد؛ باید مقدار باشد.

و همین‌جا سؤالِ اصلیِ فصل درمی‌آید: چرا tuple می‌تواند و list نمی‌تواند؟

۲. hashable یعنی چه#

فصلِ ۳ نشان داد جای هر کلید از hashش می‌آید. پس اگر hash یک کلید بعد از درج عوض شود، آن کلید در خانهٔ اشتباهی نشسته و دیگر پیدا نمی‌شود.

از این یک شرط درمی‌آید: چیزی می‌تواند کلید باشد که hashش در تمامِ عمرش ثابت بماند. پایتون این را با یک قاعدهٔ ساده‌تر تضمین می‌کند: چیزهایی که می‌شود تغییرشان داد، hashable نیستند. list تغییرپذیر است، tuple نیست. set تغییرپذیر است، رشته و عدد نیستند.

print("hash یک tuple:", hash(("a", 1)) == hash(("a", 1)))
try:
    hash(("a", [1]))
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
hash یک tuple: True
TypeError: unhashable type: 'list'

سطرِ دوم مهم‌تر از سطرِ اول است. tuple خودش تغییرپذیر نیست، ولی می‌تواند چیزِ تغییرپذیری داخلش داشته باشد — و آن‌وقت خودش هم hashable نیست. hash یک tuple از hash عضوهایش ساخته می‌شود، پس عضوی که hash ندارد کلِ tuple را از کار می‌اندازد.

۳. قاعدهٔ هم‌خوانی: اگر برابرند، hashشان هم باید یکی باشد#

پایتون دو کارِ جداگانه با یک کلید می‌کند: اول از hash جای bucket را پیدا می‌کند (پشتِ صحنه __hash__ صدا زده می‌شود)، بعد داخلِ آن bucket با == دنبالِ کلید می‌گردد (که __eq__ است). این دو باید با هم بخوانند، وگرنه ساختار می‌شکند:

اگر a == b باشد، حتماً باید hash(a) == hash(b) باشد.

خلافش لازم نیست: دو چیز می‌توانند hash یکسان داشته باشند و برابر نباشند — که همان برخوردِ فصلِ ۲ است و chaining تکلیفش را روشن می‌کند.

پایتون خودش این قاعده را رعایت می‌کند، و یک نتیجهٔ عجیب دارد:

print("1 == 1.0 == True ?", 1 == 1.0 == True)
print("hash(1), hash(1.0), hash(True):", hash(1), hash(1.0), hash(True))

box = {}
box[1] = "اولی"
box[1.0] = "دومی"
box[True] = "سومی"
print("dict بعد از سه درج:", box)
print("طولش:", len(box))
1 == 1.0 == True ? True
hash(1), hash(1.0), hash(True): 1 1 1
dict بعد از سه درج: {1: 'سومی'}
طولش: 1

سه درج، یک عضو. 1 و 1.0 و True در پایتون با هم برابرند، پس از نظرِ dict یک کلیدند — هر سه به یک bucket می‌روند و == می‌گوید همان‌اند، پس فقط مقدار جایگزین می‌شود.

و کلیدِ باقی‌مانده 1 است، نه True: کلید از اولین درج می‌ماند و فقط مقدار به‌روز می‌شود. این دقیقاً همان کاری است که table_put ما در فصلِ ۳ می‌کرد — آن‌جا هم وقتی کلید پیدا می‌شد، pair[1] عوض می‌شد و pair[0] دست‌نخورده می‌ماند.

۴. کلیدِ مرکب#

قاعدهٔ «تغییرناپذیر باشد» یک نتیجهٔ عملیِ مفید دارد: tuple کلیدِ مرکب می‌سازد. هر جا کلیدت یک چیز نیست و چند چیز است، به‌جای چسباندنشان به هم در یک رشته، tupleشان کن.

grid = {}
grid[(0, 0)] = "خانهٔ شروع"
grid[(1, 2)] = "خانهٔ گنج"
grid[(2, 1)] = "خانهٔ تله"
print(grid)
print("کلیدِ (1, 2):", grid[(1, 2)], "· کلیدِ (2, 1):", grid[(2, 1)])
{(0, 0): 'خانهٔ شروع', (1, 2): 'خانهٔ گنج', (2, 1): 'خانهٔ تله'}
کلیدِ (1, 2): خانهٔ گنج · کلیدِ (2, 1): خانهٔ تله

(1, 2) و (2, 1) دو کلیدِ کاملاً متفاوت‌اند — همان چیزی که با چسباندن به رشته به‌راحتی از دست می‌رفت. و ترتیبِ چاپ همان ترتیبِ درج است، چون dict ترتیبِ درج را نگه می‌دارد.

۵. کلیدی که بعد از درج عوض شود#

حالا نشان می‌دهیم اگر پایتون این قید را نمی‌گذاشت، چه اتفاقی می‌افتاد. hash table دست‌سازِ فصلِ ۳ چنین قیدی ندارد: poly_hash روی str(key) کار می‌کند و str یک list هم به‌راحتی ساخته می‌شود. پس می‌شود یک list را در آن کلید کرد — و بعد عوضش کرد.

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


def table_new(size):
    return [[] for _ in range(size)]


def table_put(buckets, key, value):
    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


buckets = table_new(7)
key = [1, 2]
table_put(buckets, key, "گنج")
print("قبل از تغییر  :", table_get(buckets, [1, 2]))
key.append(3)                                  # همان list، حالا یک عضو بیشتر
print("دنبالِ [1, 2]  :", table_get(buckets, [1, 2]))
print("دنبالِ [1, 2, 3]:", table_get(buckets, [1, 2, 3]))
print("ولی هنوز اینجاست:", [b for b in buckets if b])
قبل از تغییر  : ('گنج', 1)
دنبالِ [1, 2]  : (None, 1)
دنبالِ [1, 2, 3]: (None, 0)
ولی هنوز اینجاست: [[[[1, 2, 3], 'گنج']]]

سه سطرِ آخر را با هم بخوان؛ هر کدام نصفِ داستان‌اند.

  • [1, 2] پیدا نمی‌شود: hash همان است، پس به bucket درست می‌رویم و یک گام هم برمی‌داریم — ولی جفتی که آن‌جاست دیگر با [1, 2] برابر نیست.
  • [1, 2, 3] هم پیدا نمی‌شود: این بار hash عوض شده، پس اصلاً به bucket اشتباهی می‌رویم که خالی است — صفر گام.
  • و مقدار هنوز سرِ جایش است. هیچ چیزی گم نشده و هیچ خطایی هم بلند نشده؛ فقط دیگر هیچ راهی به آن نیست.

این بدترین حالتی است که یک ساختارِ داده می‌تواند به تو بدهد: نه خطا، نه پیام، فقط دادهٔ غیرقابلِ دسترسی. و دقیقاً برای جلوگیری از همین است که پایتون list را از کلید بودن محروم می‌کند — قید، محدودیت نیست؛ ضمانت است.

۶. هزینهٔ کلیدِ مرکب#

کلیدِ tuple رایگان نیست: hash گرفتن از آن یعنی hash گرفتن از هر عضوش.

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

def poly_hash_counted(key):
    """همان poly_hash، با شمارندهٔ گام."""
    h = 0
    ops = 0
    for ch in str(key):
        h = (h * 31 + ord(ch)) % 1_000_003
        ops += 1
    return h, ops


table([(length, poly_hash_counted(("ab",) * length)[1])
       for length in (250, 500, 1_000, 2_000)], "گامِ hash", ",d")
         n         گامِ hash     نسبت به سطر قبل
       250             1,500                   —
       500             3,000                2.00
     1,000             6,000                2.00
     2,000            12,000                2.00

2.00. n این‌جا تعدادِ عضوهای tuple است، نه تعدادِ کلیدها. پس هزینهٔ hash با اندازهٔ کلید خطی است — همان نتیجهٔ فصلِ ۲، این بار برای کلیدِ مرکب.

نتیجهٔ عملی: کلیدِ کوچک نگه دار. یک tuple دوتایی عملاً رایگان است؛ یک tuple هزارتایی به‌ازای هر lookup هزار گام خرج می‌کند و آن‌وقت دیگر «هزینهٔ ثابت» حرفِ بی‌معنایی است.

و حالا سؤالِ دیگر: با ثابت ماندنِ اندازهٔ کلید، آیا lookup با کلیدِ tuple هنوز به تعدادِ کلیدها بی‌اعتناست؟

rng = random.Random(SEED)
LADDER = [25_000, 50_000, 100_000, 200_000]
base = [(rng.randrange(10 ** 6), rng.randrange(10 ** 6)) for _ in range(200_000)]
maps = {n: {k: 1 for k in base[:n]} for n in LADDER}
asks = [base[rng.randrange(25_000)] if i % 2 == 0
        else (rng.randrange(10 ** 6), rng.randrange(10 ** 6)) for i in range(100_000)]


def hits_in(container, qs):
    hits = 0
    for q in qs:
        if q in container:
            hits += 1
    return hits


print("تعدادِ «بله» در همهٔ اندازه‌ها یکی است؟",
      len({hits_in(maps[n], asks) for n in LADDER}) == 1)
table([(n, 1000 * clock(lambda c=maps[n]: hits_in(c, asks), repeat=3))
       for n in LADDER], "زمان (ms)", ",.1f")
تعدادِ «بله» در همهٔ اندازه‌ها یکی است؟ True
         n         زمان (ms)     نسبت به سطر قبل
    25,000               6.7                   —
    50,000               6.9                1.03
   100,000               8.9                1.29
   200,000              10.8                1.22

نزدیکِ 1، با یک بالا رفتنِ ملایم. صد هزار پرسش، و هشت برابر شدنِ dict زمان را کمتر از دو برابر کرد — نه هشت برابر. آن بالا رفتنِ ملایم Big-O نیست؛ همان اثرِ حافظه است که فصلِ قبل هم دیدیمش.

📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ یک dict با کلیدِ tuple، در چهار اندازه، با پرسش‌های کاملاً یکسان و جوابِ تأییدشدهٔ برابر. در کدام بازهٔ n؟ ۲۵٬۰۰۰ تا ۲۰۰٬۰۰۰ کلید با صد هزار پرسشِ ثابت برای زمان، و طولِ کلیدِ ۲۵۰ تا ۲٬۰۰۰ برای هزینهٔ hash. با چند تکرار، و کمینه یا میانگین؟ جدولِ گام یک اجرا چون شمارش قطعی است؛ جدولِ زمان سه تکرار به‌علاوهٔ گرم‌کننده، کمینه.

✅ چک کن: در بخشِ ۵، خطِ key.append(3) را به key = [1, 2, 3] تغییر بده. حالا سطرِ «دنبالِ [1, 2]» جواب می‌دهد و سطرِ آخر هم [1, 2] را نشان می‌دهد؛ فقط سطرِ «دنبالِ [1, 2, 3]» همان (None, 0) می‌ماند. دلیلش این است که این خط list را عوض نمی‌کند، فقط نامِ key را به یک list تازه وصل می‌کند — و آنی که داخلِ جدول نشسته دست‌نخورده می‌ماند. همین تفاوت، تفاوتِ «تغییر دادن» و «جایگزین کردن» است.

🤖 از دستیارت بپرس: «چرا tuple می‌تواند کلیدِ dict باشد ولی list نه؟» بعد این را هم بپرس: «اگر tupleام یک list داخلش داشته باشد چه؟» — جوابِ درست باید بگوید hash یک tuple از عضوهایش ساخته می‌شود؛ اگر دستیارت گفت «tuple همیشه hashable است»، خروجیِ بخشِ ۲ را جلویش بگذار.

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

کلمه تلفظ به حروف فارسی یعنی چه
hashable هَشِبل چیزی که hash دارد و hashش هرگز عوض نمی‌شود
immutable ایمیوتِبل تغییرناپذیر؛ بعد از ساخته شدن عوض نمی‌شود
__hash__ دانِدر هَش کاری که پایتون برای گرفتنِ hash یک چیز صدا می‌زند
__eq__ دانِدر ایکیو کاری که پایتون برای مقایسهٔ دو چیز با == صدا می‌زند
composite key کامپوزیت کی کلیدی که از چند بخش ساخته شده، معمولاً یک tuple

تمرین‌ها

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

در فصل بعد#

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

دو روشِ اول هر دو O(n²) هستند و ستونِ نسبتشان نزدیکِ 4 است؛ روشِ سوم O(n) است و ستونِ نسبتش نزدیکِ 2. ولی نتیجهٔ اصلیِ آن فصل در جدول نیست: یک «امضای هوشمند» می‌سازیم که سریع‌تر است، هیچ خطایی نمی‌دهد، و از دوازده هزار متنِ یکتا فقط ۳٬۲۱۳تا را می‌بیند.

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

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