تصویر شاخص نوشته: ساختمان داده در پایتون: list، tuple، dict، set، deque و heapq را کِی به کار ببریم

ساختمان داده در پایتون: 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

سه نکته را معمولاً کسی نمی‌گوید:

  1. «به‌طور میانگین» قید واقعی است. فصل‌های ترم ۳ بنیاد ورودی خصمانه‌ای می‌سازند که همهٔ کلیدها در یک خانه بیفتند، و آن‌جا جست‌وجو دوباره خطی می‌شود.
  2. ساختن set رایگان نیست. ساختنش یعنی n بار hash گرفتن. در اندازه‌گیری فصل set و dict روی یک فهرست دویست‌هزارتایی، برای یک یا دو پرسش، جست‌وجوی مستقیم در list ارزان‌تر بود. نقطهٔ سربه‌سر بین چهار و هشت پرسش افتاد. اگر فقط یک بار می‌پرسی، set ساختن صرف نمی‌کند.
  3. 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 و فقط با کتابخانهٔ استاندارد.

  • ۶ ترم
  • ۴۹ فصل
  • همهٔ فصل‌ها رایگان

برای خواندن بدون اینترنت

خودآموز دانلودی بنیاد

PDF، EPUB، MOBI · ۸۲۴ صفحه

۲۹۹٬۰۰۰ تومان

دیدن نسخهٔ دانلودی