طَبِّقْهاتعلّم المبدأ، وطبّقه بيدكمقرر 101 · تركيب البيانات والخوارزميات
الدرس 8 · الوحدة 4: مقدمة في تحليل كفاءة الخوارزميات

قياس الزمن والذاكرة فعليًّا

قبل النظرية: نقيس بالساعة والبايت، ونرى كيف ينمو الزمن مع البيانات. ⏱ نحو 30 دقيقة.

بعد هذا الدرس ستستطيع أن:
  • تميّز بين الكفاءة الزمنية والمساحية والمقايضة بينهما.
  • تقيس زمن التنفيذ بـ perf_counter و timeit.
  • تلاحظ نمط نمو الزمن حين يتضاعف حجم المدخل.
  • تقيس الذاكرة بـ getsizeof و tracemalloc، وتعرف حدود القياس التجريبي.

١ما الكفاءة؟

كفاءة الخوارزمية تعني: كم موردًا تستهلك لتحل المسألة؟ والموردان الأهم:

الموردالسؤاليسمى تحليله
الزمنكم تستغرق حتى تنتهي؟التعقيد الزمني Time Complexity
الذاكرةكم مساحة تحتاج أثناء العمل؟التعقيد المساحي Space Complexity

وبينهما مقايضة كثيرًا: نوفّر الزمن باستهلاك ذاكرة أكثر (مثل حفظ النتائج لنعيد استخدامها)، أو العكس.

٢قياس الزمن بساعة

الدالة time.perf_counter() ساعة دقيقة جدًّا. نأخذ الوقت قبل العمل وبعده، والفرق زمن التنفيذ:

main.py
import time start = time.perf_counter()total = 0for i in range(1_000_000):    total += iend = time.perf_counter() print("المجموع:", total)print("الزمن بالملّي ثانية:", round((end - start) * 1000, 1))
Shell×
>>> %Run main.py
المجموع: 499999500000
الزمن بالملّي ثانية: 111.1
>>>

٣قياس أدق: timeit

القياس مرة واحدة يتأثر بأي برنامج آخر يعمل في الجهاز. المكتبة timeit تكرر التنفيذ وتعطي زمنًا أدق. نقارن طريقتين لمعرفة هل الرقم موجود:

main.py
import timeit setup = "data_list = list(range(100000)); data_set = set(data_list)"t_list = timeit.timeit("99999 in data_list", setup=setup, number=200)t_set  = timeit.timeit("99999 in data_set",  setup=setup, number=200) print("القائمة:", round(t_list * 1000, 2), "ms")print("المجموعة:", round(t_set * 1000, 4), "ms")print("المجموعة أسرع بنحو", round(t_list / t_set), "مرة")
Shell×
>>> %Run main.py
القائمة: 126.76 ms
المجموعة: 0.0118 ms
المجموعة أسرع بنحو 10730 مرة
>>>

٤كيف ينمو الزمن مع حجم المدخل؟

الأهم من زمن حجم واحد: ماذا يحدث حين يتضاعف المدخل؟ نقيس خوارزميتين: الأولى تمر على القائمة مرة واحدة، والثانية تقارن كل عنصر بكل عنصر:

main.py
import time def once(a):                 # مرور واحد    s = 0    for x in a:        s += x    return s def pairs(a):                # كل عنصر مع كل عنصر    c = 0    for x in a:        for y in a:            if x < y:                c += 1    return c def measure(f, n):    a = list(range(n))    t = time.perf_counter()    f(a)    return time.perf_counter() - t for n in [500, 1000, 2000]:    print(n, "| مرور واحد:", round(measure(once, n) * 1000, 2), "ms | كل زوج:", round(measure(pairs, n) * 1000, 1), "ms")
Shell×
>>> %Run main.py
500 | مرور واحد: 0.02 ms | كل زوج: 7.9 ms
1000 | مرور واحد: 0.03 ms | كل زوج: 36.7 ms
2000 | مرور واحد: 0.06 ms | كل زوج: 124.1 ms
>>>

