القوائم وكلفة عملياتها
ما الذي يحدث داخل list حين تضيف عنصرًا؟ ولماذا insert(0) بطيئة؟ ⏱ نحو 30 دقيقة.
- تشرح أن القائمة مصفوفة ديناميكية، ومعنى الكلفة المُطفأة.
- تحفظ تعقيد عمليات القائمة الأساسية.
- تتجنب العمليات المكلفة في الحلقات:
insert(0)وinو جمع النصوص. - تتعامل مع القوائم ثنائية الأبعاد وفخ النسخ المشترك.
١القائمة من الداخل: مصفوفة ديناميكية
القائمة list في بايثون مصفوفة: خانات متجاورة في الذاكرة. ولأن الخانات متجاورة، فالوصول إلى أي موقع حساب بسيط: عنوان البداية + رقم الموقع × حجم الخانة، أي O(1).
لكنها ديناميكية: تحجز خانات احتياطية أكثر مما تحتاج. حين تمتلئ، تحجز مساحة أكبر وتنسخ إليها كل العناصر. راقب الحجم بالبايت وهو يقفز:
import sys a = []last = sys.getsizeof(a)print("فارغة:", last, "بايت")for i in range(20): a.append(i) size = sys.getsizeof(a) if size != last: print(f"بعد {len(a):>2} عنصر: {size} بايت ← حجزت مساحة جديدة") last = size
لا تحجز القائمة خانة جديدة مع كل append، بل دفعة كبيرة كل حين. لذلك متوسط كلفة append يبقى O(1)، ويسمى ذلك الكلفة المُطفأة Amortized.
٢جدول كلفة العمليات
| العملية | المثال | التعقيد | السبب |
|---|---|---|---|
| الوصول بالموقع | a[i] | O(1) | حساب العنوان مباشرة |
| التعديل بالموقع | a[i] = x | O(1) | كذلك |
| الإضافة في الآخر | a.append(x) | O(1) مُطفأة | خانات احتياطية |
| الحذف من الآخر | a.pop() | O(1) | لا إزاحة |
| الإدراج في الأول أو الوسط | a.insert(0, x) | O(n) | إزاحة كل ما بعده |
| الحذف من الأول أو الوسط | a.pop(0) | O(n) | إزاحة كل ما بعده |
| البحث | x in a و a.index(x) | O(n) | بحث خطي |
| الطول | len(a) | O(1) | الطول محفوظ |
| الترتيب | a.sort() | O(n log n) | Timsort |
٣الإدراج في الأول مكلف
نعدّ كم عنصرًا يُزاح عند إدراج عناصر في أول القائمة، مقارنة بإضافتها في آخرها:
def shifts_insert_front(n): shifts = 0 a = [] for i in range(n): shifts += len(a) # كل العناصر الموجودة تُزاح خطوة a.insert(0, i) return shifts for n in [100, 1000, 10000]: print(n, "إدراج في الأول ← إزاحات:", shifts_insert_front(n), "| append ← إزاحات: 0")
إضافة n عنصر في الأول: نحو n²/2 إزاحة (O(n²) للكل). فإن كنت تحتاج الإضافة والحذف من الطرفين، استخدم collections.deque (الدرس 14).
٤عادات تجعل كودك أسرع
| بدل… | اكتب… | لماذا |
|---|---|---|
a.insert(0, x) في حلقة | a.append(x) ثم a.reverse() مرة واحدة | O(n) بدل O(n²) |
if x in a في حلقة | s = set(a) ثم if x in s | O(1) بدل O(n) للبحث |
s = s + "…" للنصوص في حلقة | parts.append(…) ثم "".join(parts) | النص غير قابل للتعديل: كل + تنسخه |
a = a + [x] | a.append(x) | الأولى تنسخ القائمة كلها |
# بناء نص من أجزاء: join أفضل من الجمع المتكررwords = ["تراكيب", "البيانات", "والخوارزميات"]parts = []for w in words: parts.append(w)print(" ".join(parts))
٥القائمة ثنائية الأبعاد
المصفوفة ثنائية الأبعاد (جدول) قائمة من قوائم. الوصول إلى grid[r][c] ما زال O(1)، والمرور على كل الخلايا O(rows × cols):
seats = [[0] * 4 for _ in range(3)] # 3 صفوف × 4 مقاعدseats[1][2] = 1 # حجز المقعدfor row in seats: print(row)print("المحجوز:", sum(sum(r) for r in seats))
توقّع وتحقّق
a[5000] في قائمة من مليون عنصر:
a.insert(0, x):
متوسط كلفة append:
أفضل بناء نص من أجزاء كثيرة:
الخلاصة
- القائمة خانات متجاورة:
a[i]بـO(1). appendوpop()بـO(1)، وinsert(0)وpop(0)وinبـO(n).- المصفوفة الديناميكية تضاعف سعتها، فيبقى
appendبـO(1)مُطفأة. - الجدول
[[0] * n for _ in range(m)]، لا[[0] * n] * m.
تحدٍّ برمجي: مصفوفة ديناميكية بنفسك
متقدمابنِ مصفوفة ديناميكية بسيطة: سعة تبدأ بـ 2، وتتضاعف حين تمتلئ. أضف 10 عناصر، واطبع السعة كلما تغيرت، وعدد عمليات النسخ الكلية.
- الكلاس DynArray فيه: data (قائمة بطول السعة) و size و capacity.
- append: إن كانت
size == capacityضاعف السعة وانسخ العناصر (عدّ كل عنصر منسوخ). - اطبع عند كل تغيير: السعة: 4 ثم 8 ثم 16.
- في الأخير: عمليات النسخ: 14
ابدأ من هذا الكود، واضغط ▶ شغّل هنا لتكتب حلّك وتجرّبه مباشرة:
class DynArray: def __init__(self): self.capacity = 2 self.size = 0 self.data = [None] * self.capacity self.copies = 0 def append(self, x): pass
💡 تلميح 1
8: 2 + 4 + 8 = 14.💡 تلميح 2
self.data[self.size] = x ثم self.size += 1حاول بنفسك أولًا؛ للمسألة أكثر من حلّ صحيح.
class DynArray: def __init__(self): self.capacity = 2 self.size = 0 self.data = [None] * self.capacity self.copies = 0 def append(self, x): if self.size == self.capacity: self.capacity *= 2 new = [None] * self.capacity for i in range(self.size): new[i] = self.data[i] self.copies += 1 self.data = new print("السعة:", self.capacity) self.data[self.size] = x self.size += 1 arr = DynArray()for i in range(10): arr.append(i)print("عمليات النسخ:", arr.copies)