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

فصل ۶ از ۹

پیشرفت ترم
۰٪

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

هر بار که هزینهٔ جابه‌جایی را دیدیم، یک فکر پیش آمد: اگر خانه‌ها لازم نبود کنارِ هم باشند، هیچ‌کدام از این جابه‌جایی‌ها لازم نمی‌شد.

این فصل آن ظرف را می‌سازد. linked list هیچ نوارِ پیوسته‌ای ندارد؛ هر عضو یک گره است که مقدارش را نگه می‌دارد و یک ارجاع به گرهٔ بعدی. درج در جایی که ارجاعش را داری، O(1) است — بدونِ هیچ جابه‌جایی.

بعد اندازه‌اش می‌گیریم و نتیجه منفی درمی‌آید. روی کاری که linked list قرار است در آن برنده باشد، list بیش از چهل برابر سریع‌تر است. این نتیجه را همان‌قدر پررنگ گزارش می‌کنیم که یک نتیجهٔ مثبت را، چون همان‌قدر واقعی است — و دلیلش Big-O نیست: هر قدمِ زنجیر یک دورِ حلقهٔ پایتون است و list همان کار را یکجا انجام می‌دهد.

زنجیری از مهره‌های پراکنده روی میز در برابرِ یک ریلِ فشردهٔ پیوسته

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

  • یک linked list را از صفر بسازی، فقط با listهای دوخانه‌ای
  • بگویی درجِ O(1) دقیقاً کِی ممکن است و چه چیزی را فرض می‌گیرد
  • هزینهٔ رسیدن به جای درج را از هزینهٔ خودِ درج جدا کنی
  • یک نتیجهٔ منفی را کامل و بدونِ لاپوشانی گزارش کنی

قبل از شروع#

از فصلِ ۱: نزدیکیِ داده‌ها در حافظه و ضریبی که برایش اندازه گرفتیم. از فصلِ ۴: هزینهٔ جابه‌جایی در list.

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

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

۱. کوچک‌ترین نسخهٔ ممکن، با دست#

یک گره فقط دو چیز لازم دارد: مقدار، و ارجاع به گرهٔ بعدی. برای همین یک list دوخانه‌ای کافی است. آخرین گره به‌جای گرهٔ بعدی None دارد.

VALUE, NEXT = 0, 1


def linked_from(values):
    """از انتها به ابتدا زنجیر را می‌بندد و سرِ زنجیر را برمی‌گرداند."""
    head = None
    for v in reversed(values):
        head = [v, head]
    return head


def to_list(head):
    """زنجیر را از سر تا ته دنبال می‌کند."""
    out = []
    node = head
    while node is not None:
        out.append(node[VALUE])
        node = node[NEXT]
    return out


small = linked_from([10, 20, 30])
print("خودِ ساختار:", small)
print("پیمایشش    :", to_list(small))
print("گرهٔ اول    :", small[VALUE], "· گرهٔ دوم:", small[NEXT][VALUE],
      "· گرهٔ سوم:", small[NEXT][NEXT][VALUE])
print("بعد از سوم :", small[NEXT][NEXT][NEXT])
خودِ ساختار: [10, [20, [30, None]]]
پیمایشش    : [10, 20, 30]
گرهٔ اول    : 10 · گرهٔ دوم: 20 · گرهٔ سوم: 30
بعد از سوم : None

سه گره، هر کدام دو خانه، و تنها چیزی که آن‌ها را به هم وصل می‌کند یک ارجاع است. هیچ نوارِ پیوسته‌ای در کار نیست؛ سه گره می‌توانند هر جای حافظه باشند.

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

۲. کاری که قرار است در آن برنده باشد#

افزودن به ابتدا در list بدترین حالت بود. در linked list بهترین حالت است.

🤔 اول حدس بزن: ستونِ نسبتِ linked list را حدس بزن، و بعد حدس بزن نسبت به list.insert(0, x) چند برابر سریع‌تر می‌شود.

from collections import deque


def push_front_linked(n):
    head = None
    for i in range(n):
        head = [i, head]
    return head


def push_front_list(n):
    out = []
    for i in range(n):
        out.insert(0, i)
    return out


def push_front_deque(n):
    out = deque()
    for i in range(n):
        out.appendleft(i)
    return out


print("هر سه یک ترتیب می‌دهند؟",
      to_list(push_front_linked(500)) == push_front_list(500)
      == list(push_front_deque(500)))

FRONT = [10_000, 20_000, 40_000, 80_000]
print("\n— linked list")
table([(n, 1000 * clock(lambda k=n: push_front_linked(k), repeat=3)) for n in FRONT],
      "زمان (ms)", ",.2f")
