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

فصل ۸ از ۹

پیشرفت ترم
۰٪

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

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

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

سه ظرفِ هم‌طول با ساختِ متفاوت، کنارِ سه ابزارِ اندازه‌گیری

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

  • الگوی دسترسیِ یک مسئله را قبل از انتخابِ ظرف بنویسی
  • جدولِ هزینهٔ عملیات را برای list، deque و array بخوانی و راستی‌آزمایی کنی
  • ظرف را از روی نسبتِ خواندن به نوشتن انتخاب کنی، نه از روی عادت
  • بگویی array و bytearray کِی به‌کار می‌آیند و چه چیزی را از تو می‌گیرند

قبل از شروع#

از فصلِ ۱: دسترسی با اندیس در list هزینهٔ ثابت دارد. از فصلِ ۷: deque در دو سرش ارزان است و در وسطش نه.

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

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

۱. الگوی دسترسی: سؤالی که قبل از انتخاب پرسیده می‌شود#

«کدام ظرف بهتر است؟» سؤالِ بی‌جوابی است، دقیقاً مثلِ «کدام ابزار بهتر است؟». سؤالی که جواب دارد این است:

در این مسئله، کدام عملیات چند بار انجام می‌شود؟

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

۲. جدولِ هزینه، اندازه‌گیری‌شده#

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

🤔 اول حدس بزن: برای هر شش خانهٔ این جدول حدس بزن کدام ظرف برنده است — و مخصوصاً برای «خواندنِ خانهٔ وسط» در deque حدس بزن چند برابرِ list می‌شود.

from array import array
from collections import deque

N = 100_000
OPS = 20_000
rng = random.Random(SEED)
picks = [rng.randrange(N) for _ in range(OPS)]


def read_many(box, idxs):
    seen = None
    for i in idxs:
        seen = box[i]
    return seen


def repeat_op(make, op, times=OPS):
    box = make()
    return clock(lambda: [op(box) for _ in range(times)], repeat=3) / times


print(f"{'عملیات':>26}{'list (µs)':>13}{'deque (µs)':>13}{'array (µs)':>13}")
rows = [
    ("خواندن با اندیسِ تصادفی",
     lambda: clock(lambda: read_many(list(range(N)), picks), repeat=3) / OPS,
     lambda: clock(lambda: read_many(deque(range(N)), picks), repeat=3) / OPS,
     lambda: clock(lambda: read_many(array("q", range(N)), picks), repeat=3) / OPS),
    ("افزودن به انتها",
     lambda: repeat_op(lambda: list(range(N)), lambda b: b.append(1)),
     lambda: repeat_op(lambda: deque(range(N)), lambda b: b.append(1)),
     lambda: repeat_op(lambda: array("q", range(N)), lambda b: b.append(1))),
    ("افزودن به ابتدا",
     lambda: repeat_op(lambda: list(range(N)), lambda b: b.insert(0, 1)),
     lambda: repeat_op(lambda: deque(range(N)), lambda b: b.appendleft(1)),
     lambda: repeat_op(lambda: array("q", range(N)), lambda b: b.insert(0, 1))),
]
for name, a, b, c in rows:
    print(f"{name:>26}{1e6 * a():>13.4f}{1e6 * b():>13.4f}{1e6 * c():>13.4f}")
                    عملیات    list (µs)   deque (µs)   array (µs)
   خواندن با اندیسِ تصادفی       0.1198       1.1876       0.3380
           افزودن به انتها       0.0663       0.0534       0.1293
           افزودن به ابتدا      59.4147       0.0595      26.5636

سه سطر، و هیچ ستونی در هر سه برنده نیست.

  • خواندن با اندیس: list ارزان‌ترین است و array نزدیکِ سه برابرش — چون هر خانه‌اش عددِ خام است و برای برگرداندنش باید یک شیءِ پایتونی از رویش ساخته شود. deque نزدیکِ ده برابرِ list است، چون برای رسیدن به اندیسِ وسط باید از یکی از دو سر راه بیفتد.
  • افزودن به انتها: هر سه ارزان و هر سه در یک بازه.
  • افزودن به ابتدا: deque ارزان، و list و array هر دو صدها برابر گران‌تر — چون هر دو نوارِ پیوسته‌اند و باید همه‌چیز را جابه‌جا کنند.

پس جدولِ تصمیم را نمی‌شود به یک ستون خلاصه کرد. هر خانه‌اش یک معامله است.

