كيف تعمل المجموعات بشكل مختلف

المجموعات: مبنية لأسئلة العضوية

تخزن المجموعة العناصر الفريدة باستخدام تقنية تسمى hashing. عندما تضيف عنصراً، يحسب الحاسوب hash (بصمة رقمية) تخبره بالضبط أين يخزن ذلك العنصر.

عندما تفحص العضوية، يحسب الحاسوب نفس hash و ينتقل مباشرة إلى المكان الصحيح. بدون مسح.

# مجموعة من الحيوانات الأليفة
pets = {"cat", "dog", "cat", "fish", "dog"}

print(pets)      # {"cat", "dog", "fish"} — العناصر المكررة مزالة
print(len(pets)) # 3 — فقط العناصر الفريدة

لاحظ ثلاثة اختلافات عن القوائم:

1. لا توجد عناصر مكررة. "cat" ظهر مرتين في الإدخال لكن المجموعة تحتفظ بنسخة واحدة فقط.

2. لا ترتيب مضمون. قد تطبع المجموعة العناصر في أي ترتيب.

3. لا وصول بالفهرس. لا يمكنك كتابة pets[0] — المجموعات لا تملك مواضع.

المقابلة: تفقد الترتيب والعناصر المكررة. تكسب اختبار عضوية O(1) — التحقق مما إذا كان العنصر موجوداً يستغرق نفس الوقت سواء كانت المجموعة تحتوي على 5 عناصر أو 5 ملايين.

# فحص العضوية — هل "fish" في المجموعة؟
if "fish" in pets:    # hash("fish") → انتقل إلى الدلو → موجود
    print("found!")   # فحص مكان واحد فقط، ليس 4

مجموعة مقابل قائمة العضوية

لديك 500 اسم طالب مخزنة في مجموعة بدلاً من قائمة.

students = {"Alex", "Maria", ..., "Zara", ...}  # 500 اسم
if "Zara" in students:
    print("enrolled")

مقارنة جنباً إلى جنب

قائمة مرجعية العمليات

استخدم قائمة عندما تحتاج:

- عناصر بترتيب معين (قائمة تشغيل، وصفة، طابور)

- الوصول حسب الموضع (items[3])

- العناصر المكررة محفوظة ("cat" يظهر 3 مرات = 3 قطط)

استخدم مجموعة عندما تحتاج:

- فحص عضوية سريع ("هل رأيت هذا من قبل؟")

- إزالة التكرار التلقائية

- لا يهمك الترتيب

استخدم كليهما عندما تحتاج ترتيب و بحث سريع:

seen = set()     # فحوصات عضوية O(1)
result = []      # يحافظ على ترتيب الإدراج
for item in data:
    if item not in seen:  # فحص O(1)
        seen.add(item)    # إضافة O(1)
        result.append(item)  # إضافة O(1)
# الإجمالي: O(N) — ممر واحد، كل خطوة O(1)

يعطيك نمط "مجموعة + قائمة" أفضل ما في العالمين: نتائج مرتبة مع اكتشاف تكرار سريع.

اختر البنية الصحيحة

ثلاث مشاكل. لكل واحدة، قرر: قائمة، مجموعة، أم كليهما؟

1. تحتاج إلى تخزين قائمة تشغيل الأغاني بالترتيب الذي أضافها المستخدم.

2. تحتاج إلى التحقق بسرعة ما إذا كان اسم المستخدم مأخوذاً بالفعل.

3. تحتاج إلى إزالة رسائل البريد الإلكتروني المكررة من قائمة بريدية لكن احتفظ بها بالترتيب الذي اشتركوا به.

مشكلة إزالة التكرار

مشكلة: إزالة التكرارات، احتفظ بالترتيب

تتلقى قائمة بـ بريد اشتراك البريد الإلكتروني. اشترك بعض الناس مرتين. تحتاج لإرسال بريد واحد لكل شخص، بالترتيب الذي اشتركوا به أولاً.

المحاولة 1: قائمة فقط (بطيء)

signups = ["alice@a.com", "bob@b.com", "alice@a.com", "carol@c.com"]
unique = []
for email in signups:
    if email not in unique:  # مسح O(N) للقائمة الفريدة
        unique.append(email)
# يعمل! لكن: فحص O(N) × N عنصر = O(N²)

مع 100 اشتراك، يفعل هذا ~5,000 فحص. مع 10,000 اشتراك: ~50,000,000 فحص.

المحاولة 2: مجموعة + قائمة (سريع)

