پرسشِ «هست یا نه؟» چقدر خرج دارد

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

«این عضو در فهرست هست یا نه؟» کوتاه‌ترین پرسشی است که از یک ظرف می‌شود پرسید و بی‌آزارترین به‌نظر می‌رسد. در این فصل هزینه‌اش را می‌شماریم و می‌بینیم که برای یک پرسش واقعاً ارزان است — و برای هزار پرسش، همان کد اصلاً تمام نمی‌شود.

شمارندهٔ ترمِ ۱ را برمی‌داریم و دو جدول می‌سازیم: یکی با یک پرسش که ستونِ نسبتش 2.00 می‌دهد، و یکی با پرسش‌هایی که تعدادشان هم با n بالا می‌رود و ستونِ نسبتش 4.00 می‌شود. همان یک پرسش، دو مرتبهٔ کاملاً متفاوت — و تفاوت در خودِ پرسش نیست، در تعدادِ دفعاتش است.

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

• جست‌وجوی خطی را با شمارندهٔ خودت اندازه بگیری و مرتبه‌اش را از ستونِ نسبت بخوانی
• بگویی بهترین، بدترین و متوسطِ یک جست‌وجوی خطی چه فرقی با هم دارند
• تشخیص بدهی کِی یک پرسشِ ارزان، به‌خاطرِ تکرار، به گران‌ترین بخشِ برنامه تبدیل می‌شود

قبل از شروع#

از ترمِ ۱ فصلِ ۴: شمارندهٔ عملیات، و اینکه شمارش قطعی است ولی ثانیه نیست.

از ترمِ ۲ فصلِ ۵: قاعدهٔ تشخیص — یک عملِ O(n) داخلِ یک حلقهٔ nتایی. این فصل همان قاعده را از سمتِ دیگرش نگاه می‌کند: این بار عملِ O(n) را می‌شناسیم و می‌خواهیم بدانیم دقیقاً چقدر خرج دارد.

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

۱. کاری که پایتون واقعاً می‌کند#

x in values یک عبارتِ سه‌کلمه‌ای است، ولی داخلش یک حلقه نشسته: از خانهٔ اول شروع می‌کند، هر عضو را با x مقایسه می‌کند، و به‌محضِ برابری می‌ایستد. اگر هیچ‌کدام برابر نبودند، تا آخر می‌رود. اسمش جست‌وجوی خطی است و «خطی» دقیقاً همان چیزی است که ستونِ نسبت نشان می‌دهد.

می‌نویسیمش تا شمارنده داشته باشیم.

def find_linear(values, target):
    """می‌گردد تا پیدا شود یا فهرست تمام شود؛ تعدادِ مقایسه را هم برمی‌گرداند."""
    ops = 0
    for v in values:
        ops += 1
        if v == target:
            return True, ops
    return False, ops


small = [7, 3, 9, 4]
for target in (7, 4, 5):
    found, ops = find_linear(small, target)
    print(f"دنبالِ {target}: پیدا شد؟ {found} · مقایسه‌ها: {ops}")

دنبالِ 7: پیدا شد؟ True · مقایسه‌ها: 1
دنبالِ 4: پیدا شد؟ True · مقایسه‌ها: 4
دنبالِ 5: پیدا شد؟ False · مقایسه‌ها: 4

سه پرسش روی یک فهرستِ چهارتایی، سه هزینهٔ متفاوت: یک، چهار، چهار.

و همین‌جا سه پرسشِ متفاوت از هم جدا می‌شوند. هزینهٔ پیدا کردنِ 7 که اولِ فهرست است با هزینهٔ پیدا کردنِ 4 که آخرش است یکی نیست، و هزینهٔ نبودن با هزینهٔ بدترین حالتِ بودن یکی است — چون در هر دو حالت کلِ فهرست دیده می‌شود.

n = 1_000
values = list(range(n))
print("بهترین حالت — عضوِ اول:", find_linear(values, 0)[1])
print("بدترین حالت — عضوِ آخر:", find_linear(values, n - 1)[1])
print("اصلاً نبودن در فهرست :", find_linear(values, -1)[1])
print("میانگینِ همهٔ عضوهای موجود:",
      sum(find_linear(values, v)[1] for v in values) / n)

بهترین حالت — عضوِ اول: 1
بدترین حالت — عضوِ آخر: 1000
اصلاً نبودن در فهرست : 1000
میانگینِ همهٔ عضوهای موجود: 500.5

یک، هزار، هزار، و پانصد و نیم. میانگین دقیقاً وسطِ بهترین و بدترین درآمد، و این تصادفی نیست: اگر همهٔ عضوها به یک اندازه پرسیده شوند، به‌طورِ متوسط نصفِ فهرست دیده می‌شود.

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

۲. جدولِ رشد برای یک پرسش#

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

LADDER = [1_000, 2_000, 4_000, 8_000]
pools = {n: list(range(n)) for n in LADDER}
table([(n, find_linear(pools[n], -1)[1]) for n in LADDER], "مقایسه", ",d")

         n            مقایسه     نسبت به سطر قبل
     1,000             1,000                   —
     2,000             2,000                2.00
     4,000             4,000                2.00
     8,000             8,000                2.00

2.00، سه بار پشتِ هم و بدونِ کوچک‌ترین نوسان. شمارنده قطعی است و این عددها روی ماشینِ تو هم دقیقاً همین‌اند.