لاحظ النمط لا الأرقام: حين يتضاعف n يتضاعف زمن «المرور الواحد» تقريبًا، ويتضاعف زمن «كل زوج» نحو أربع مرات. هذا النمط هو ما يصفه ترميز O الكبير في الدرس القادم.

٥قياس الذاكرة

sys.getsizeof تعطي حجم الكائن بالبايت. قارن قائمة مليون رقم بـ range الذي لا يخزّن الأرقام بل يولّدها عند الحاجة:

main.py
import sys numbers = list(range(1_000_000))lazy = range(1_000_000)squares_gen = (x * x for x in range(1_000_000)) print("القائمة:", sys.getsizeof(numbers) // 1024, "KB")print("range:", sys.getsizeof(lazy), "بايت")print("المولّد:", sys.getsizeof(squares_gen), "بايت")
Shell×
>>> %Run main.py
القائمة: 7812 KB
range: 48 بايت
المولّد: 200 بايت
>>>

وللقياس الأدق لكل ما يحجزه البرنامج نستخدم tracemalloc:

main.py
import tracemalloc tracemalloc.start()data = [i * 2 for i in range(100_000)]current, peak = tracemalloc.get_traced_memory()tracemalloc.stop()print("أقصى ذاكرة:", peak // 1024, "KB")
Shell×
>>> %Run main.py
أقصى ذاكرة: 3903 KB
>>>

٦حدود القياس التجريبي

المشكلةمثال
يعتمد على الجهازحاسوب المعمل أسرع من جوالك، فالأرقام لا تُقارن بين جهازين.
يتأثر بالبرامج الأخرىتحديث يعمل في الخلفية يبطئ القياس.
يحتاج كتابة الكود أولًالا تقيس فكرة قبل تنفيذها.
لا يغطي كل المدخلاتجربت 1000 عنصر، فماذا عن مليار؟

لذلك نحتاج طريقة نظرية مستقلة عن الجهاز: نعدّ عدد العمليات كدالة في حجم المدخل n. وهذا موضوع الوحدة القادمة.

توقّع وتحقّق

الدالة الأدق لقياس فترة زمنية قصيرة:

ساعة عالية الدقة.

مضاعفة n في خوارزمية «كل زوج» تضاعف الزمن نحو:

n² ← (2n)² = 4n².

أيها يحجز ذاكرة أقل لمليون رقم؟

لا يخزّن الأرقام.

لماذا نحتاج التحليل النظري؟

نعدّ العمليات.

الخلاصة

تحدٍّ برمجي: عدّ العمليات بدل الساعة

متوسط

بدل قياس الزمن، عدّ عمليات المقارنة في دالة «كل زوج» لأحجام مختلفة، ولاحظ النسبة حين يتضاعف n.

المطلوب:
  • دالة count_pairs(n) تُرجع عدد مرات تنفيذ المقارنة x < y لقائمة من n عنصرًا.
  • اطبع لكل n من 10 و 20 و 40: n ثم العدد.
  • اطبع في الأخير نسبة العدد عند 40 إلى العدد عند 20: النسبة: 4.0

ابدأ من هذا الكود، واضغط ▶ شغّل هنا لتكتب حلّك وتجرّبه مباشرة:

main.py
def count_pairs(n):    a = list(range(n))    count = 0    # أكمل    return count
المطلوب×
10 100
20 400
40 1600
النسبة: 4.0
💡 تلميح 1
حلقتان متداخلتان، وفي الداخلية count += 1
💡 تلميح 2
العدد = n × n

حاول بنفسك أولًا؛ للمسألة أكثر من حلّ صحيح.

main.py
def count_pairs(n):    a = list(range(n))    count = 0    for x in a:        for y in a:            count += 1    return count for n in [10, 20, 40]:    print(n, count_pairs(n))print("النسبة:", count_pairs(40) / count_pairs(20))
انتقل إلى تقييم الدرساختيار من متعدد، وصح وخطأ، وأكمل الفراغ، وتتبّع الناتج.ابدأ التقييم ←

📝 معلم؟ أرسل ملاحظة للمؤلف عن هذا الدرس