✅ چک کن: picks را با [0] * OPS عوض کن و فقط سطرِ اول را دوباره بگیر. ستونِ deque باید به‌اندازهٔ list ارزان شود. اگر نشد، picks را جای دیگری هم به‌کار برده‌ای. این آزمایش می‌گوید هزینهٔ deque به خودِ خواندن نیست، به فاصلهٔ اندیس تا نزدیک‌ترین سر است.

۳. همان بارِ کاری، دو نسبتِ متفاوت#

جدولِ بالا هزینهٔ تکِ عملیات را می‌دهد. تصمیم ولی به ترکیب بند است، نه به تک‌عملیات.

پس یک بارِ کاریِ ثابت می‌سازیم و فقط نسبتِ خواندن به نوشتن را عوض می‌کنیم.

🤔 اول حدس بزن: یک بار بیست هزار خواندنِ تصادفی و ده هزار افزودن به ابتدا، یک بار برعکس. بنویس در هر حالت کدام ظرف برنده است و چند برابر.

WRITES = 10_000


def read_only(box, idxs):
    total = 0
    for i in idxs:
        total += box[i]
    return total


def write_front(box, k):
    if isinstance(box, deque):
        for i in range(k):
            box.appendleft(i)
    else:
        for i in range(k):
            box.insert(0, i)
    return len(box)


base_l = clock(lambda: list(range(N)), repeat=3)
base_d = clock(lambda: deque(range(N)), repeat=3)
read_l = clock(lambda: read_only(list(range(N)), picks), repeat=3) - base_l
read_d = clock(lambda: read_only(deque(range(N)), picks), repeat=3) - base_d
write_l = clock(lambda: write_front(list(range(N)), WRITES), repeat=2) - base_l
write_d = clock(lambda: write_front(deque(range(N)), WRITES), repeat=2) - base_d

print(f"روی {N:,} عنصر، هزینهٔ ساختنِ خودِ ظرف کم شده\n")
print(f"{'الگوی دسترسی':>26}{'list (ms)':>13}{'deque (ms)':>13}"
      f"{'برنده':>9}{'چند برابر':>12}")
for label, tl, td in ((f"{OPS:,} خواندنِ تصادفی", read_l, read_d),
                      (f"{WRITES:,} افزودن به ابتدا", write_l, write_d)):
    winner = "list" if tl < td else "deque"
    print(f"{label:>26}{1000 * tl:>13.2f}{1000 * td:>13.2f}"
          f"{winner:>9}{max(tl, td) / min(tl, td):>12,.0f}")
روی 100,000 عنصر، هزینهٔ ساختنِ خودِ ظرف کم شده

              الگوی دسترسی    list (ms)   deque (ms)    برنده   چند برابر
     20,000 خواندنِ تصادفی         1.52        22.76     list          15
    10,000 افزودن به ابتدا       483.71         0.80    deque         607

همان دو ظرف، همان داده، همان n — و برنده عوض شد.

در الگوی خواندن‌محور list بیش از ده برابر جلوست، و در الگوی نوشتن‌محور deque صدها برابر. هیچ‌کدام از این دو عدد به‌تنهایی «کدام ظرف بهتر است» را جواب نمی‌دهد؛ هر دو با هم جواب می‌دهند که سؤال غلط بوده.

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

📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ list و deque روی دو الگوی دسترسیِ متفاوت با همان داده و همان اندیس‌های تصادفیِ ثابت. در کدام بازهٔ n؟ یک اندازه، n = 100,000، با بیست هزار خواندن و ده هزار نوشتن — ادعای این آزمایش دربارهٔ رشد نیست، دربارهٔ ترکیبِ عملیات است. با چند تکرار، و کمینه یا میانگین؟ دو تا سه تکرار، کمینه، و هزینهٔ ساختنِ خودِ ظرف جدا اندازه گرفته و کم شد — وگرنه همان یک ساخت نتیجه را عوض می‌کرد.

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

تا اینجا همه‌چیز دربارهٔ زمان بود. گاهی دیوارِ مسئله زمان نیست، حافظه است — و آن‌جا list گران‌ترین انتخابِ ممکن است.

دلیلش را فصلِ ۱ گفت: هر خانهٔ list یک ارجاع است، نه خودِ مقدار. پس برای صد هزار عدد، هم صد هزار ارجاعِ هشت‌بایتی داری و هم صد هزار شیءِ عددِ جدا.

array از ماژولِ array مقدارها را خام و پشتِ سرِ هم نگه می‌دارد، و bytearray همان کار را برای عددهای صفر تا دویست و پنجاه و پنج می‌کند.