signups = ["alice@a.com", "bob@b.com", "alice@a.com", "carol@c.com"]
seen = set()     # O(M) لبناء
unique = []
for email in signups:
    if email not in seen:   # بحث hash O(1)
        seen.add(email)     # إضافة O(1)
        unique.append(email) # إضافة O(1)
# فحص O(1) × N عنصر = O(N)

نفس النتيجة. نفس الترتيب. لكن: 10,000 اشتراك الآن يتطلب ~10,000 فحص بدلاً من ~50,000,000.

احسب التسريع

نسخة القائمة فقط تعمل بـ O(N²). نسخة المجموعة+القائمة تعمل بـ O(N).

لديك 10,000 اشتراك بريد إلكتروني لإزالة التكرار منها.

إيجاد العناصر المشتركة

مشكلة: ابحث عن العناصر في كلا القائمتين

لديك قائمتا فصول دراسية. تحتاج إلى إيجاد الطلاب المسجلين في كلا الفصلين.

طريقة بطيء: حلقات متداخلة O(N × M)

class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b = ["Bob", "Diana", "Eve", "Frank"]
both = []
for student in class_a:        # N تكرارات
    if student in class_b:     # M مسح في كل مرة
        both.append(student)
# O(N × M) — كل طالب ممسوح مقابل جميع class_b

طريقة سريعة: حول قائمة واحدة لمجموعة O(N + M)

class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b_set = set(class_b)     # O(M) لبناء
both = []
for student in class_a:        # N تكرارات
    if student in class_b_set: # O(1) في كل مرة
        both.append(student)
# O(N + M) — بناء المجموعة مرة واحدة، فحص N مرة بـ O(1) لكل واحدة

أو حتى أبسط باستخدام تقاطع المجموعة المدمج في Python:

both = set(class_a) & set(class_b)  # O(N + M)

يعثر العامل & على جميع العناصر التي تظهر في كلا المجموعتين.

أعد الكتابة للسرعة

لدى مدرسة نادي فن و نادي شطرنج بـ 200 عضو لكل منهما. يجد هذا الكود الطلاب في كلا الناديين:

chess_club = [...]   # 200 اسم
art_club = [...]     # 200 اسم
both_clubs = []
for student in chess_club:
    if student in art_club:
        both_clubs.append(student)

إطار عمل القرار

إطار عمل قرار بنية البيانات الخاص بك

في كل مرة تكتب فيها كوداً يخزن مجموعة عناصر، اسأل:

1. هل أحتاج العناصر بترتيب؟ → قائمة

2. هل أحتاج فحوصات عضوية سريعة؟ → مجموعة

3. هل أحتاج ترتيب و فحوصات عضوية سريعة؟ → مجموعة + قائمة معاً

4. هل أحتاج العناصر المكررة؟ → قائمة (المجموعات تسقط التكرارات)

---

الفكرة الأساسية من هذا الدرس: نفس البرنامج، حل نفس المشكلة، يمكن أن يعمل 1,000× إلى 1,000,000× أسرع فقط باختيار بنية البيانات الصحيحة. لا حيل ذكية. لا رياضيات معقدة. فقط اسأل: ما العمليات التي يفعلها كودي بأكثر تكرار؟ ثم اختر البنية حيث تلك العمليات تكلف O(1) بدلاً من O(N).

غطى هذا الدرس القوائم والمجموعات. بنى بيانات أخرى موجودة (قواميس، أشجار، أكوام) تحل مشاكل أخرى. يبقى إطار العمل نفسه: افهم العمليات الخاصة بك، ثم اختر البنية التي تجعلها رخيصة.

---

تريد الغوص أعمق؟ يغطي درسنا Big O معدلات النمو و حسابات التوسع بالتفصيل. انظر Big O: كم السرعة كافية؟. يغطي مسار unhamming العيب الحقيقي (MOAD-0001) حيث أنتج هذا الإصلاح بالضبط من قائمة إلى مجموعة تسريع 1,000× في برمجيات الإنتاج. انظر الفصل المفقود: تعقيد الخوارزمية.

صحح هذا الكود

كتب طالب هذا الكود لعد كم عدد الكلمات الفريدة التي تظهر في كتاب:

words = book.split()           # قائمة بجميع الكلمات
unique_count = 0
checked = []
for word in words:             # N كلمة
    if word not in checked:    # تفحص قائمة checked
        checked.append(word)
        unique_count += 1
print(unique_count)

الكتاب يحتوي على 100,000 كلمة.