کالکشن‌ها و الگوریتم‌های پایه

این بخش «ساختمان داده» نیست که جای درس ساختمان داده را بگیرد؛ جعبه‌ابزار انتخاب درست در برنامه‌سازی روزمره است: کدام کالکشن، کدام الگوریتم، با چه هزینه‌ای.

چهار کالکشن اصلی

names = ["سارا", "علی", "سارا"]
unique = set(names)              # {'سارا', 'علی'} — حذف تکراری در یک خط
scores = {"سارا": 19, "علی": 17}
print(scores.get("رضا", "ثبت نشده"))  # دسترسی امن با پیش‌فرض

تکرارگر در برابر تکرارپذیر

تکرارپذیر (iterable) چیزی است که می‌شود رویش حلقه زد؛ تکرارگر (iterator) اشاره‌گرِ حالت‌داری است که با next جلو می‌رود و یک‌بارمصرف است.

nums = [1, 2, 3]     # iterable
it = iter(nums)      # iterator
print(next(it))      # 1
print(next(it))      # 2

مولد: دنبالهٔ تنبل

def evens(limit):
    n = 0
    while n < limit:
        yield n
        n += 2

for e in evens(1_000_000_000):
    if e > 10:
        break
    print(e)

مولد هیچ‌وقت کل دنباله را در حافظه نمی‌سازد؛ هر مقدار موقع نیاز تولید می‌شود. برای دادهٔ بزرگ یا جریانی، تفاوت «برنامه‌ای که اجرا می‌شود» و «برنامه‌ای که حافظه تمام می‌کند» همین yield است.

پیچیدگی: زبان مقایسهٔ الگوریتم‌ها

جزئیات کامل نماد و جدول مقایسه در تعریف O بزرگ و پیچیدگی‌های رایج آمده؛ این‌جا فقط شهود: جست‌وجوی خطی در لیست $O(n)$ است، عضویت در set میانگین $O(1)$، و جست‌وجوی دودویی روی دادهٔ مرتب $O(\log n)$.

def linear_search(items, target):
    for i, item in enumerate(items):
        if item == target:
            return i
    return -1

def binary_search(items, target):  # items باید مرتب باشد
    lo, hi = 0, len(items) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1