M = 200_000
lst = list(range(M))
arr = array("q", range(M))          # هر عضو یک عددِ صحیحِ هشت‌بایتی
ba = bytearray(M)                   # هر عضو یک بایت
one_int = sys.getsizeof(1_000_000)

print(f"{'ظرف':>12}{'خودِ ظرف':>14}{'با عددها':>16}")
print(f"{'list':>12}{sys.getsizeof(lst):>14,}"
      f"{sys.getsizeof(lst) + M * one_int:>16,}")
print(f"{'array(q)':>12}{sys.getsizeof(arr):>14,}{sys.getsizeof(arr):>16,}")
print(f"{'bytearray':>12}{sys.getsizeof(ba):>14,}{sys.getsizeof(ba):>16,}")
print(f"\nیک عددِ صحیحِ پایتون به‌تنهایی: {one_int} بایت")
print(f"list در برابرِ array : "
      f"{(sys.getsizeof(lst) + M * one_int) / sys.getsizeof(arr):.1f} برابر")
print(f"list در برابرِ bytearray: "
      f"{(sys.getsizeof(lst) + M * one_int) / sys.getsizeof(ba):.1f} برابر")
         ظرف      خودِ ظرف        با عددها
        list     1,600,056       7,200,056
    array(q)     1,691,304       1,691,304
   bytearray       200,057         200,057

یک عددِ صحیحِ پایتون به‌تنهایی: 28 بایت
list در برابرِ array : 4.3 برابر
list در برابرِ bytearray: 36.0 برابر

چند برابر برای array و ده‌ها برابر برای bytearray. روی دویست هزار عضو این یعنی چند مگابایت اختلاف؛ روی بیست میلیون عضو یعنی تفاوتِ «جا می‌شود» و «نشستِ Colab بی‌صدا ری‌استارت می‌شود».

و بهایش این است که این ظرف‌ها فقط یک نوع داده قبول می‌کنند. list هر چیزی را می‌پذیرد چون ارجاع نگه می‌دارد؛ array باید بداند هر خانه چند بایت است، و همان قیدِ فصلِ ۱ است که دسترسی با اندیس را ارزان می‌کند.

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

۵. جدولِ تصمیم#

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

الگوی دسترسی ظرفِ درست چرا (فصل)
خواندنِ زیاد با اندیسِ دلخواه list ۱ — دسترسیِ O(1)
افزودن و برداشتن فقط از انتها (stack) list ۳ و ۷ — append و pop هر دو O(1)ِ amortised
افزودن و برداشتن از هر دو سر (queue) deque ۴ و ۷ — popleft در برابرِ pop(0)
درج در وسط، با اندیس list ۶ — حتی linked list هم نبرد
عددِ خام و زیاد، حافظه تنگ array / bytearray ۸ — چند برابر تا ده‌ها برابر کمتر
پرسشِ مکررِ «هست یا نه؟» هیچ‌کدام ۵ — ترمِ ۳

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

🔧 اگر کار نکرد: array سخت‌گیر است و همان سخت‌گیری چیزی است که ارزانش می‌کند:

try:
    array("q", [1, 2, "سه"])
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
try:
    bytearray([1, 2, 300])
except ValueError as err:
    print(f"{type(err).__name__}: {err}")
TypeError: 'str' object cannot be interpreted as an integer
ValueError: byte must be in range(0, 256)

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

🤖 از دستیارت بپرس: «الگوی دسترسی چیست و چرا قبل از انتخابِ ساختارِ داده باید نوشته شود؟» بعد این را هم بپرس: «اگر بیشترِ کارم خواندن با اندیسِ تصادفی باشد ولی گاهی هم به ابتدا اضافه کنم، کدام ظرف؟» — جوابِ درست به نسبتِ این دو بستگی دارد، و اگر دستیارت بدونِ پرسیدنِ آن نسبت یک ظرف را نام برد، جدولِ بخشِ ۳ را جلویش بگذار.

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

کلمه تلفظ به حروف فارسی یعنی چه
access pattern اکسس پترن اینکه در یک مسئله کدام عملیات چند بار انجام می‌شود
array اَرِی ظرفی که مقدارهای هم‌نوع را خام و پشتِ سرِ هم نگه می‌دارد
bytearray بایت‌اَرِی ظرفی از بایت‌های خام، برای عددهای صفر تا ۲۵۵

تمرین‌ها

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

در فصل بعد#

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

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

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

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