در این فصل چه یاد میگیری#
هفت فصل ظرف و عملیات دیدیم. این فصل هیچ ظرفِ تازهای برای سرعت معرفی نمیکند؛ یک جدولِ تصمیم میسازد — هزینهٔ هر عملیاتِ اصلی روی هر ظرف، اندازهگیریشده، نه نقلشده از جایی.
بعد یک بارِ کاریِ ثابت را دو بار اجرا میکنیم و فقط نسبتِ خواندن به نوشتن را عوض میکنیم. برنده کاملاً جابهجا میشود: در یکی 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 |
بایتاَرِی | ظرفی از بایتهای خام، برای عددهای صفر تا ۲۵۵ |
تمرینها
اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.
در فصل بعد#
هشت فصل ابزار ساختیم. فصلِ آخر هیچ ابزارِ تازهای نمیسازد و همهشان را روی یک مسئلهٔ واقعی بهکار میبرد: یک سیاههٔ بزرگ، دو بار — یک بار با ظرفهای بد و یک بار با ظرفهای درست، با خروجیِ کاملاً یکسان و یک جدولِ اندازهگیری.
و یک نتیجهٔ خلافِ انتظار هم آنجاست: از دو تصمیمِ بدِ نسخهٔ اول، آنی که همه فوری مقصر میدانند تقریباً بیگناه از آب درمیآید و آنی که کسی نگاهش نمیکند تقریباً تمامِ زمان را میخورد.
به آخر این فصل رسیدی!
اگر ساختی و جواب داد، این دکمه مال توست.