پیچیدگی زمانی عملیات‌ها روی انواع توکار

این صفحه پیچیدگی زمانی عملیات‌های مختلف روی انواع توکار در سی‌پایتون را مستند می‌کند. پیاده‌سازی‌های دیگر پایتون ممکن است ویژگی‌های عملکردی متفاوتی داشته باشند. علاوه بر این، هزینه‌های لیست‌شده انواع توکار دقیق را فرض می‌کنند، زیرا نمونه‌های زیرکلاس‌ها ممکن است هزینه‌های متفاوتی داشته باشند.

ما از Big O notation برای توصیف نحوه رشد زمان اجرای یک عملیات با اندازه ورودی‌های آن استفاده می‌کنیم. مگر اینکه خلاف آن ذکر شده باشد، n تعداد المان‌های فعلی در ظرف را نشان می‌دهد، و k مقدار یک پارامتر عددی است، مانند یک اندیس یا تعداد تکرار.

list

فهرست‌ها دنباله‌های تغییرپذیر هستند؛ برای جزئیات بیشتر در مورد پیاده‌سازی به فهرست‌ها در CPython چگونه پیاده‌سازی شده‌اند؟ مراجعه کنید. بزرگترین هزینه‌ها ناشی از رشد فراتر از اندازه تخصیص فعلی است (چون همه چیز باید جابجا شود)، یا از درج یا حذف در جایی نزدیک به ابتدا (چون همه چیز بعد از آن باید جابجا شود). اگر نیاز به اضافه یا حذف در هر دو طرف دارید، به جای آن از collections.deque استفاده کنید.

عملیات

پیچیدگی

کپی (l.copy())

O(n)

افزودن (l.append(x)) [1]

O(1)

حذف (l.pop(k)) [1] [2]

O(n - k)

درج (l.insert(k, x)) [1] [2]

O(n - k)

دریافت آیتم (l[k])

O(1)

تنظیم آیتم (l[k] = x)

O(1)

حذف آیتم (del l[k]) [2]

O(n - k)

پیمایش

O(n)

دریافت اسلایس (l[i:j])

O(j - i)

تنظیم اسلایس (l[i:j] = t) [1]

O(j - i) اگر len(t) == j - i، در غیر این صورت O(n - i + len(t))

حذف اسلایس (del l[i:j])

O(n - i)

گسترش (l.extend(t)) [1] [3]

O(len(t))

مرتب‌سازی (l.sort()) [4]

O(n log n)

الحاق (l1 + l2)

O(len(l1) + len(l2))

ضرب (l * k)

O(nk)

x in l

O(n)

min(l), max(l)

O(n)

بدست آوردن طول (len(l)) [5]

O(1)

tuple

یک tuple یک تغییرناپذیر دنباله است. از آنجا که یک تاپل هرگز تغییر نمی‌کند، هزینه‌ی درج یا حذف وجود ندارد، و ایجاد یک کپی صرفاً همان شیء را بازمی‌گرداند، بنابراین زمان ثابت است (O(1)).

عملیات

پیچیدگی

کپی (tuple(t))

O(1)

دریافت آیتم (t[k])

O(1)

دریافت اسلایس (t[i:j])

O(j - i)

الحاق (t1 + t2)

O(len(t1) + len(t2))

ضرب (t * k)

O(nk)

پیمایش

O(n)

x in t

O(n)

min(t), max(t)

O(n)

دریافت طول (len(t)) [5]

O(1)

dict, frozendict

زمان‌های فهرست‌شده برای شیء‌ها dict زمان‌های حالت‌میانگین هستند، زیرا آن‌ها فرض می‌کنند که تابع هش برای شیء‌ها به‌قدر کافی قوی است تا تصادفات را کم کند. آن‌ها همچنین فرض می‌کنند که کلیدها در میان مجموعه‌ی کلیدهای ممکن به‌خوبی توزیع شده‌اند. در بدترین حالت، وقتی هر کلید به یک مقدار هش می‌شود، هر یک از عملیات‌های O(1) در زیر در عوض زمان O(n) می‌طلبد. آن‌ها همچنین فرض می‌کنند که هش کردن و مقایسه یک کلید O(1) است. برای جزئیات بیشتر در مورد پیاده‌سازی، به دیکشنری‌ها در CPython چگونه پیاده‌سازی شده‌اند؟ مراجعه کنید.

A frozendict is immutable, so it does not support setting, deleting, or updating items. The other operations below apply to it at the same costs.

عملیات

پیچیدگی

key in d

O(1)

Copy (d.copy()) [6] [7]

O(n)

دریافت آیتم (d[key], d.get(key))

O(1)

تنظیم آیتم (d[key] = value) [1]

O(1)

حذف آیتم (del d[key], d.pop(key))

O(1)

به‌روزرسانی (d.update(t), d |= t) [1] [3] [7]