print("\n— list.insert(0, x)")
table([(n, 1000 * clock(lambda k=n: push_front_list(k), repeat=2)) for n in FRONT],
      "زمان (ms)", ",.2f")
print("\n— deque.appendleft")
table([(n, 1000 * clock(lambda k=n: push_front_deque(k), repeat=3)) for n in FRONT],
      "زمان (ms)", ",.2f")
هر سه یک ترتیب می‌دهند؟ True

— linked list
         n         زمان (ms)     نسبت به سطر قبل
    10,000              0.75                   —
    20,000              1.58                2.12
    40,000              4.44                2.81
    80,000             11.87                2.67

— list.insert(0, x)
         n         زمان (ms)     نسبت به سطر قبل
    10,000             23.02                   —
    20,000             88.53                3.85
    40,000            368.27                4.16
    80,000          1,472.19                4.00

— deque.appendleft
         n         زمان (ms)     نسبت به سطر قبل
    10,000              0.33                   —
    20,000              0.69                2.06
    40,000              1.55                2.26
    80,000              2.66                1.71

linked list همان‌طور که وعده داده شده بود از list.insert(0, x) می‌برد — و با فاصلهٔ خیلی زیاد، چون ستونِ یکی حولِ 2 می‌گردد و دیگری نزدیکِ 4 است.

ستونِ linked list بینِ 2 و 3 می‌لرزد و این لرزش خودش یک واقعیت است: هشتاد هزار گرهٔ تازه ساختن، کارِ حافظه است و مثلِ یک عملِ ساده رفتار نمی‌کند. جدولِ deque که هیچ گرهٔ جدایی نمی‌سازد، خیلی صاف‌تر است.

ولی جدولِ سوم را هم ببین: deque همان کار را با ستونِ نسبتِ 2 و زمانِ کمتری انجام می‌دهد. یعنی حتی در بهترین میدانِ linked list، ظرفِ استانداردِ پایتون جلوتر است.

۳. نتیجهٔ منفی: درج در وسط#

بهترین حالتِ linked list وقتی است که ارجاعِ گرهٔ قبل از محلِ درج را داشته باشی. آن‌وقت درج دو خط است و به n هیچ ربطی ندارد.

سؤال این است: آن ارجاع را از کجا می‌آوری؟

🤔 اول حدس بزن: می‌خواهیم دویست بار در وسطِ یک دنبالهٔ nتایی درج کنیم. list باید هر بار نصفِ داده را جابه‌جا کند و linked list باید هر بار تا وسط راه برود. هر دو O(n) هستند. بنویس کدامشان و چند برابر برنده می‌شود.

K = 200


