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

فصل ۵ از ۹

پیشرفت ترم
۰٪

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

insert(0, x) یک تلهٔ آشکار است. این فصل دربارهٔ تله‌های نامرئی است: چهار تکه کد که هیچ‌کدام حلقهٔ تودرتوی آشکار ندارند و هر چهارتا O(n²) هستند — یا دستِ‌کم می‌توانند باشند.

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

چرخ‌دنده‌ای پنهان که برای هر دندانهٔ دستهٔ بیرونی یک دورِ کامل می‌زند

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

  • چهار شکلِ رایجِ O(n²)ِ تصادفی را در کد بشناسی
  • قاعدهٔ تشخیص را روی کدِ خودت به‌کار ببری
  • بگویی چرا یکی از این چهارتا روی پایتونِ امروز خطی است و چرا نباید رویش حساب کرد

قبل از شروع#

از فصلِ ۴: هزینهٔ درج و حذف بر حسبِ محلش، و اینکه list جابه‌جا می‌کند.

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

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

۱. شکلِ اول: in روی یک list، داخلِ حلقه#

x in known یک عبارتِ کوتاه و بی‌آزار است. ولی اگر known یک list باشد، این عبارت از ابتدا تا آخرش می‌گردد. داخلِ یک حلقهٔ nتایی، همین می‌شود n بار گشتن.

🤔 اول حدس بزن: ستونِ نسبتِ این کد با دو برابر شدنِ n چه عددی می‌دهد؟

rng = random.Random(SEED)


def count_shared(items, known):
    hits = 0
    for x in items:
        if x in known:              # این خط، خودش یک حلقه است
            hits += 1
    return hits


def counted_shared(items, known):
    """همان کار، با شمارندهٔ صریح به‌جای in."""
    ops = 0
    for x in items:
        for y in known:
            ops += 1
            if x == y:
                break
    return ops


LADDER = [250, 500, 1_000, 2_000]
pairs = {n: (rng.sample(range(4 * n), n), rng.sample(range(4 * n), n)) for n in LADDER}
print("— شمارشِ مقایسه‌ها")
table([(n, counted_shared(*pairs[n])) for n in LADDER], "مقایسه", ",d")
— شمارشِ مقایسه‌ها
         n            مقایسه     نسبت به سطر قبل
       250            55,553                   —
       500           218,729                3.94
     1,000           873,254                3.99
     2,000         3,514,059                4.02

4.00. شمارنده قطعی است و جای شک نمی‌گذارد.

🌱 ریشه‌اش کجاست: چرا دقیقاً چهار برابر؟ چون هر یک از n عضوِ items تا n خانهٔ known را می‌بیند، و n بار n می‌شود n². همین شکل در بخش‌های ۲ و ۴ کمی فرق دارد: آن‌جا ظرف در هر دور یکی بزرگ‌تر می‌شود، پس کلِ کار 1 + 2 + … + n است که با باز کردن و فاکتور گرفتن به n(n+1)/2 تبدیل می‌شود — یعنی نصفِ n² به‌علاوهٔ نصفِ n. باز کردن و فاکتور گرفتن در ریشه ترمِ ۳ فصل ۴ ساخته می‌شود. در هر دو حالت جملهٔ n² غالب است و برای همین نسبت به 4 می‌رسد، نه به 2.

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

۲. شکلِ دوم: ساختنِ رشته با +=#

هر کتابی می‌گوید s += "x" در حلقه O(n²) است، چون رشته در پایتون تغییرناپذیر است و هر بار نسخهٔ تازه‌ای ساخته می‌شود.

🤔 اول حدس بزن: بنویس ستونِ نسبتش را چه عددی انتظار داری: 2 یا 4؟

def grow_plain(n):
    s = ""
    for _ in range(n):
        s += "x"
    return s


def grow_with_shadow(n):
    """همان حلقه، فقط یک ارجاعِ دومِ زنده به رشته هم نگه می‌دارد."""
    s = ""
    shadow = s
    for _ in range(n):
        s += "x"
        shadow = s
    return s


TEXT = [20_000, 40_000, 80_000, 160_000]
print("جوابِ دو نسخه یکی است؟", grow_plain(2_000) == grow_with_shadow(2_000))
print("\n— s += 'x'")
table([(n, 1000 * clock(lambda k=n: grow_plain(k), repeat=2)) for n in TEXT],
      "زمان (ms)", ",.2f")
print("\n— همان حلقه، با یک ارجاعِ دومِ زنده")
table([(n, 1000 * clock(lambda k=n: grow_with_shadow(k), repeat=2)) for n in TEXT],
      "زمان (ms)", ",.2f")
جوابِ دو نسخه یکی است؟ True

— s += 'x'
         n         زمان (ms)     نسبت به سطر قبل
    20,000              1.96                   —
    40,000              3.95                2.01
    80,000              8.17                2.07
   160,000             15.49                1.90

— همان حلقه، با یک ارجاعِ دومِ زنده
         n         زمان (ms)     نسبت به سطر قبل
    20,000              7.81                   —
    40,000             26.85                3.44
    80,000             82.95                3.09
   160,000            332.86                4.01