O(len(t))

پیمایش [7]

O(n)

دریافت طول (len(d)) [5]

O(1)

set, frozenset

از dict ببینید زیرا پیاده‌سازی‌های set و frozenset مشابه هستند، و همان احتیاط‌ها اعمال می‌شوند. در بدترین حالت، عملیات‌های O(1) به جای آن زمان O(n) می‌برند، و عملیات‌هایی که به جستجوی هر المان می‌پردازند به‌طوری مشابه کاهش می‌یابند.

یک frozenset تغییرناپذیر است، بنابراین از افزودن، حذف، یا عملیات‌های به‌روزرسانی درجا پشتیبانی نمی‌کند. موارد دیگر در پایین با همان هزینه‌ها بر آن اعمال می‌شوند.

عملیات

پیچیدگی

x in s

O(1)

کپی (s.copy()) [6] [7]

O(n)

افزودن (s.add(x)) [1]

O(1)

حذف (s.discard(x), s.remove(x))

O(1)

اتحاد (s1 | s2, s1.union(s2)) [7]

O(len(s1) + len(s2))

به‌روزرسانی (s1 |= s2, s1.update(s2)) [1] [7]

O(len(s2))

تقاطع (s1 & s2, s1.intersection(s2)) [7] [8]

O(min(len(s1), len(s2)))

به‌روزرسانی تقاطع (s1 &= s2, s1.intersection_update(s2)) [1] [7] [8]

O(min(len(s1), len(s2)))

تفاضل (s1 - s2, s1.difference(s2)) [7] [9]

O(len(s1))

به‌روزرسانی تفاضل (s1 -= s2, s1.difference_update(s2)) [1] [7] [8]

O(min(len(s1), len(s2)))

تفاضل متقارن (s1 ^ s2, s1.symmetric_difference(s2)) [7]

O(len(s1) + len(s2))

به‌روزرسانی تفاضل متقارن (s1 ^= s2, s1.symmetric_difference_update(s2)) [1] [7]

O(len(s2))

دریافت طول (len(s)) [5]

O(1)

str, bytes, bytearray

str و bytes به‌ترتیب دنباله‌های تغییرناپذیری از نویسه‌ها و بایت‌ها هستند. مانند تاپل‌ها، کپی کردن یکی از آن‌ها همان شیء اصلی را برمی‌گرداند. bytearray تغییرپذیر است و علاوه بر این، عملیات تغییر‌دهنده‌ی list (به‌جز sort()) را با همان هزینه‌ها پشتیبانی می‌کند. بااین‌حال، حذف از ابتدای آن با del (del b[0]، del b[:k]) فقط ابتدای بافر را جلو می‌برد، به‌جای اینکه بایت‌های باقی‌مانده را جابه‌جا کند، و پیچیدگی آن به‌طور سرشکن O(1) است.

عملیات

پیچیدگی

دریافت آیتم (s[k])

O(1)

دریافت اسلایس (s[i:j])

O(j - i)

الحاق (s + t) [10]

O\ (len(s) + len(t))

ضرب (s * k)

O(nk)

جستجوی زیررشته (x in s، s.find(x)، s.index(x)) [11]

O(n)

جستجوی معکوس زیررشته (s.rfind(x)، s.rindex(x)) [11] [12]

O\ (n × len(x))

کدگذاری یا کدگشایی [13]

O(n)

پیمایش

O(n)

دریافت طول (len(s)) [5]

O(1)

memoryview

شیء‌های memoryview به کد پایتون اجازه می‌دهند تا به داده‌های درونی یک شیء که از پروتکل بافر پشتیبانی می‌کند، بدون کپی کردن دسترسی پیدا کنند. به‌ویژه، برش یک نمای حافظه یک نما جدید بر روی همان بافر را برمی‌گرداند.

عملیات

پیچیدگی

ساخت (memoryview(obj))

O(1)

دریافت آیتم (v[k])

O(1)

دریافت اسلایس (v[i:j])

O(1)

اندیس (v.index(x)) [11] [14]

O(n)

شمارش (v.count(x)) [14]

O(n)

تبدیل به بایت‌ها (v.tobytes(), bytes(v))

O(n)

دریافت طول (len(v)) [5]

O(1)

range

یک شیء range آیتم‌های خود را به‌صورت تقاضا‌محور از مقادیر start، stop و step محاسبه می‌کند، بنابراین اکثر عملیات به طول محدوده وابسته نیستند.

عملیات

پیچیدگی

دریافت آیتم (r[k])

O(1)

دریافت اسلایس (r[i:j])

O(1)

x in r [15]

O(1)

اندیس و شمارش (r.index(x)، r.count(x)) [15]

O(1)

پیمایش

O(n)

min(r)، max(r)

O(n)

دریافت طول (len(r)) [5]

O(1)

یادداشت‌ها