def middle_insert_list(values, k=K):
    out = list(values)
    for i in range(k):
        out.insert(len(out) // 2, -i)
    return out


def middle_insert_linked(head, length, k=K):
    for i in range(k):
        node = head
        for _ in range(length // 2 - 1):      # هزینهٔ رسیدن
            node = node[NEXT]
        node[NEXT] = [-i, node[NEXT]]         # هزینهٔ خودِ درج
        length += 1
    return head


base = list(range(1_000))
print("دو نسخه یک جواب می‌دهند؟",
      middle_insert_list(base) == to_list(middle_insert_linked(linked_from(base), 1_000)))

MID = [20_000, 40_000, 80_000, 160_000]
sources = {n: list(range(n)) for n in MID}
print("\n— list.insert(وسط, x)")
table([(n, 1000 * clock(lambda v=sources[n]: middle_insert_list(v), repeat=2))
       for n in MID], "زمان (ms)", ",.2f")
print("\n— linked list")
table([(n, 1000 * clock(lambda v=sources[n], k=n:
                        middle_insert_linked(linked_from(v), k), repeat=2))
       for n in MID], "زمان (ms)", ",.2f")
دو نسخه یک جواب می‌دهند؟ True

— list.insert(وسط, x)
         n         زمان (ms)     نسبت به سطر قبل
    20,000              0.94                   —
    40,000              1.84                1.96
    80,000              4.05                2.20
   160,000              8.31                2.05

— linked list
         n         زمان (ms)     نسبت به سطر قبل
    20,000             47.37                   —
    40,000             91.81                1.94
    80,000            188.74                2.06
   160,000            411.45                2.18

هر دو ستونِ نسبت نزدیکِ 2 هستند — یعنی از نظرِ Big-O این دو ظرف در این کار برابرند. و linked list ده‌ها برابر کندتر است.

این نتیجهٔ اصلیِ فصل است و هیچ ستارهٔ کنارش نیست: روی همان کاری که کتاب‌های درسی برای linked list مثال می‌زنند، در پایتون و در این بازهٔ n، linked list می‌بازد.

بیایید دقیق‌تر بگوییم کجا می‌بازد، چون «کندتر است» یک گزارشِ ناقص است.

n = 160_000
values = sources[n]
head = linked_from(values)
t_reach = clock(lambda: middle_insert_linked(linked_from(values), n), repeat=2)
t_build = clock(lambda: linked_from(values), repeat=2)
t_list = clock(lambda: middle_insert_list(values), repeat=2)
print(f"n = {n:,} · {K} درج در وسط\n")
print(f"list.insert(وسط, x)              : {1000 * t_list:9.2f} ms")
print(f"linked list (با ساختنِ زنجیر)     : {1000 * t_reach:9.2f} ms")
print(f"  از آن، فقط ساختنِ زنجیر         : {1000 * t_build:9.2f} ms")
print(f"  پس خودِ {K} درج                 : {1000 * (t_reach - t_build):9.2f} ms")
print(f"\nنسبتِ درج‌ها به list             : {(t_reach - t_build) / t_list:9.1f} برابر")
print(f"هر درج در linked list            : "
      f"{1e6 * (t_reach - t_build) / K:9.1f} µs")
print(f"هر درج در list                   : {1e6 * t_list / K:9.1f} µs")
n = 160,000 · 200 درج در وسط

list.insert(وسط, x)              :     17.54 ms
linked list (با ساختنِ زنجیر)     :    407.45 ms
  از آن، فقط ساختنِ زنجیر         :     47.58 ms
  پس خودِ 200 درج                 :    359.87 ms

نسبتِ درج‌ها به list             :      20.5 برابر
هر درج در linked list            :    1799.3 µs
هر درج در list                   :      87.7 µs

ده‌ها برابر، و کلِ اختلاف در «هزینهٔ رسیدن» است، نه در «هزینهٔ درج».

خودِ درج در linked list واقعاً دو خط است. ولی برای رسیدن به گرهٔ وسط، هشتاد هزار بار باید node = node[NEXT] اجرا شود — هشتاد هزار پرشِ حافظه که هر کدام ممکن است جای کاملاً دیگری از حافظه باشد. list هم همان‌قدر خانه را لمس می‌کند، ولی این کار را با یک انتقالِ پیوسته انجام می‌دهد که سخت‌افزار برایش ساخته شده.

ضریبِ فصلِ ۱ فقط بخشِ کوچکی از این فاصله است. روی همین ماشین، هشتاد هزار قدم روی زنجیری که گره‌هایش به‌ترتیب ساخته شده‌اند به‌اندازهٔ یک حلقهٔ پایتونی روی همان تعداد خانهٔ list طول کشید، و با به‌هم‌ریختنِ جای گره‌ها در حافظه حدودِ دو و نیم برابر شد. بیشترِ فاصله از جای دیگری می‌آید: هر قدمِ زنجیر یک دورِ حلقهٔ پایتون است، و insert آن هشتاد هزار خانه را با یک انتقالِ یکجا در کدِ کامپایل‌شده جابه‌جا می‌کند.

⚠️ مواظب باش: این نتیجه nِ خودش را دارد. ادعای ما این است: در پایتون، در بازهٔ ۲۰٬۰۰۰ تا ۱۶۰٬۰۰۰، برای درج در وسط. در زبانی که گره‌ها را می‌شود پشتِ سرِ هم چید، یا وقتی همان ارجاع از قبل دستت است، جواب می‌تواند فرق کند. ولی هیچ‌کدام از این‌ها مجوزِ نوشتنِ «linked list برای درج بهتر است» بدونِ جدول نیست.

۴. دو اندازه‌گیریِ دیگر، برای کامل شدنِ گزارش#

def linked_sum(head):
    total = 0
    node = head
    while node is not None:
        total += node[VALUE]
        node = node[NEXT]
    return total


def list_sum(values):
    total = 0
    for v in values:
        total += v
    return total


n = 160_000
head = linked_from(sources[n])
print("جوابِ دو نسخه یکی است؟", linked_sum(head) == list_sum(sources[n]))
t_l = clock(lambda: list_sum(sources[n]), repeat=3)
t_k = clock(lambda: linked_sum(head), repeat=3)
print(f"\nپیمایشِ کامل — list       : {1000 * t_l:7.2f} ms")
print(f"پیمایشِ کامل — linked list: {1000 * t_k:7.2f} ms   ({t_k / t_l:.2f} برابر)")

node_bytes = sys.getsizeof([0, None])
print(f"\nحافظهٔ خودِ ظرف — list       : {sys.getsizeof(sources[n]):>10,} بایت")
print(f"حافظهٔ گره‌ها — linked list  : {node_bytes * n:>10,} بایت"
      f"   ({node_bytes * n / sys.getsizeof(sources[n]):.1f} برابر)")
جوابِ دو نسخه یکی است؟ True

پیمایشِ کامل — list       :    4.45 ms
پیمایشِ کامل — linked list:    7.72 ms   (1.74 برابر)

حافظهٔ خودِ ظرف — list       :  1,280,056 بایت
حافظهٔ گره‌ها — linked list  : 11,520,000 بایت   (9.0 برابر)

پیمایش کندتر است و حافظه چند برابر. گرهٔ ما دو خانه دارد ولی هر گره خودش یک list کامل با سربارِ خودش است — و همان سربار در چند برابر شدنِ حافظه دیده می‌شود.

📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ یک linked list دستی با list و deque، روی سه کارِ متفاوت، با خروجیِ برابرِ تأییدشده در هر سه. در کدام بازهٔ n؟ ۱۰٬۰۰۰ تا ۸۰٬۰۰۰ برای درج در ابتدا و ۲۰٬۰۰۰ تا ۱۶۰٬۰۰۰ برای درج در وسط و پیمایش. با چند تکرار، و کمینه یا میانگین؟ دو یا سه تکرار به‌علاوهٔ گرم‌کننده، کمینه — و در جدولِ تفکیکی، هزینهٔ ساختنِ زنجیر جدا اندازه گرفته و کم شد، چون بخشی از کارِ سنجیده‌شده نبود.

۵. پس linked list به چه دردی می‌خورد؟#

سه جواب، و هر سه صادقانه:

  1. به‌عنوان یک ظرفِ عمومی در پایتون، به هیچ دردی. list و deque تقریباً همیشه بهترند و کدشان به زبانِ سطحِ پایین‌تری نوشته شده.
  2. به‌عنوان یک ایدهٔ ساختاری، به دردِ خیلی چیزها. ترمِ ۵ همین دوره درخت و گراف می‌سازد و هر دو دقیقاً همین شکل‌اند: گره‌هایی که با ارجاع به هم وصل شده‌اند. اگر این فصل را فهمیده باشی، آن‌جا هیچ چیزِ تازه‌ای در نحوهٔ ساخت نیست.
  3. به‌عنوان یک درسِ روش‌شناسی، به بهترین درد: یک ساختار می‌تواند از نظرِ Big-O بهتر باشد و در عمل ببازد. این دقیقاً همان چیزی است که فصلِ ۹ ترمِ ۱ با نقطهٔ تقاطع نشان داد، این بار بدونِ هیچ نقطهٔ تقاطعی — چون در کلِ بازهٔ آزمایش‌شده، برنده عوض نشد.

✅ چک کن: middle_insert_linked را طوری تغییر بده که به‌جای وسط، در ابتدا درج کند (حلقهٔ رسیدن را کاملاً بردار). زمانش باید به تقریباً صفر برسد و از list ببرد. اگر نبرد، حلقهٔ رسیدن هنوز جایی مانده — و همان یک حلقه تفاوتِ برنده و بازنده است.

🔧 اگر کار نکرد: پرتکرارترین خطای کار با زنجیر این است که یک قدم زیادی جلو بروی:

try:
    node = linked_from([1, 2, 3])
    for _ in range(4):
        node = node[NEXT]
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
TypeError: 'NoneType' object is not subscriptable

None گرهٔ آخر است و خانه ندارد. در list همین اشتباه IndexError می‌داد و می‌گفت اندیس بیرون از بازه است؛ در زنجیر پیام از نوعِ داده حرف می‌زند، نه از طول. دلیلش این است که زنجیر اصلاً طولش را نمی‌داند — برای دانستنِ len باید کلِ زنجیر را بشمارد، که خودش O(n) است.

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

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

کلمه تلفظ به حروف فارسی یعنی چه
linked list لینکد لیست دنباله‌ای از گره‌ها که هر کدام ارجاعِ گرهٔ بعدی را دارد
node نُود یک عضوِ زنجیر: مقدار به‌علاوهٔ ارجاعِ بعدی
pointer chasing پوینتر چیسینگ رفتن از گره به گره با دنبال کردنِ ارجاع‌ها
negative result نگتیو ریزالت نتیجه‌ای که خلافِ انتظار درمی‌آید و باید کامل گزارش شود

تمرین‌ها

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

در فصل بعد#

deque تا اینجا دو بار برنده شده و ما هنوز نگفته‌ایم چیست.

فصلِ بعد دو انضباطِ کلاسیک را روی همان داده می‌گذارد: stack که آخرین ورودی را اول برمی‌دارد، و queue که اولین ورودی را اول. یکی از این دو با list عالی کار می‌کند و دیگری با list یک فاجعهٔ درجه‌دو است — و همان‌جا با عدد می‌بینی که popleft در برابرِ pop(0) در n = 80,000 چند ده برابر فاصله دارد.

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

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