جدولِ اول 2 می‌دهد، نه 4. کتاب‌ها اشتباه نمی‌گویند؛ فقط دربارهٔ پایتونِ امروز حرف نمی‌زنند.

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

پس این میان‌بر یک تضمین نیست، یک شانس است — و شانسی که با یک خط کدِ کاملاً بی‌ربط از دست می‌رود. اگر رشته‌ای را در حلقه می‌سازی، "".join(parts) را به‌کار ببر: همیشه خطی است و به هیچ شرطی بند نیست.

۳. شکلِ سوم: del items[0] مکرر#

def drain_front(n):
    items = list(range(n))
    while items:
        del items[0]
    return len(items)


def drain_back(n):
    items = list(range(n))
    while items:
        del items[-1]
    return len(items)


DEL = [10_000, 20_000, 40_000, 80_000]
print("— del items[0]")
table([(n, 1000 * clock(lambda k=n: drain_front(k), repeat=2)) for n in DEL],
      "زمان (ms)", ",.2f")
print("\n— del items[-1]")
table([(n, 1000 * clock(lambda k=n: drain_back(k), repeat=2)) for n in DEL],
      "زمان (ms)", ",.2f")
— del items[0]
         n         زمان (ms)     نسبت به سطر قبل
    10,000             19.79                   —
    20,000             78.00                3.94
    40,000            324.74                4.16
    80,000          1,212.42                3.73

— del items[-1]
         n         زمان (ms)     نسبت به سطر قبل
    10,000              0.30                   —
    20,000              0.60                1.99
    40,000              1.27                2.10
    80,000              2.74                2.16

4 در برابرِ 2، دقیقاً مثلِ pop(0) در برابرِ pop() در فصلِ قبل. یک نویسه اختلاف — 0 یا -1 — و دو مرتبهٔ متفاوت.

۴. شکلِ چهارم: items = items + [x]#

این یکی موذی‌ترینشان است، چون خیلی شبیهِ append به‌نظر می‌رسد.

def grow_by_concat(n):
    items = []
    for i in range(n):
        items = items + [i]         # یک list تازه، هر بار
    return items


def grow_by_append(n):
    items = []
    for i in range(n):
        items.append(i)             # همان list، هر بار
    return items


CONCAT = [4_000, 8_000, 16_000, 32_000]
print("جوابِ دو نسخه یکی است؟", grow_by_concat(500) == grow_by_append(500))
print("\n— items = items + [x]")
table([(n, 1000 * clock(lambda k=n: grow_by_concat(k), repeat=2)) for n in CONCAT],
      "زمان (ms)", ",.2f")
print("\n— items.append(x)")
table([(n, 1000 * clock(lambda k=n: grow_by_append(k), repeat=2)) for n in CONCAT],
      "زمان (ms)", ",.2f")
جوابِ دو نسخه یکی است؟ True

— items = items + [x]
         n         زمان (ms)     نسبت به سطر قبل
     4,000             14.55                   —
     8,000             69.79                4.80
    16,000            324.32                4.65
    32,000          1,169.11                3.60

— items.append(x)
         n         زمان (ms)     نسبت به سطر قبل
     4,000              0.11                   —
     8,000              0.27                2.39
    16,000              0.54                2.02
    32,000              0.84                1.56

4 در برابرِ 2، با خروجیِ کاملاً یکسان. items + [i] یک list تازه می‌سازد و همه‌چیز را در آن کپی می‌کند؛ append همان ظرف را نگه می‌دارد.

⚠️ مواظب باش: items += [x] — با علامتِ مساوی — رفتارِ append را دارد نه رفتارِ +. سه شکلِ نوشتاریِ نزدیک به هم، دو مرتبهٔ متفاوت. این‌جا هم مثلِ شکلِ دوم، تفاوت در این است که ظرف همان یکی می‌ماند یا دوباره ساخته می‌شود.

۵. قاعدهٔ تشخیص#

هر چهار شکل یک ساختارِ مشترک دارند و این ساختار را می‌شود در یک جمله نوشت:

یک عملِ O(n) داخلِ یک حلقهٔ nتایی.

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

عمل مرتبه چرا کجا اندازه گرفته شد
x in values روی list O(n) از ابتدا می‌گردد همین فصل، بخشِ ۱
values.index(x) O(n) همان ت۲ف۱ بخشِ ۳
values.insert(0, x) · values.pop(0) O(n) همه را جابه‌جا می‌کند ت۲ف۴ بخش‌های ۱ تا ۳
del values[0] O(n) همان همین فصل، بخشِ ۳
a + b روی list یا رشته O(n) ظرفِ تازه می‌سازد و کپی می‌کند همین فصل، بخش‌های ۲ و ۴
list(values) · values[:] O(n) کپیِ کامل ت۲ف۲ بخشِ ۴ (فقط list(values))
values.append(x) O(1) amortised فقط انتها ت۲ف۳ بخشِ ۵
values.pop() · del values[-1] O(1) فقط انتها ت۲ف۴ بخشِ ۳ · همین فصل، بخشِ ۳
values[i] O(1) آدرس را حساب می‌کند ت۲ف۱ بخشِ ۱
len(values) O(1) طول را جدا نگه می‌دارد نسنجیده

