
ساختمان داده در پایتون: list، tuple، dict، set، deque و heapq را کِی به کار ببریم
ساختمان داده یعنی روشی که داده در حافظه چیده میشود تا یک کار مشخص روی آن ارزان باشد. پایتون شش ساختمان دادهٔ پرکاربرد آماده دارد: list برای دنبالهٔ مرتب با دسترسی با اندیس، tuple برای دنبالهٔ ثابت، dict برای «کلید ← مقدار»، set برای «هست یا نه؟»، deque برای صف، و heapq برای «کوچکترین بعدی کدام است؟». هیچکدام در همهچیز بهتر نیست. هر کدام یک کار را ارزان میکند و بهایش را جای دیگری میگیرد.
(در بعضی کتابها و در خودآموز بنیاد به این مفهوم «ساختار داده» هم میگویند. هر دو یک چیزند.)
سؤال اول: برنامهات چه کاری را بیشتر انجام میدهد؟
پیش از انتخاب ظرف باید «الگوی دسترسی» را بدانی: کدام عملیات چند بار انجام میشود. چند نمونه:
- با اندیس میخوانی، مثلاً «عضو هزارم»؟
- فقط به انتها اضافه میکنی، یا از ابتدا هم برمیداری؟
- مدام میپرسی «این عضو هست یا نه؟»
- مدام کوچکترین یا مهمترین عضو را میخواهی؟
یک ظرف ممکن است برای یکی از اینها عالی و برای دیگری فاجعه باشد. برای همین اول باید کار را شناخت، بعد ظرف را.
list: نوار پیوسته
list عضوها را پشتسرهم در حافظه نگه میدارد. نتیجهاش این است:
| عملیات | هزینه | چرا |
|---|---|---|
خواندن با اندیس a[i] |
O(1) |
جای خانه با یک حساب ساده معلوم است |
افزودن به انتها append |
O(1) بهطور سرشکن (amortised) |
گاهی کل نوار به جای بزرگتری کپی میشود، ولی آنقدر کم که میانگین ثابت میماند |
برداشتن از انتها pop() |
O(1) |
چیزی جابهجا نمیشود |
افزودن یا برداشتن از ابتدا insert(0, x)، pop(0) |
O(n) |
همهٔ عضوهای بعدی یک خانه جابهجا میشوند |
پرسش عضویت x in a |
O(n) |
باید تکتک عضوها را نگاه کند |
اینها همان چیزی است که فصلهای ترم ۲ بنیاد اندازه میگیرند. list بهترین stack پایتون است، چون append و pop() هر دو از انتها کار میکنند. ولی برای صف، که از ابتدا برمیدارد، انتخاب بدی است.
tuple: همان دنباله، ولی ثابت
tuple مثل list دنباله است و با اندیس خوانده میشود، ولی بعد از ساختن عوض نمیشود. این محدودیت یک امتیاز مهم میدهد: اگر همهٔ عضوهایش قابلhash باشند، tuple خودش میتواند کلید dict یا عضو set باشد. list نمیتواند.
grid = {(0, 0): "start", (2, 3): "goal"}
print(grid[(2, 3)])
try:
bad = {[2, 3]: "goal"}
except TypeError as e:
print("TypeError:", e)
goal
TypeError: cannot use 'list' as a dict key (unhashable type: 'list')
متن دقیق پیام خطا در نسخههای مختلف پایتون کمی فرق دارد، ولی عبارت unhashable type همیشه هست. هر جا کلید مرکب لازم داری، مثل مختصات یا «نام و تاریخ»، tuple جواب است.
dict و set: جدول hash
dict و set هر کلید را با یک تابع hash به یک خانه در یک جدول میبرند. پس برای فهمیدن اینکه کلیدی هست یا نه، لازم نیست همه را نگاه کنند. پرسش عضویت و خواندن با کلید بهطور میانگین O(1) است.
from collections import Counter
words = "red blue red green blue red".split()
counts = {}
for w in words:
counts[w] = counts.get(w, 0) + 1
print(counts)
print(Counter(words).most_common(1))
seen = set(words)
print(sorted(seen), "blue" in seen)
{'red': 3, 'blue': 2, 'green': 1}
[('red', 3)]
['blue', 'green', 'red'] True
سه نکته را معمولاً کسی نمیگوید:
- «بهطور میانگین» قید واقعی است. فصلهای ترم ۳ بنیاد ورودی خصمانهای میسازند که همهٔ کلیدها در یک خانه بیفتند، و آنجا جستوجو دوباره خطی میشود.
- ساختن
setرایگان نیست. ساختنش یعنیnبارhashگرفتن. در اندازهگیری فصل set و dict روی یک فهرست دویستهزارتایی، برای یک یا دو پرسش، جستوجوی مستقیم درlistارزانتر بود. نقطهٔ سربهسر بین چهار و هشت پرسش افتاد. اگر فقط یک بار میپرسی،setساختن صرف نمیکند. setترتیب ندارد،dictدارد.dictترتیب درج را نگه میدارد. ترتیب چاپ یکsetاز رشتهها حتی بین دو اجرا عوض میشود، برای همین در کد بالا ازsortedاستفاده کردیم.
deque: صف درست
deque از کتابخانهٔ collections برای افزودن و برداشتن از هر دو سر ساخته شده است. popleft() در آن O(1) است، در حالی که pop(0) روی list همهٔ عضوها را جابهجا میکند. این کد هر دو را اندازه میگیرد:
import time
from collections import deque
def best_of(fn, repeat=5):
times = []
for _ in range(repeat):
start = time.perf_counter()
fn()
times.append(time.perf_counter() - start)
return min(times)
def drain_list(n):
q = list(range(n))
while q:
q.pop(0) # removes from the front: shifts everything left
def drain_deque(n):
q = deque(range(n))
while q:
q.popleft() # removes from the front: no shifting
for n in (20_000, 40_000, 80_000):
a = best_of(lambda: drain_list(n))
b = best_of(lambda: drain_deque(n))
print(f"{n:>7,} list {a*1000:7.1f} ms deque {b*1000:5.2f} ms")
نتیجهٔ یک اجرای واقعی (عددهای تو فرق میکنند، نسبتها نباید خیلی فرق کنند):
n |
list با pop(0) |
deque با popleft() |
|---|---|---|
20,000 |
19.7 ms |
0.65 ms |
40,000 |
82.3 ms |
1.43 ms |
80,000 |
326.8 ms |
2.94 ms |
ستون list با هر دو برابرشدن n حدود چهار برابر میشود (82.3 ÷ 19.7 ≈ 4.2 و 326.8 ÷ 82.3 ≈ 4.0). یعنی صف با list درجهدوم است. ستون deque حدود دو برابر میشود، یعنی خطی. اگر این نسبتها برایت آشنا نیست، Big O به زبان ساده همین خواندن را توضیح میدهد.
ولی deque هم بهایی دارد. خواندن عضو وسطش با اندیس گران است، چون باید از یکی از دو سر راه بیفتد. در جدول فصل انتخاب دنباله خواندن با اندیس تصادفی در deque حدود ده برابر list طول کشید.
heapq: همیشه کوچکترین
heapq ظرف جدایی نیست. چند تابع است که یک list معمولی را به شکل heap نگه میدارد: کوچکترین عضو همیشه در h[0] است. افزودن با heappush و برداشتن کوچکترین با heappop هر دو O(log n) هستند.
import heapq
tasks = []
heapq.heappush(tasks, (3, "write report"))
heapq.heappush(tasks, (1, "fix bug"))
heapq.heappush(tasks, (2, "reply email"))
print(heapq.heappop(tasks))
print(heapq.nlargest(2, [5, 1, 9, 3, 7]))
(1, 'fix bug')
[9, 7]
heapq.nlargest چند بزرگترین عضو را بدون مرتبکردن کل داده پیدا میکند. فصل heap در بنیاد نشان میدهد که روی ورودی تصادفی، درج بهطور متوسط تقریباً هزینهٔ ثابت دارد و log n بیشتر در برداشتن است.
یک دام هم هست: وقتی دو tuple اولویت برابر دارند، پایتون عضو دوم را مقایسه میکند. اگر عضو دوم چیزی مثل dict باشد که مقایسه نمیشود، TypeError میگیری. راه رایج این است که یک شمارنده وسط بگذاری: (priority, counter, item).
جدول انتخاب
| کاری که زیاد انجام میدهی | ظرف مناسب |
|---|---|
| خواندن با اندیس دلخواه | list |
افزودن و برداشتن فقط از انتها (stack) |
list |
افزودن از یک سر و برداشتن از سر دیگر (queue) |
deque |
| دنبالهٔ ثابت، یا کلید مرکب | tuple |
| پرسش مکرر «هست یا نه؟» | set |
| رسیدن به مقدار با یک نام یا شناسه، یا شمردن | dict |
| گرفتن مکرر کوچکترین یا مهمترین | heapq |
این جدول نقطهٔ شروع است، نه حکم. همیشه کار واقعی خودت را اندازه بگیر. خودآموز بنیاد همین قاعده را دارد: هیچ ادعای هزینهای بدون جدول اندازهگیری. خودآموز دانلودی بنیاد نسخهٔ دانلودی همین دوره است.
اگر میخواهی این موضوع را کامل یاد بگیری
ساختمان داده و الگوریتم، با اندازهگیری واقعی
ساختمان داده و الگوریتم را با پایتون یاد بگیر، با اندازهگیری بهجای حفظکردن. کدت درست کار میکند و روی دادهٔ واقعی غیرقابلِ استفاده است. این دوره میگوید چرا — و مهمتر، چطور قبل از اجرا پیشبینیاش کنی: اندازهگیریِ صادقانهٔ زمان، Big-O بهعنوان یک پیشبینی که آزمون میدهد، list و hash و درخت و گراف، مرتبسازی و جستوجو، و یک قاعدهٔ سخت — هیچ ادعای پیچیدگی بدونِ جدولِ اندازهگیری. همه در Google Colab، فقط روی CPU و فقط با کتابخانهٔ استاندارد.
- ۶ ترم
- ۴۹ فصل
- همهٔ فصلها رایگان