نسبتِ نزدیکِ 2 یعنی کار پابه‌پای n جلو می‌رود: مرتبهٔ O(n). یک پرسش روی یک ظرفِ ترتیبی O(n) است — و این نه خوب است نه بد، تا وقتی که نگفته باشیم چند بار می‌پرسیم.

۳. همان پرسش، این بار تکراری#

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

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

rng = random.Random(SEED)
asks = {n: [rng.randrange(4 * n) for _ in range(n // 4)] for n in LADDER}


def ask_all(values, questions):
    """به هر پرسش جداگانه جواب می‌دهد و مقایسه‌ها را روی هم جمع می‌زند."""
    ops = 0
    for q in questions:
        ops += find_linear(values, q)[1]
    return ops


print("تعدادِ پرسش در هر سطر:", [len(asks[n]) for n in LADDER])
table([(n, ask_all(pools[n], asks[n])) for n in LADDER], "مقایسه", ",d")

تعدادِ پرسش در هر سطر: [250, 500, 1000, 2000]
         n            مقایسه     نسبت به سطر قبل
     1,000           212,263                   —
     2,000           894,367                4.21
     4,000         3,527,341                3.94
     8,000        14,051,508                3.98

نزدیکِ 4، نه 2. و هیچ چیزی در خودِ پرسش عوض نشده؛ فقط تعدادِ پرسش‌ها هم با n بالا رفته.

منطقش یک ضرب است: n/4 پرسش، هر کدام تا n مقایسه، روی هم n²/4. دو برابر شدنِ n هر دو عامل را دو برابر می‌کند، پس حاصل‌ضرب چهار برابر می‌شود. این دقیقاً همان قاعدهٔ تشخیصِ ترمِ ۲ فصلِ ۵ است — یک عملِ O(n) داخلِ حلقه‌ای که خودش nتایی است — با این تفاوت که این بار هیچ حلقهٔ تودرتویی در کدِ ما نیست. حلقهٔ دوم داخلِ find_linear پنهان است.

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

۴. ساعت هم همان را می‌گوید#

table([(n, 1000 * clock(lambda v=pools[n], q=asks[n]: ask_all(v, q), repeat=3))
       for n in LADDER], "زمان (ms)", ",.1f")

         n         زمان (ms)     نسبت به سطر قبل
     1,000               6.3                   —
     2,000              27.0                4.31
     4,000             111.4                4.13
     8,000             455.2                4.09

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

و یک عددِ ساده که ارزشِ نوشتن دارد و از جدولِ شمارش درمی‌آید، نه از ساعت: از سطرِ اول تا سطرِ آخر n هشت برابر شد و تعدادِ مقایسه‌ها بیش از شصت برابر. اگر همین کد را روی سیاهه‌ای با یک میلیون سطر بگذاری، دیگر منتظرش نمی‌مانی.

📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ یک پرسشِ عضویت با n/4 پرسشِ عضویت، روی همان ظرف و همان داده. در کدام بازهٔ n؟ ۱٬۰۰۰ تا ۸٬۰۰۰ عضو، با پرسش‌هایی که یک‌چهارمِ n هستند و از بازه‌ای چهار برابرِ بزرگ‌تر انتخاب شده‌اند، پس بیشترشان جوابِ «نه» می‌گیرند. با چند تکرار، و کمینه یا میانگین؟ جدولِ شمارش یک اجرا — شمارش قطعی است؛ جدولِ زمان سه تکرار به‌علاوهٔ گرم‌کننده، کمینه.

۵. سطری که از ترمِ ۲ خالی ماند#

جدولِ فصلِ ۸ ترمِ ۲ برای هر عملیاتِ هر ظرفِ ترتیبی یک هزینه داشت، و برای x in values نوشته بود O(n). آن سطر درست بود و راهِ حلی نداشت: در یک نوارِ پیوسته، تنها راهِ فهمیدنِ اینکه عضوی هست یا نه، نگاه کردن به همه‌شان است.

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

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

✅ چک کن: در asks عبارتِ rng.randrange(4 * n) را به rng.randrange(n) تغییر بده تا همهٔ پرسش‌ها جوابِ «بله» بگیرند، و جدولِ بخشِ ۳ را دوباره بساز. تعدادِ مقایسه باید تقریباً نصف شود، ولی ستونِ نسبت باید هنوز نزدیکِ 4 بماند. اگر نسبت هم عوض شد، احتمالاً n // 4 را هم دست زده‌ای — و آن‌وقت داری دو چیز را هم‌زمان تغییر می‌دهی، که هیچ آزمایشی از آن درنمی‌آید.

🔧 اگر کار نکرد: رایج‌ترین اشتباه موقعِ نوشتنِ این آزمایش این است که به‌جای ظرف، اندازه‌اش را جلوی in بگذاری:

try:
    limit = 8
    print(3 in limit)
except TypeError as err:
    print(f"{type(err).__name__}: {err}")

TypeError: argument of type 'int' is not iterable

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

🤖 از دستیارت بپرس: «چرا جست‌وجوی خطی برای پرسشی که جوابش «نه» است همیشه بدترین حالت است؟» بعد این را هم بپرس: «اگر فهرستم مرتب بود، پرسشِ عضویت چقدر ارزان‌تر می‌شد؟» — جوابِ درست عددِ log n را می‌آورد و هزینهٔ مرتب‌کردن را هم حساب می‌کند؛ اگر دستیارت فقط از سرعتِ جست‌وجو گفت و از هزینهٔ مرتب‌سازی چیزی نگفت، نصفِ معامله را جا انداخته. (ترمِ ۴ همین معامله را با عدد باز می‌کند.)

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

در فصل بعد#

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

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