یک سطر «نسنجیده» علامت خورده و این عمدی است. len(values) جوابش بدیهی به‌نظر می‌رسد — و این دوره اندازه‌اش نگرفته. values[:] هم همین‌طور: فقط list(values) سنجیده شد. مخصوصاً len: اینکه پایتون طول را جدا نگه می‌دارد به‌جای اینکه هر بار بشمارد، یک جزئیاتِ پیاده‌سازی است، نه یک قانون. در جدولِ خودت هم همین کار را بکن؛ خانهٔ نقل‌شده را با خانهٔ اندازه‌گیری‌شده یک شکل ننویس. (ترمِ ۶ فصلِ ۲ کلِ یک بخش را به همین می‌دهد.)

و بازهٔ n هم بخشی از این جدول است: سطرهای اندازه‌گیری‌شده در بازه‌ای بینِ حدودِ ۲۵۰ و ۱۶۰٬۰۰۰ عضو گرفته شده‌اند. زیرِ چند ده عضو هیچ‌کدام از این مرتبه‌ها دیده نمی‌شوند — همان درسِ ترمِ ۱ فصلِ ۵.

و مهم‌ترین نکتهٔ این جدول ستونِ مرتبه نیست، ستونِ اول است: شش سطرِ اول همه یک خط کدِ کوتاه‌اند. هیچ‌کدامشان شبیهِ حلقه نیستند.

✅ چک کن: count_shared را طوری تغییر بده که known را قبل از حلقه به یک set تبدیل کند و جدولِ زمانش را بگیر. ستونِ نسبت باید از 4 به حدودِ 2 بیفتد. فعلاً همین‌قدر بدان که set پرسشِ عضویت را ارزان می‌کند؛ ترمِ ۳ نشان می‌دهد چطور، و هزینهٔ پنهانش چیست.

📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ چهار الگوی O(n²)، هرکدام با نسخهٔ خطیِ متناظرش که خروجیِ یکسان می‌دهد. در کدام بازهٔ n؟ هر شکل در بازهٔ خودش — از ۲۵۰ تا ۲٬۰۰۰ برای شمارش، و از ۴٬۰۰۰ تا ۱۶۰٬۰۰۰ برای زمان، چون بازه را طوری انتخاب کردیم که هر جدول در حدودِ یک ثانیه تمام شود. با چند تکرار، و کمینه یا میانگین؟ دو تکرار به‌علاوهٔ گرم‌کننده، کمینه، و هر اجرا ورودیِ تازهٔ خودش را می‌سازد.

🔧 اگر کار نکرد: موقعِ درست کردنِ شکلِ چهارم، رایج‌ترین اشتباه این است که + را نگه داری و فقط براکت را برداری:

try:
    items = [1, 2, 3]
    items = items + 4
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
TypeError: can only concatenate list (not "int") to list

پیام صریح است: + روی list فقط list قبول می‌کند. و همین سخت‌گیری یادآورِ همان چیزی است که گران بود — items + [4] یک ظرفِ سوم می‌سازد. اگر یک عضو می‌خواهی اضافه کنی، append کارِ درست است.

🤖 از دستیارت بپرس: «چه عملیاتی در پایتون O(n) هستند ولی شبیهِ یک عملِ ساده به‌نظر می‌رسند؟» بعد این را هم بپرس: «چرا s += "x" در حلقه گاهی خطی است و گاهی درجه‌دو؟» — جوابِ درست به تعدادِ ارجاع‌های زندهٔ آن رشته برمی‌گردد، و اگر دستیارت فقط گفت «همیشه درجه‌دو است»، جدولِ بخشِ ۲ را جلویش بگذار.

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

کلمه تلفظ به حروف فارسی یعنی چه
accidental quadratic اکسیدنتال کوادراتیک کدی که بدونِ حلقهٔ تودرتوی آشکار، O(n²) است
hidden loop هیدن لوپ عملی که در یک خط نوشته می‌شود ولی داخلش روی کلِ داده می‌گردد

تمرین‌ها

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

در فصل بعد#

هر بار که هزینهٔ جابه‌جایی را دیدیم، یک فکر پیش آمده: اگر ظرفی داشتیم که خانه‌هایش لازم نبود کنارِ هم باشند، هیچ‌کدام از این جابه‌جایی‌ها لازم نمی‌شد.

فصلِ بعد آن ظرف را می‌سازد — linked list — و روی همان کاری که قرار است در آن برنده باشد اندازه‌اش می‌گیرد. نتیجه منفی است، و ما همان‌قدر پررنگ گزارشش می‌کنیم که یک نتیجهٔ مثبت را: در یک آزمایش، list بیش از چهل برابر سریع‌تر درمی‌آید. دلیلش هم Big-O نیست.

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

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