منابع ترجمه · Python Built-ins · فصل ۶
پیچیدگی زمانی عملیات روی نوع‌های درون‌ساخت (مرجع درون‌ساخت‌های پایتون)
منبع اصلی: Python Built-ins, Chapter 6: Time Complexity — Python Software Foundation
💡 این صفحه مثل یک نوت‌بوک Jupyter است: متغیر و تابعی که در یک سلول تعریف شود، در سلول‌های بعدی همین صفحه در دسترس است. سلول‌ها را به ترتیب اجرا کنید، یا با «⏮ تا اینجا» همهٔ سلول‌های قبلیِ اجرانشده را یک‌جا اجرا کنید.
این صفحه پیچیدگی زمانی عملیات گوناگون روی نوع‌های درون‌ساخت در CPython را مستند می‌کند. پیاده‌سازی‌های دیگر پایتون ممکن است ویژگی‌های کارایی متفاوتی داشته باشند. علاوه بر این، هزینه‌های فهرست‌شده فرض می‌کنند نوع‌های درون‌ساخت دقیق (exact) باشند، چون نمونه‌های زیرکلاس‌ها ممکن است هزینه‌های متفاوتی داشته باشند.
ما برای توصیف اینکه زمان اجرای یک عملیات با اندازهٔ ورودی‌هایش چگونه رشد می‌کند، از نماد O بزرگ (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 |
اگر len(t) == j - i باشد O(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 یک دنبالهٔ تغییرناپذیر (immutable) است. چون تاپل هرگز تغییر نمی‌کند، هزینهٔ درج یا حذف ندارد و ساختن کپی صرفاً همان شیء را برمی‌گرداند، پس زمان ثابت است (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 زمان‌های حالت میانگین هستند، چون فرض می‌کنند تابع هش اشیا به‌اندازهٔ کافی مقاوم است تا برخوردها (collisions) نادر باشند. همچنین فرض می‌کنند کلیدها در میان مجموعهٔ کلیدهای ممکن خوب توزیع شده‌اند. در بدترین حالت، وقتی هر کلید به یک مقدار هش یکسان می‌رسد، هر یک از عملیات O(1) زیر در عوض O(n) زمان می‌برد. همچنین فرض می‌کنند هش کردن و مقایسهٔ یک کلید O(1) است. برای جزئیات بیشتر دربارهٔ پیاده‌سازی دیکشنری‌ها در CPython چگونه پیاده‌سازی شده‌اند؟ را ببینید.
frozendict تغییرناپذیر است، بنابراین از تنظیم، حذف یا به‌روزرسانی عناصر پشتیبانی نمی‌کند. عملیات دیگر زیر با همان هزینه‌ها برای آن اعمال می‌شوند.
| عملیات | پیچیدگی |
|---|---|
key in d |
O(1) |
کپی (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 تغییرناپذیر است، بنابراین از افزودن، دور انداختن (discard) یا عملیات به‌روزرسانی درجا پشتیبانی نمی‌کند. عملیات دیگر زیر با همان هزینه‌ها برای آن اعمال می‌شوند.
| عملیات | پیچیدگی |
|---|---|
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) سرشکن (amortized) است.
| عملیات | پیچیدگی |
|---|---|
گرفتن عنصر (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 به کد پایتون اجازه می‌دهند به داده‌های داخلی شیئی که پروتکل بافر را پشتیبانی می‌کند بدون کپی دسترسی داشته باشد. به‌ویژه، برش دادن یک memory view، نمای جدیدی روی همان بافر برمی‌گرداند.
| عملیات | پیچیدگی |
|---|---|
ساختن (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) |
تبدیل به bytes (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) |
یادداشت‌ها
Footnotes
-
سرشکن (Amortized). یک عملیات منفرد ممکن است گاهی هنگام تغییر اندازهٔ ذخیره‌سازی زیربنایی O(n) باشد، اما این هزینه بسته به تاریخچهٔ ظرف روی عملیات زیادی پخش می‌شود. ↩ ↩2 ↩3 ↩4 ↩5 ↩6 ↩7 ↩8 ↩9 ↩10 ↩11 ↩12
-
برداشتن یا حذف عنصر در اندیس k از فهرستی به اندازهٔ n، همهٔ عناصر بعد از k را یک خانه به چپ می‌برد و n - k - 1 عنصر را جابه‌جا می‌کند؛ درج در اندیس k عناصر از k به بعد را یک خانه به راست می‌برد و n - k عنصر را جابه‌جا می‌کند. بدترین حالت اندیس ۰ است، که کل باقی فهرست باید جابه‌جا شود؛ حالت میانگین، یعنی اندیسی در وسط فهرست، O(n/2) = O(n) عملیات می‌برد؛ و عملیات در انتهای فهرست چیزی را جابه‌جا نمی‌کند و O(1) است. ↩ ↩2 ↩3
-
به‌علاوهٔ هزینهٔ پیمایش روی t، که برای یک تکرارپذیر دلخواه ممکن است گران باشد. ↩ ↩2
-
این سناریوی بدترین حالت است. مرتب‌سازی تطبیقی (adaptive) است و ورودی که از قبل مرتب یا معکوس‌مرتب است فقط O(n) مقایسه می‌برد. برای اطلاعات بیشتر
Objects/listsort.txtرا ببینید. ↩ -
تعداد عناصر در خود شیء ذخیره می‌شود، بنابراین
len()لازم نیست آن‌ها را بشمارد. ↩ ↩2 ↩3 ↩4 ↩5 ↩6 ↩7 -
کپی کردن
frozendictیاfrozensetO(1) است چون شیء اصلی را برمی‌گرداند. ↩ ↩2 -
این عملیات جدول هش داخلی ظرف را پویش می‌کنند، که هنگام حذف عناصر کوچک نمی‌شود. پس از حذف بیشتر عناصر، همچنان زمانی متناسب با اندازهٔ پیشین ظرف می‌برند، تا اینکه یک درج بعدی تغییر اندازه را راه بیندازد. ↩ ↩2 ↩3 ↩4 ↩5 ↩6 ↩7 ↩8 ↩9 ↩10 ↩11 ↩12
-
اگر t مجموعه (set) نباشد O(len(s) + len(t)). ↩
-
هر الحاق یک شیء جدید می‌سازد، بنابراین ساختن رشته با الحاق قطعات زیاد در یک حلقه نسبت به طول کل درجه دوم (quadratic) است. برای جایگزین‌ها یادداشت دربارهٔ الحاق دنباله‌های تغییرناپذیر را ببینید. ↩
-
با آرگومان‌های start و end، n طول ناحیه‌ای است که جست‌وجو می‌شود نه طول s، و بر خلاف برش، چیزی کپی نمی‌شود. ↩ ↩2 ↩3
-
این بدترین حالت است. جست‌وجوهای معکوس روی ورودی معمول O(n) هستند. جست‌وجوهای رو به جلو در عوض از الگوریتم پیچیده‌تری با بدترین حالت خطی استفاده می‌کنند که در
Objects/stringlib/stringlib_find_two_way_notes.txtشرح داده شده است. ↩ -
این فرض می‌کند codec به ازای هر نویسه مقدار ثابتی کار انجام می‌دهد. ↩
-
این‌ها هر عنصر را جداگانه از بسته خارج و مقایسه می‌کنند، بنابراین بسیار کندتر از متدهای معادل
bytesهستند. ↩ ↩2 -
با فرض آرگومان‌های
intیاbool. برای نوع‌های دیگر، بازه مانند هر دنبالهٔ دیگر در زمان O(n) جست‌وجو می‌شود. ↩ ↩2